基于虚拟零部件的零等待约束复杂产品综合调度算法

doi:10.3901/JME.2020.04.246

机械工程学报 ›› 2020, Vol. 56 ›› Issue (4): 246-257.doi: 10.3901/JME.2020.04.246

扫码分享

基于虚拟零部件的零等待约束复杂产品综合调度算法

郭伟飞, 雷琦, 宋豫川, 吕向飞, 李磊

重庆大学机械传动国家重点实验室重庆 400030

收稿日期:2019-02-25 修回日期:2019-08-20 出版日期:2020-02-20 发布日期:2020-04-23
通讯作者: 雷琦(通信作者),女,1976年出生,副教授。主要研究方向为网络化制造、制造业信息化等。E-mail:leiqi@cqu.edu.cn
作者简介:郭伟飞,男,1990年出生,博士研究生。主要研究方向为制造业信息化、智能优化算法。E-mail:gweifei668@163.com;宋豫川,男,1973年出生,教授。主要研究方向为网络化制造、制造业信息化等;吕向飞,男,1984年出生,博士研究生。主要研究方向为网络化制造、智能优化算法;李磊,男,1994年出生。主要研究方向为制造业信息化、智能优化算法。
基金资助:
国家自然科学基金（51205429）、教育部“创新团队发展计划”（IRT_15R64）和工信部“船用柴油机关重件绿色设计平台建设及示范”（CCLS-JB-002）资助项目。

Integrated Scheduling Algorithm of Complex Product with No-wait Constraint Based on Virtual Component

GUO Weifei, LEI Qi, SONG Yuchuan, Lü Xiangfei, LI Lei

State Key Laboratory of Mechanical Transmission, Chongqing University, Chongqing 400030

Received:2019-02-25 Revised:2019-08-20 Online:2020-02-20 Published:2020-04-23

摘要/Abstract

摘要： 针对复杂产品实际生产中工序间存在零等待约束的综合调度问题，提出一种基于设计结构矩阵和遗传算法的综合调度算法。该算法在提出零等待虚拟零部件、非零等待虚拟零部件、叉点虚拟零部件以及子虚拟零部件等概念的基础上，设计一种更为有效的基于数字化虚拟零部件下三角设计结构矩阵的编码方式，不仅满足了复杂产品的加工装配顺序约束关系，而且体现了工序间存在的零等待约束；设计了能满足加工装配顺序约束的遗传算子，避免了不可行子代个体转化操作；提出一种满足零等待约束的解码方法，且能确保染色体经过解码后能够产生主动调度。与现有算法进行对比试验，结果表明所提出的调度算法对于存在零等待约束的复杂产品综合调度问题具有良好的求解速度和质量。

关键词: 零等待约束, 虚拟零部件, 遗传算法, 综合调度

Abstract: For the complex product scheduling problem with no-wait constraint between operations in the actual production, an integrated scheduling algorithm based on design structure matrix and genetic algorithm is proposed. Based on the concepts of no-wait virtual component, wait virtual component, furcated virtual component and child virtual component, a more effective encoding based on lower triangular design structure matrix of digital virtual component is designed, which not only satisfies the sequence constraints of complex product processing and assembly, but also reflects the no-wait constraint between operations. Feasible crossover and mutation methods are designed and avoid the transformation work of infeasible offspring individuals. A decoding method which can meet the no-wait constraint between operations is also presented, and ensures that chromosomes are decoded into active schedules. Experimental results show that the proposed integrated scheduling algorithm has good solution speed and quality for complex product scheduling problem with no-wait constraint between operations.

Key words: no-wait constraint, virtual component, genetic algorithm, integrated scheduling

中图分类号:

TP278

郭伟飞, 雷琦, 宋豫川, 吕向飞, 李磊. 基于虚拟零部件的零等待约束复杂产品综合调度算法[J]. 机械工程学报, 2020, 56(4): 246-257.

GUO Weifei, LEI Qi, SONG Yuchuan, Lü Xiangfei, LI Lei. Integrated Scheduling Algorithm of Complex Product with No-wait Constraint Based on Virtual Component[J]. Journal of Mechanical Engineering, 2020, 56(4): 246-257.

参考文献

