A Batch Scheduling Method of Flexible Job-Shop with Partially Out-of-Ordered Execute Operation

doi:10.12141/j.issn.1000-565X.230722

Abstract

Abstract:

Actual job-shop scheduling problems often exhibit high complexity, and the scheduling algorithm needs to consider more constraints, so it increases the difficulty of solving the problem. To address the challenge of out-of-order processing for different batches and processes in the flexible job shop’s batch scheduling scenario, it is necessary to overcome the issues related to low utilization rates of existing job shop machines and unbalanced workload distribution among machines of the same type. Therefore, this paper constructed a flexible job shop equal batch scheduling model that incorporates partially out-of-order execution of processes. Firstly, based on the widely adopted fast non-dominated sorting genetic algorithm (NSGA-Ⅱ), this paper introduced a novel two-stage coding structure that integrates batch information and process sorting information. The priority rule method was used to obtain the initial population, and with minimizing the completion time, machine load equilibrium rate and total machine load as the optimization goal, the greedy algorithm was used to obtain the optimal value of the model, and then the processing path of different batches was dynamically constructed.Then, the optimized objective functions were sorted, and the non-dominant sorting process was added step by step to solve the problem that multiple optimized objective functions are difficult to optimize at the same time and improve the solving efficiency. Finally, taking the wood products processing workshop of a printing and packaging enterprise as an example, the scheduling process was realized according to the field operation information. The results show that, compared with the priority scheduling rules, the completion time of the proposed method is shortened by 6.6%, the average machine load balancing variance is reduced by 10.7%, and the average of the proposed method is reduced by 53.3% compared with the genetic algorithm, thus verifying the feasibility of the method. This method can meet the high performance scheduling requirements of the flexible workshop of printing and packaging enterprises.

Key words: out-of-order execute operation, batch scheduling, flexible job-shop, multi-objective optimization, NSGA-Ⅱ

CLC Number:

TP391.41

