基于改进遗传-跳点搜索算法的整经车间机器人调度系统

Robotic scheduling system for weaving workshop based on improved genetic-jump point search algorithm

摘要

针对纺织整经车间机器人系统的任务分配与调度问题,综合考虑整经车间工序流程,提取整经任务特性,构建障碍环境下的整经车间多异构机器人任务分配与路径规划模型。结合实际作业情况,提出一种引入近亲检测的改进遗传算法作为任务分配层,嵌入跳点搜索算法作为路径规划层,采用双层编码方式分别生成任务分配与任务排序染色体,任务分配染色体中引入重编码扩充位置信息,考虑机器人对不同任务的工作效率不同,以最小化机器人路程与完工时间为目标对模型进行求解。仿真结果表明,本文提出的改进遗传-跳点搜索算法能实现整经车间的多机器人任务分配与调度,在中规模算例 EX2 与大规模算例 EX3 中得到的最佳适应度值较传统遗传算法分别低2.1%、13.3%和6.0%、9.1%,且相较于其他对比算法,改进的遗传算法在全局搜索能力、收敛速度与稳定性方面具有优势。

Abstract

Addressing the issue of task allocation and scheduling for robotic systems within textile warping workshops, this research comprehensively examines the process flow of the warping workshop and distills the unique attributes of warping tasks. Consequently, a model is formulated for task allocation and path planning for multiple heterogeneous robots operating in an obstacle-laden warping workshop environment. Drawing upon practical operational scenarios, an enhanced genetic algorithm incorporating kinship detection is introduced at the task allocation level, while a jump point search algorithm is integrated at the path planning level. A dual-layer encoding approach is employed to generate separate chromosomes for task allocation and task sequencing. In the task allocation chromosome, re-encoding is utilized to augment positional information, taking into account the varying efficiency of robots in executing diverse tasks. The objective of the model is to minimize both the travel distance of robots and the completion time. Simulation results demonstrate that the proposed improved genetic algorithm integrated with the jump point search algorithm effectively addresses task allocation and scheduling for multiple robots in warping workshops. Specifically, in medium-scale scenario EX2 and large-scale scenario EX3, the optimal fitness values obtained are 2.1% and 13.3% lower, as well as 6.0% and 9.1% lower, respectively, compared to those achieved by traditional genetic algorithms. Furthermore, the refined genetic algorithm exhibits superior convergence speed and stability compared to its conventional counterpart.

关键词

改进遗传-跳点搜索算法 / 调度系统 / 多异构机器人 / 近亲检测 / 综合最优

Key words

improved genetic-jump point search algorithm / scheduling system / multi-homogeneous robots / cousin detection / comprehensive optimization

参考文献

[1] 阎迪. 纺织机器人的应用及发展趋势[J]. 棉纺织技术, 2017, 45(9): 81-84.

[2] YAN D. Application and development trend of textile robot[J]. Cotton Textile Technology, 2017, 45(9): 81-84.

[3] 席立锋, 周衡书, 陈桂春, 等. 纺织智能化生产技术现状及对纺织工业转型发展的影响[J]. 湖南工程学院学报(自然科学版), 2021, 31(4): 80-85.

[4] XI L F, ZHOU H S, CHEN G C, et al. Current situation of textile intelligent production technology and its influence on transformation and development of textile industry[J]. Journal of Hunan Institute of Engineering (Natural Science Edition), 2021, 31(4): 80-85.

[5] 张洁, 徐楚桥, 汪俊亮, 等. 数据驱动的机器人化纺织生产智能管控系统研究进展[J]. 纺织学报, 2022, 43(9): 1-10.

[6] ZHANG J, XU C Q, WANG J L, et al. Advancement in data-driven intelligent control system for roboticized textile production[J]. Journal of Textile Research, 2022, 43(9): 1-10.

[7] 沈春娅, 方辽辽, 彭来湖, 等. 基于自适应模拟退火算法的整经准备车间排产模型[J]. 纺织学报, 2024, 45(3): 81-86.

[8] SHEN C Y, FANG L L, PENG L H, et al. Production scheduling of warping department based on adaptive simulated annealing algorithm[J]. Journal of Textile Research, 2024, 45(3): 81-86.

[9] 王飞, 杨清平. 面向多无人机物流配送的双层任务规划方法[J]. 北京航空航天大学学报, 2026, 52(1): 94-103.

[10] WANG F, YANG Q P. Two-layer task planning method for multi-UAV logistics distribution[J]. Journal of Beijing University of Aeronautics and Astronautics, 2026, 52(1): 94-103.