[1] 张长胜,孙吉贵,杨轻云,等. 一种求解车间调度的混合算法[J]. 自动化学报,2009,3(3):332-336. ZHANG Changsheng,SUN Jigui,YANG Qingyun,et al. A hybrid algorithm for flowshop scheduling problem[J]. Acta Automatica Sinica,2009,3(3):332-336.
[2] 雷德明. 基于新型教学优化算法的低碳柔性作业车间调度[J]. 控制与决策,2017,32(9):1621-1627. LEI Deming. Novel teaching-learning-based optimization algorithm for low carbon scheduling of flexible job shop[J]. Control and Decision,2017,32(9):1621-1627.
[3] SHAO W,PI D,SHAO Z. A hybrid discrete teaching-learning based meta-heuristic for solving no-idle flow shop scheduling problem with total tardiness criterion[J]. Computers and Operations Research,2018,94:89-105.
[4] 姜天华. 混合灰狼优化算法求解柔性作业车间调度问题[J]. 控制与决策,2018,33(3):503-508. JIANG Tianhua. Flexible job shop scheduling problem with hybrid grey wolf optimization algorithm[J]. Control and Decision,2018,33(3):503-508.
[5] QIN W,ZHANG J,SONG D. An improved ant colony algorithm for dynamic hybrid flow shop scheduling with uncertain processing time[J]. Journal of Intelligent Manufacturing,2018,29(4):891-9041-14.
[6] GONG G,DENG Q,GONG X,et al. A new double flexible job-shop scheduling problem integrating processing time,green production,and human factor indicators[J]. Journal of Cleaner Production,2018,174:560-576.
[7] 牟健慧,郭前建,高亮,等. 基于混合的多目标遗传算法的多目标流水车间逆调度问题求解方法[J]. 机械工程学报,2016,52(22):186-197. MOU Jianhui,GUO Qianjian,GAO Liang,et al. Multi-objective genetic algorithm for solving multi-objective flow-shop inverse scheduling problems[J]. Journal of Mechanical Engineering,2016,52(22):186-197.
[8] NOUIRI M,BEKRAR A,JEMAI A,et al. An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem[J]. Journal of Intelligent Manufacturing,2018,29(3):603-615.
[9] 谢志强. 工件间有约束的复杂产品工序调度研究[D]. 哈尔滨:哈尔滨理工大学,2009. XIE Zhiqiang. Study on operation scheduling of complex product with constraint among jobs[D].Harbin:Harbin University of Science and Technology,2009.
[10] 谢志强,刘胜辉,乔佩利. 基于ACPM和BFSM的动态Job-Shop调度算法[J]. 计算机研究与发展,2003,40(7):977-983. XIE Zhiqiang,LIU Shenghui,QIAO Peili. Dynamic job-shop scheduling algorithm based on ACPM and BFSM[J]. Journal of Computer Research and Development,2003,40(7):977-983.
[11] 谢志强,杨静,周勇,等. 基于工序集的动态关键路径多产品制造调度算法[J]. 计算机学报,2011,34(2):406-412. XIE Zhiqiang,YANG Jing,ZHOU Yong,et al. Dynamic critical paths multi-Product manufacturing scheduling algorithm based on operation set[J]. Chinese Journal of Computers,2011,34(2):406-412.
[12] 谢志强,齐永红,杨静. 存在多设备工序的综合调度算法[J]. 机械工程学报,2014,50(24):191-200. XIE Zhiqiang,QI Yonghong,YANG Jing. Dynamic critical paths multi-Product manufacturing scheduling algorithm based on operation set[J]. Journal of Mechanical Engineering,2014,50(24):191-200.
[13] 谢志强,张晓欢,高一龙,等. 考虑串行工序紧密度的择时综合调度算法[J]. 机械工程学报,2018,54(6):191-202. XIE Zhiqiang ZHANG Xiaohuan GAO Yilong,et al. Time-selective integrated scheduling algorithm considering the compactness of serial processes[J]. Journal of Mechanical Engineering,2018,54(6):191-202.
[14] 谢志强,张晓欢,辛宇,等. 考虑后续工序的择时综合调度算法[J]. 自动化学报,2018,44(2):344-362. XIE Zhiqiang,ZHANG Xiaohuan,XIN Yu,et al. Time-selective integrated scheduling algorithm considering posterior processes[J]. Acta Automatica Sinica,2018,44(2):344-362.
[15] 李志敏. 工序间存在零等待约束的产品加工调度研究[D]. 哈尔滨:哈尔滨理工大学,2009. LI Zhimin. Study on product scheduling problem with no-wait constrains between operations[D].Harbin:Harbin University of Science and Technology,2009.
[16] 谢志强,滕宇峥,杨静. 紧密衔接工序组联动的综合调度算法[J]. 自动化学报,2011,37(3):117-125. XIE Zhiqiang,TENG Yuzheng,YANG Jing.Integrated scheduling algorithm with no-wait constraint operationgroup[J].Acta Automatica Sinica,2011,37(3):117-125.
[17] 谢志强,辛宇,杨静. 基于逆序信号驱动的紧密衔接综合调度算法[J]. 计算机研究与发展,2013,50(8):1710-1721. XIE Zhiqiang,XIN Yu,YANG Jing.No-wait Integrated scheduling algorithm based on reversed order signal-driven[J].Journal of Computer Research and Development,2013,50(8):1710-1721.
[18] XIE Z Q,SU W X,GUO H,et al. The integrated flexible scheduling algorithm of complex product with no-wait constraint between procedures[C]//International Forum on Strategic Technology. IEEE,2017:249-253.
[19] 赵诗奎,韩青,王桂从. 基于虚拟零部件级别分区编码的产品综合调度算法[J]. 计算机集成制造系统,2015,21(9):2435-2445. ZHAO Shikui,HAN Qing,WANG Guicong. Product comprehensive scheduling algorithm based on virtual component level division coding[J]. Computer Integrated Manufacturing Systems,2015,21(9):2435-2445.
[20] 石飞,赵诗奎. 基于工序约束链编码的遗传算法求解产品综合调度问题[J]. 中国机械工程,2017,28(20):2483-2492. SHI Fei,ZHAO Shikui. Product comprehensive scheduling problems solved by genetic algorithm based on operation constraint chain coding[J]. China Mechanical Engineering,2017,28(20):2483-2492.
[21] 张其亮,俞祚明. 基于优势种群的离散果蝇优化算法求解无等待流水车间调度问题[J]. 计算机集成制造系统,2017,23(3):609-615. ZHANG Qiliang,YU Zuoming. Discrete fruit fly optimization algorithm based on dominant population for solving no-wait flow shop scheduling problem[J]. Computer Integrated Manufacturing Systems,2017,23(3):609-615.
[22] 潘全科,王文宏,朱剑英. 解决无等待流水车间调度问题的离散粒子群优化算法[J]. 计算机集成制造系统,2007,13(6):1127-1130. PAN Quanke,WANG Wenhong,ZHU Jianying. Modified discrete particle swarm optimization algorithm for no-wait flow shop problem[J]. Computer Integrated Manufacturing Systems,2007,13(6):1127-1130.
[23] RIAHI V,KAZEMI M. A new hybrid ant colony algorithm for scheduling of no-wait flowshop[J]. Operational Research,2018,18(1):55-74.
[24] BOŻEJKO W,MAKUCHOWSKI M. Solving the no-wait job-shop problem by using genetic algorithm with automatic adjustment[J]. International Journal of Advanced Manufacturing Technology,2011,57(5-8):735-752.
[25] SUNDAR S,SUGANTHAN P N,JIN C T,et al. A hybrid artificial bee colony algorithm for the job-shop scheduling problem with no-wait constraint[J]. Soft Computing,2017,21(5):1193-1202.
[26] PAN J,HUANG H C. A hybrid genetic algorithm for no-wait job shop scheduling problems[J]. Expert Systems with Applications,2009,36(3):5800-5806.
[27] 谢志强,李志敏,郝淑珍,等. 工序间存在零等待约束的复杂产品调度研究[J]. 自动化学报,2009,35(7):983-989. XIE Zhiqiang,LI Zhimin,HAO Shuzhen,et al. Study on complex product scheduling problem with no-wait constraint between operations[J]. Acta Automatica Sinica,2009,35(7):983-989.
[28] 王凌. 车间调度及其遗传算法[M]. 北京:清华大学出版社,2003. WANG Ling. Job shop scheduling and its genetic algorithm[M]. Beijing:Tsinghua University Press,2003.
[29] 苏财茂,柯映林. 面向协同设计的任务规划与解耦策略[J]. 计算机集成制造系统,2006,12(1):21-26. SU Caimao,KE Yinglin. Task planning and decoupling strategy for collaborative design[J]. Computer Integrated Manufacturing Systems,2006,12(1):21-26.
[30] HOU E S H,ANSARI N,REN H. A genetic algorithm for multiprocessor scheduling[J]. IEEE Trans Parallel and Distributed Systems,1994,5(2):113-120.
[31] STEWARD D V. The design structure system:A method for managing the design of complex systems[J]. Engineering Management IEEE Transactions on, 1981, EM-28(3):71-74.
[32] PINEDO M. Scheduling:Theory,algorithms,and systems[M]. 5th ed. Cham Heidelberg:Springer,2015.