LIU Ning, HUA Tianbiao, WANG Gao, et al. A Batch Scheduling Method of Flexible Job-Shop with Partially Out-of-Ordered Execute Operation[J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(10): 51-63.

Figures/Tables 15

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Table 1

Fig.6

Table 2

Table 3

Fig.7

Table 4

Table 5

Fig.8

Table 6

Table 7

References 23

1	YI H， QU T， ZHANG K，et al ．Production logistics in industry 3.x：bibliometric analysis，frontier case study，and future directions［J］．Systems，2023，11（7）：371/1-30．
2	LI M， LI M， GUO D，et al ．Real-time data-driven out-of-order synchronization for production and intralogistics in multiresource-constrained assembly systems［J］．IEEE Transactions on Systems，Man，and Cybernetics：Systems，2023，53（12）：7513-7525．
3	BRUCKER P， SCHLIE R ．Job-shop scheduling with multi-purpose machines［J］．Computing，1990，45：369-375．
4	徐本柱，费晓璐，章兴玲．柔性作业车间批量划分与并行调度优化［J］．计算机集成制造系统，2016，22（8）：1953-1964．
	XU Benzhu， FEI Xiaolu， ZHANG Xingling ．Batch division and parallel scheduling optimization of flexible job shop［J］．Computer Integrated Manufacturing System，2016，22（8）：1953-1964．
5	ZHAO B， GAO J， CHEN K，et al ．Two-generation Pareto ant colony algorithm for multi-objective job shop scheduling problem with alternative process plans and unrelated parallel machines［J］．Journal of Intelligent Manufacturing，2018，29（1）：93-108．
6	JAMRUS T， CHIEN C F，GEN M，et al ．Hybrid particle swarm optimization combined with genetic operators for flexible job-shop scheduling under uncertain processing time for semiconductor manufacturing［J］．IEEE Transactions on Semiconductor Manufacturing，2017，31（1）：32-41．
7	SUN K， ZHENG D， SONG H，et al ．Hybrid genetic algorithm with variable neighborhood search for flexible job shop scheduling problem in a machining system［J］．Expert Systems with Applications，2023，215：119359/1-18．
8	LI Y， CHEN X， AN Y，et al ．Integrating machine layout，transporter allocation and worker assignment into job-shop scheduling solved by an improved non-dominated sorting genetic algorithm［J］．Computers & Industrial Engineering，2023，179：109169/1-19．
9	ZHANG F， MEI Y， NGUYEN S，et al ．Multitask multiobjective genetic programming for automated scheduling heuristic learning in dynamic flexible job-shop scheduling［J］．IEEE Transactions on Cybernetics，2023，53（7）：4473-4486．
10	BRAUNE R， BENDA F， DOERNER K F，et al ．A genetic programming learning approach to generate dispatching rules for flexible shop scheduling problems［J］．International Journal of Production Economics，2022，243：108342/1-13．
11	SONG W， CHEN X， LI Q，et al ．Flexible job-shop scheduling via graph neural network and deep reinforcement learning［J］．IEEE Transactions on Industrial Informatics，2022，19（2）：1600-1610．
12	张凯，毕利，焦小刚．集成强化学习算法的柔性作业车间调度问题研究［J］．中国机械工程，2023，34（2）：201-207．
	ZHANG Kai， BI Li， JIAO Xiaogang ．Research on flexible job-shop scheduling problems with integrated reinforcement learning algorithm［J］．China Mechanical Engineering，2023，34（2）：201-207．
13	LI Y， WANG A， ZHANG S ．A batch scheduling technique of flexible job-shop based on improved genetic algorithm［C］∥ Proceedings of 2022 IEEE International Conference on Mechatronics and Automation．Guilin：IEEE，2022：1463-1467．
14	刘雪红，段程，王磊．基于改进候鸟算法的柔性作业车间分批调度问题［J］．计算机集成制造系统，2021，27（11）：3185-3195．
	LIU Xuehong， DUAN Cheng， WANG Lei ．Flexible job shop scheduling with lot streaming based on improved migrating birds optimizetion algorithm［J］．Computer Integrated Manufacturing System，2021，27（11）：3185-3195．
15	闫富乾，陈浩杰，丁国富，等．求解柔性分批调度问题的双层搜索框架入侵杂草算法［J］．计算机集成制造系统，2023，29（2）：556-567．
	YAN Fuqian， CHEN Haojie， DING Guofu，et al ． Improved invasive weed algorithm based on double layer search framework for flexible batch scheduling problem［J］．Computer Integrated Manufacturing System，2023，29（2）：556-567．
16	DEB K， PRATAP A， AGARWAL S，et al ．A fast and elitist multiobjective genetic algorithm：NSGA-Ⅱ［J］．IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197．
17	李树勋，胡迎港，李成，等．基于代理模型的轴流式调节阀阀体型线优化［J］．华南理工大学学报（自然科学版），2023，51（3）：41-52．
	LI Shuxun， HU Yinggang， LI Cheng，et al ．Optimization of body profile line of axial flow control valve based on surrogate model［J］．Journal of South China University of Technology （Natural Science Edition），2023，51（3）：41-52．
18	VERMA S， PANT M， SNASEL V ．A comprehensive review on NSGA-Ⅱ for multi-objective combinatorial optimization problems［J］．IEEE Access，2021，9：57757-57791．
19	郑锦灿，邵立珍，雷雪梅．一种基于改进NSGA-Ⅱ的多目标绿色柔性作业车间调度方法［J］．制造技术与机床，2023（1）：145-152．
	ZHENG Jincan， SHAO Lizhen， LEI Xuemei ．A multi-objective green flexible job shop scheduling method based on improved NSGA-Ⅱ algorithm［J］．Manufacturing Technology & Machine Tool，2023（1）：145-152．
20	尹爱军，闫文涛，张厚望．面向多目标柔性作业车间调度的强化学习NSGA-Ⅱ算法［J］．重庆大学学报， 2022，45（10）：113-123．
	YIN Aijun， YAN Wentao， ZHANG Houwang ． Reinforcement learning NSGA-Ⅱ for multi-objective flexible job shop scheduling［J］．Journal of Chongqing University，2022，45（10）：113-123．
21	王亚昆，刘应波，吴永明，等．改进NSGA-Ⅱ算法求解考虑运输约束的柔性作业车间节能调度问题［J］．计算机集成制造系统，2023，29（9）：3028-3040．
	WANG Yakun， LIU Yingbo， WU Yongming，et al ．Improved NSGA-Ⅱ algorithm to solve energy-saving sche-duling problem of flexible job shop considering transpor-tation constraints［J］．Computer Integrated Manufactu-ring System，2023，29（9）：3028-3040．
22	MA H， ZHANG Y， SUN S，et al ．A comprehensive survey on NSGA-Ⅱ for multi-objective optimization and applications［J］．Artificial Intelligence Review，2023，56：15217-15270．
23	吴秀丽，李雨馨，匡源，等．改进迭代贪婪算法求解可重入流水车间调度问题［J］．计算机集成制造系统，2024，30（7）：2364-2380．
	WU Xiuli， LI Yuxin， KUANG Yuan，et al ．Improved iterative greedy algorithm for reentrant flow shop scheduling problem［J］．Computer Integrated Manufacturing Systems，2024，30（7）：2364-2380．

编号	机器名称	加工工序	辅助时间/min	时产比率
1-10	单头激光切割机	切割、雕刻	10	1
11-21	双头激光切割机	切割、雕刻	15	2
22-24	UV喷墨机	色彩	13	1
25-28	丝印机	丝印、烫金	10	1
29-30	手工包装线	包装	0	1

序号	作业批量/件	初始工序流程	无序工序	工序时产/（件·h^-1）	子批次最小批量/件
1	600	切割-雕刻-丝印、烫金-包装	雕刻、丝印、烫金	30，50，250，500，600	100
2	800	切割-色彩、烫金-包装	色彩、烫金	33，250，300，530	100
3	1 000	切割-雕刻-色彩、烫金-包装	雕刻、色彩、包装	35，60，210，570，500	100
4	1 200	切割-雕刻-色彩、丝印-包装	色彩、丝印	40，55，230，320，500	100

序号	作业批量/件	初始工序流程	无序工序	工序时产/（件·h^-1）	子批次最小批量/件
1	800	切割-雕刻-丝印、烫金-包装	雕刻、丝印、烫金	30，50，250，500，600	50
2	700	切割-色彩、烫金-包装	色彩、烫金	33，250，300，530	60
3	600	切割-雕刻-色彩、烫金-包装	色彩、烫金	35，60，210，570，500	50
4	900	切割-雕刻-色彩、丝印-包装	色彩、丝印	40，55，230，320，500	40
5	1 200	切割-雕刻、丝印、烫金-包装	雕刻、丝印、烫金	32，70，200，580，500	60
6	1 500	切割-色彩、烫金-包装	色彩、烫金	35，240，450，600，560	50
7	1 250	切割-色彩、烫金-包装	色彩、烫金	36，250，620，500	50

运行次数	完工时间/min	机器负载均衡方差	机器总负荷/min	作业分批数	总批次
平均值	879	7 115	13 460	6，8，9，11	25
1	876	8 732	13 460	6，8，10，11	25
2	893	8 625	13 483	6，8，9，11	24
3	893	5 998	13 380	6，8，10，12	26
4	867	8 153	13 350	6，8，9，11	24
5	889	6 723	13 681	6，7，10，12	25
6	859	8 716	13 306	6，7，10，12	25
7	865	5 595	13 441	5，8，10，12	25
8	882	5 996	13 653	6，8，9，11	24
9	893	5 981	13 505	6，8，9，11	24
10	878	6 635	13 341	6，8，10，12	26

算法	完工时间/min	机器负载均衡方差	机器总负荷/min	作业分批数	总批次
FCFS	890	8 916	13 160	6，8，10，12	26
SPT	904	9 115	13 076	6，8，10，12	26
EDD	915	6 782	13 059	6，8，10，12	26
STR	989	9 729	12 912	6，8，10，12	26
GA	840	10 393	13 552	6，8，10，12	26
MNSGA-Ⅱ	879	7 115	13 460	6，8，9，11	25