面向部分工序无序加工的柔性作业车间批量调度方法

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

华南理工大学学报(自然科学版) ›› 2024, Vol. 52 ›› Issue (10): 51-63.doi: 10.12141/j.issn.1000-565X.230722

面向部分工序无序加工的柔性作业车间批量调度方法

柳宁¹^,²(), 华天标¹, 王高¹, 陈法明¹()

^1.暨南大学信息科学技术学院，广东广州 510632
^2.暨南大学智能科学与工程学院，广东珠海 519070

收稿日期:2023-11-22 出版日期:2024-10-25 发布日期:2024-02-09
通信作者: 陈法明（1986—），男，实验师，主要从事嵌入式智能控制、车间建模与可视化研究。 E-mail:fmchen@jnu.edu.cn
作者简介:柳宁（1963—），男，博士，教授，主要从事智能制造、车间建模与调度、机器人研究。E-mail：tliuning@jnu.edu.cn
基金资助:
国家自然科学基金面上项目(62172188);珠海市科技计划项目(2220004002542)

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

LIU Ning¹^,²(), HUA Tianbiao¹, WANG Gao¹, CHEN Faming¹()

^1.College of Information Science and Technology, Jinan University, Guangzhou 510632, Guangdong, China
^2.School of Intelligent Systems Science and Engineering, Jinan University, Zhuhai 519070, Guangdong, China

Received:2023-11-22 Online:2024-10-25 Published:2024-02-09
Contact: 陈法明（1986—），男，实验师，主要从事嵌入式智能控制、车间建模与可视化研究。 E-mail:fmchen@jnu.edu.cn
About author:柳宁（1963—），男，博士，教授，主要从事智能制造、车间建模与调度、机器人研究。E-mail：tliuning@jnu.edu.cn
Supported by:
the General Program of the National Natural Science Foundation of China(62172188)

摘要/Abstract

摘要：

实际的车间调度问题往往具有更高的复杂度，调度算法需要考虑更多的约束条件，因此增加了问题的求解难度。为解决柔性作业车间批量调度场景中不同批次、不同工序之间可以无序加工的难题，进而突破现有车间机器使用率低、同类型机器负载不均衡的难点，文中构建了一种面向部分工序无序加工的柔性作业车间等量分批调度模型。首先，基于广泛使用的快速非支配排序遗传算法（NSGA-Ⅱ），提出了一种融合批次、批量和工序排序信息的两段编码结构，采用优先级规则方法获得初始种群，并以最小化完工时间、机器负载均衡率、机器总负荷为优化目标，采用贪心算法求解模型最优值，进而动态构建不同批次的加工路径；然后，对优化目标函数进行排序，再逐步加入非支配排序过程，以解决多个优化目标函数之间难以同时优化的问题，提高求解效率；最后，以某印刷包装企业的木制品加工车间为例，面向现场作业信息，采用仿真手段实现调度过程。结果表明，与优先级调度规则相比，文中所提方法的完工时间平均缩短了6.6%、机器负载均衡方差平均减小了10.7%，文中所提方法的机器负载均衡方差比遗传算法平均减小了53.3%，从而验证了文中方法的可行性，且该方法可以满足印刷包装企业柔性作业车间的高性能调度需求。

关键词: 工序无序加工, 批量划分, 柔性作业车间, 多目标优化, NSGA-Ⅱ

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-Ⅱ

中图分类号:

TP391.41

柳宁, 华天标, 王高, 等. 面向部分工序无序加工的柔性作业车间批量调度方法[J]. 华南理工大学学报(自然科学版), 2024, 52(10): 51-63.

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.

图/表 15

图1

图2

图3

图4

图5

表1

图6

表2

表3

图7

表4

表5

图8

表6

表7

参考文献 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

面向部分工序无序加工的柔性作业车间批量调度方法

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 23

相关文章 15

编辑推荐

Metrics

本文评价