[11] 孙孝飞, 郭捷, 魏灿名, 等. 3C智能制造工厂的 AGV 智慧物料传输与调度综述[J]. 中南大学学报(自然科学版), 2025, 56(2): 514-535.

[12] SUN X F, GUO J, WEI C M, et al. Review of AGV smart material transmission and dispatching in 3C smart manufacturing factories[J]. Journal of Central South University (Science and Technology), 2025, 56(2): 514-535.

[13] 张振国, 毛建旭, 谭浩然, 等. 重大装备制造多机器人任务分配与运动规划技术研究综述[J]. 自动化学报, 2024, 50(1): 21-41.

[14] ZHANG Z G, MAO J X, TAN H R, et al. A review of task allocation and motion planning for multi-robot in major equipment manufacturing[J]. Acta Automatica Sinica, 2024, 50(1): 21-41.

[15] TANG J, LIU G, PAN Q T. A review on representative swarm intelligence algorithms for solving optimization problems: applications and trends[J]. IEEE/CAA Journal of Automatica Sinica, 2021, 8(10): 1627-1643.

[16] KATOCH S, CHAUHAN S S, KUMAR V. A review on genetic algorithm: past, present, and future[J]. Multimedia Tools and Applications, 2021, 80(5): 8091-8126.

[17] ZAKA A, JABEEN R, IQBAL KHAN K. Optimization of reliability-redundancy allocation problems: a review of the evolutionary algorithms[J]. Computers, Materials & Continua, 2022, 71(1): 537-571.

[18] 吕超, 李慕宸, 欧家骏. 基于分层深度强化学习的无人机混合路径规划[J]. 北京航空航天大学学报, 2025, 51(10): 3451-3459.

[19] LÜ C, LI M C, OU J J. UAV hybrid path planning based on hierarchical deep reinforcement learning[J]. Journal of Beijing University of Aeronautics and Astronautics, 2025, 51(10): 3451-3459.

[20] 李喆, 吴君, 王顺森, 等. 采用A星-遗传算法的船舶管路智能布置[J]. 西安交通大学学报, 2023, 57(6): 172-180.

[21] LI Z, WU J, WANG S S, et al. Intelligent arrangement of ship pipeline based on Astar-genetic algorithm[J]. Journal of Xi’an Jiaotong University, 2023, 57(6): 172-180.

[22] MUHAMMED B, BEEMARAJ S B, JOSHI A, et al. A novel approach for early-stage automated flowline design[J]. Ocean Engineering, 2023, 277: 114351.

[23] TRAN N Q H, PRODAN I, GRØTLI E I, et al. Safe navigation in a coastal environment of multiple surface vehicles under uncertainties: a combined use of potential field constructions and NMPC[J]. Ocean Engineering, 2020, 216: 107706.

[24] 刘志华, 张冉, 郝梦男, 等. 基于改进 T 分布烟花-粒子群算法的AUV全局路径规划[J]. 电子学报, 2024, 52(9): 3123-3134.

[25] LIU Z H, ZHANG R, HAO M N, et al. AUV global path panning based on improved T-distribution fireworks-particle swarm optimization algorithm[J]. Acta Electronica Sinica, 2024, 52(9): 3123-3134.

[26] ZHOU H L, CHEN G, LU Y J, et al. A permutation-combination heuristics for crane-based automated storage and retrieval systems considering order fulfillment time and energy consumption[J]. Mathematical Biosciences and Engineering, 2024, 21(1): 116-143.

[27] LIU S, FENG B H, BI Y Y, et al. An integrated approach to precedence-constrained multi-agent task assignment and path finding for mobile robots in smart manufacturing[J]. Applied Sciences, 2024, 14(7): 3094.

[28] LI Y, ZHANG R N, JIANG D D. Order-picking efficiency in E-commerce warehouses: a literature review[J]. Journal of Theoretical and Applied Electronic Commerce Research, 2022, 17(4): 1812-1830.

[29] CHU J, TIAN Y Q, YUE Q, et al. Task allocation and path planning for multi-robot systems in intelligent warehousing[J]. Journal of Northwestern Polytechnical University, 2024, 42(5): 929-938.

[30] JIANG Z L, ZHANG X D, WANG P. Grid-map-based path planning and task assignment for multi-type AGVs in a distribution warehouse[J]. Mathematics, 2023, 11(13): 2802.

基金资助

国家重点研发计划支持项目(2022YFB4700600)

国家重点研发计划支持项目(2022YFB4700605)