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

doi:10.3901/JME.2020.04.246

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

CLC Number:

TP278

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.

References

[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.