MNSGA-Ⅱ	完工时间/min	机器负载均衡方差	机器总负载/min	作业分批数	总批次
平均值	1 366	2 368	25 122	15，9，10，19，19，27，18	116
1	1 346	3 216	25 023	16，12，6，18，19，28，11	110
2	1 362	1 017	25 502	16，10，12，21，14，29，25	127
3	1 379	2 441	25 440	16，10，12，14，14，29，25	120
4	1 397	1 760	25 183	16，9，12，20，30，25，18	114
5	1 393	2 543	25 380	15，11，8，20，19，19，19	111
6	1 372	3 742	24 619	16，8，8，19，18，28，11	108
7	1 348	2 869	24 863	15，10，12，13，20，29，15	114
8	1 330	2 061	25 080	15，8，10，21，19，29，25	127
9	1 363	3 258	25 134	7，11，10，22，20，27，14	111
10	1 365	777	24 995	13，10，5，20，19，30，22	119

算法	完工时间/min	机器负载均衡方差	机器总负荷/min	作业分批数	总批次
FCFS	1 420	1 832	23 840	16，12，12，23，20，30，25	138
SPT	1 515	4 697	23 838	16，12，12，23，20，30，25	138
EDD	1 441	2 006	24 284	16，12，12，23，20，30，25	138
STR	1 476	2 067	23 841	16，12，12，23，20，30，25	138
GA	1 347	5 096	24 608	16，12，4，10，21，31，12	106
MNSGA-Ⅱ	1 366	2 368	25 122	15，9，10，19，19，27，18	116

[1]	张跃明, 李天宇, 纪姝婷. 摆线针轮减速机参数对传动效率的影响与参数优化[J]. 华南理工大学学报(自然科学版), 2024, 52(4): 77-87.
[2]	唐进君, 任茂昕, 李志涛, 等. 基于代理模型辅助NSGA-II算法的地铁接驳公交优化[J]. 华南理工大学学报(自然科学版), 2024, 52(11): 95-105.
[3]	王学武, 方俊宇, 高进, 等. 基于改善解集分布性的多目标优化[J]. 华南理工大学学报(自然科学版), 2023, 51(8): 137-148.
[4]	李树勋, 胡迎港, 李成, 等. 基于代理模型的轴流式调节阀阀体型线优化[J]. 华南理工大学学报(自然科学版), 2023, 51(3): 41-52.
[5]	刘国勇, 张文鹏, 张铜鑫, 等. 大幅面SLM成型仓结构优化及其流场特性[J]. 华南理工大学学报(自然科学版), 2023, 51(12): 53-63.
[6]	赵克刚, 何坤阳, 黎杰, 等. 基于改进动态规划法的HEV多目标能量管理策略[J]. 华南理工大学学报(自然科学版), 2022, 50(9): 138-148.
[7]	蒋涛, 路洲. 高架铁路客运站平天窗的多目标优化[J]. 华南理工大学学报(自然科学版), 2022, 50(7): 13-24.
[8]	魏润斌, 贾顺平, 童瑞咏, 等. 一般树型线条件下的列车开行方案优化研究[J]. 华南理工大学学报(自然科学版), 2022, 50(11): 44-51.
[9]	刘汉武, 雷雨龙, 付尧, 等. 基于多目标优化的增程式电动汽车自适应制动回馈控制策略[J]. 华南理工大学学报（自然科学版）, 2021, 49(7): 42-50,65.
[10]	金霞, 胡俊聪, 王威, 等. 虚拟环境下汽车引擎盖的匹配调整策略[J]. 华南理工大学学报（自然科学版）, 2020, 48(6): 87-96.
[11]	姚恩建张金萌郇宁. 效率与公平导向下城轨大小交路开行方案优化[J]. 华南理工大学学报（自然科学版）, 2020, 48(5): 41-48,57.
[12]	吴迪刘立李晓俊刘丛红. 基于多目标优化的被动式低能耗建筑技术研究 ———以寒冷地区居住建筑为例 [J]. 华南理工大学学报（自然科学版）, 2018, 46(4): 98-104,120.
[13]	白中浩何成朱峰. 复合材料三明治结构板的电磁和冲击性能分析[J]. 华南理工大学学报（自然科学版）, 2016, 44(9): 137-143.
[14]	翟振坤李迪. 基于多目标优化的数控实时任务参数选择方法[J]. 华南理工大学学报（自然科学版）, 2016, 44(3): 23-28.
[15]	邓卓明刘明波. 求解多目标暂态电压紧急控制的强化学习方法[J]. 华南理工大学学报（自然科学版）, 2015, 43(12): 9-17.