基于虚拟零部件的零等待约束复杂产品综合调度算法

Integrated Scheduling Algorithm of Complex Product with No-wait Constraint Based on Virtual Component

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	石琴, 蒋正信, 刘翼闻, 魏宇江, 胡晓松, 贺林. 基于分数阶模型的锂离子电池荷电状态估计[J]. 机械工程学报, 2024, 60(8): 224-232,244.
[2]	王跃飞, 王超, 许于涛, 孙睿, 肖锴, 王凯林. 边-云协同下智能制造单元作业的数字孪生任务调度方法[J]. 机械工程学报, 2024, 60(6): 137-152.
[3]	秦涛, 李运华, 范茹军. 强力摇臂矿用液压挖掘机自主挖掘轨迹优化[J]. 机械工程学报, 2024, 60(18): 374-384.
[4]	刘承尚, 陈锐, 李芳, 王萌, 徐戊矫. 基于改进遗传算法的超高强钢硬化模型参数确定及折弯回弹预测[J]. 机械工程学报, 2024, 60(12): 240-249.
[5]	卢琪, 苏凯新, 张继旺, 闫涛, 杨冰, 张浩楠. 基于BP神经网络和遗传算法的简单链型悬挂接触网结构优化[J]. 机械工程学报, 2024, 60(12): 313-320.
[6]	田志强, 姜兴宇, 杨国哲, 刘伟军, 索英祁, 陈克强, 邢飞. 一种面向航天复杂构件的柔性作业车间能耗优化调度问题研究[J]. 机械工程学报, 2023, 59(8): 273-287.
[7]	刘浩, 陈正颖, 沈楷, 熊旭辉. 基于AC转角变化最小的五轴FDM熔覆路径的法矢量优化技术[J]. 机械工程学报, 2023, 59(6): 272-284.
[8]	苏进展, 李旭东, 尹逊民, 贾海涛, 郭芳. 人字齿轮直线型对角修形设计及成形磨原理[J]. 机械工程学报, 2023, 59(5): 121-129.
[9]	吴宏宇, 牛文栋, 张玉玲, 王树新, 阎绍泽. 水下滑翔机多点探测能耗最低路径的规划方法[J]. 机械工程学报, 2023, 59(5): 156-166.
[10]	李昆鹏, 刘腾博, 李文莉. 改进自适应遗传算法求解“货到人”拣选系统订单分批问题[J]. 机械工程学报, 2023, 59(4): 308-317.
[11]	李贝贝, 孙深圳, 刘秀梅, 刘启航, 刘申, 赵巧, 贺杰. 基于改进SVM算法的调节阀空化状态识别[J]. 机械工程学报, 2023, 59(24): 312-322.
[12]	娄维达, 秦国华, 王华敏, 吴竹溪. 基于复化Cotes积分和神经网络的稳定铣削工艺参数多目标优化方法[J]. 机械工程学报, 2023, 59(17): 279-290.
[13]	郭鑫, 王海涵, 王杰, 张凯, 赵武. 韧性产品交互式概念设计与知识推理方法研究[J]. 机械工程学报, 2023, 59(11): 74-83.
[14]	孙树栋, 周新民, 常昇博. 含私有信息的多代理作业车间协商调度算法[J]. 机械工程学报, 2022, 58(9): 210-217.
[15]	陈晋市, 张淼淼, 毕秋实, 李永奇, 霍东阳, 齐洪阳. 面向自主作业的挖掘机多目标最优挖掘运动规划[J]. 机械工程学报, 2022, 58(7): 237-245.