基于仿真的双目标并行机开放车间自适应动态调度

doi:10.16182/j.issn1004731x.joss.21-0697

摘要/Abstract

摘要：

针对工件到达时间与加工时间不确定，且存在紧急工件的并行机开放车间调度问题，以TWC(total weighted completion time)与TWT(total weighted tardiness)为优化目标，设计了一种集成FlexSim仿真模型与NSGA-Ⅱ算法的自适应动态调度方法。该方法以FlexSim模型仿真工件的生成和加工为基础，根据车间实时负荷确定动态调度周期，对紧急工件进行右移重调度，利用NSGA-Ⅱ算法生成双目标优化的调度方案。某晶粒拣选车间生产数据的实验结果表明，相较于利用规则的实时动态调度与固定周期重调度，提出的方法能够在最小化调度偏离度的同时获得满意解。

关键词: 并行机开放车间, NSGA-Ⅱ算法, 动态调度, 工件随机到达, 仿真模型

Abstract:

Aiming at the parallel multi-processor open shop scheduling problem with uncertain job's release time,processing time and urgent jobs, an adaptive dynamic method integrating FlexSim simulation model and NSGA-Ⅱ algorithm is designed to optimize the bi-objectives of TWC(total weighted completion time) and TWT(total weighted tardiness). By using the FlexSim simulation model, this method determines the adaptive scheduling cycle according to the dynamic workload of the open shop, and conducts right-shift rescheduling to the urgent jobs. NSGA-Ⅱ algorithm is used to generate the bi-objective optimization scheduling scheme. Experimental results of a grain sorting shop show that compared with the rule-based real-time dynamic scheduling and periodic rescheduling, the proposed method can obtain a satisfactory solution while minimizing the deviation degree between the dynamic scheduling and the original scheduling.

Key words: Parallel multi-processor open shop, NSGA-Ⅱ algorithm, dynamic scheduling, random release time of the job, simulation model

中图分类号:

TP391.9

陈亚绒, 管舒晨, 黄成军, 朱立夏, 周富得. 基于仿真的双目标并行机开放车间自适应动态调度[J]. 系统仿真学报, 2023, 35(1): 69-81.

Yarong Chen, Shuchen Guan, Chengjun Huang, Lixia Zhu, Chou FuhDer. Simulation-Based Adaptive Dynamic Scheduling for Bi-objective Parallel Multi-processor Open Shop[J]. Journal of System Simulation, 2023, 35(1): 69-81.

图/表 11

表1

参数与变量定义

参数		变量定义
符号	$n$	工件数
	$m$	阶段/工序数
	$i, g$	工件序号
	$j, l$	阶段/工序序号
	$k$	阶段/工序中并行机的序号
集合	$S$	阶段/工序集 $S = {s 1, ⋯, s j, ⋯, s m}$
集合	$J$	工件集 $J = {J 1, ⋯, J i, ⋯, J n}$
参数	$N j$	工序 $j$ 的机器数
	$m j k$	机器集 $S$ 中可以加工第 $j$ 工序的第 $k$ 台并行机 $(k = 1,2, ⋯, N j)$
	$r i, w i, d i, C i, T i$	工件 $J i$ 的到达时间，权重，交期，完工时间与拖期时间
	$p i j, c i j$	工件 $J i$ 在工序 $s j$ 的加工时间，完工时间
	$M$	足够大的整数，设置 $M = ∑ i = 1 n ∑ j = 1 m p i j + m n$
决策变量	$X i j k$	工件 $J i$ 是否在工序 $j$ 机器 $m j k$ 上加工，是为1，否则为0
	$Y i j l$	工件 $J i$ 的工序 $j$ 是否在工序 $l$ 之前加工，是为1，否则为0
	$Z i g j k$	工序 $j$ 的机器 $m j k$ 上工件 $J i$ 是否在工件 $J g$ 前加工，是为1，否则为0

表1

图1

图2

图3

表2

20工件4工序的数据信息表

工件	到达时间	加工时间
工件	到达时间	工序1	工序2	工序3	工序4
$J 1$	0	8	3	9	6
$J 2$	0	9	3	7	6
$J 3$	0	8	2	9	4
$J 4$	0	7	4	7	3
$J 5$	0	8	2	7	5
$J 6$	4	8	3	7	6
$J 7$	6	6	2	8	5
$J 8$	7	9	3	9	6
$J 9$	10	6	3	9	5
$J 10$	14	9	4	7	2
$J 11$	19	7	2	7	3
$J 12$	21	7	3	9	3
$J 13$	26	7	4	8	4
$J 14$	31	7	4	7	3
$J 15$	34	9	2	8	2
$J 16$	39	6	3	7	2
$J 17$	43	8	2	8	4
$J 18$	45	6	4	7	3
$J 19$	48	8	4	8	2
$J 20$	51	7	3	9	6

表2

表3

表4

独立解密度的实验结果

工件数量	$d w *$	运行时间/s	迭代次数	目标值(TWC, TWT)
10	0.45	131	24	(856, 35), (874, 30), (886, 27), (895, 22)
	0.50	236	35	(836, 26), (847, 19), (862, 18), (888, 17), (890, 15)
	0.55	253	52	(870, 31), (877, 26), (913, 22), (940, 21), (969, 14)
	0.60	296	55	(864, 23), (867, 22), (886, 20)
20	0.45	1 315	45	(2 646, 214), (2 594, 221), (2 573, 227)
	0.50	1 441	53	(2 574, 211), (2 583, 210), (2 592, 209)
	0.55	2 230	65	(2 529, 191), (2 517, 208), (2 508, 216), (2 471, 221)
	0.60	2 751	80	(2 566, 198), (2 546, 201), (2 532, 207), (2 507, 210)
30	0.45	1 502	46	(6 302, 841), (6 358, 827), (6 377, 815), (6 384, 804)
	0.50	1 648	54	(6 265, 872), (6 362, 820), (6 378, 816)
	0.55	1 680	59	(6 210, 829), (6 271, 818), (6 342, 815), (6 396, 809)
	0.60	1 824	68	(6 337, 856), (6 354, 844), (6 386, 828)

表4

图4

表5

在线实时调度与混合动态调度方案的实验结果

工件数量	动态调度方案		$d O$	$d M$	目标值 (TWC, TWT)	动态调度次数	模型运行时间/s
10	实时动态调度	WSPT+LALF			(750, 5)		48
		WSPT+FA			(831, 13)		52
		EDD+LALF			(790, 24)		49
		EDD+FA			(799, 0)		52
	混合动态调度	自适应周期+紧急工件驱动	316	20	(713, 0)	3	55
		固定周期10+紧急工件驱动	594	51	(815, 14)	4	60
		固定周期30+紧急工件驱动	403	27	(763, 10)	3	79
20	实时动态调度	WSPT+LALF			(2 854, 212)		86
		WSPT+FA			(2 965, 242)		86
		EDD+LALF			(2 860, 128)		93
		EDD+FA			(2 800, 130)		85
	混合动态调度	自适应周期+紧急工件驱动	401	70	(2 890, 118)	6	96
		固定周期10+紧急工件驱动	954	149	(2 971, 121)	9	97
		固定周期30+紧急工件驱动	797	75	(3 035, 172)	5	101
30	实时动态调度	WSPT+LALF			(5 990, 806)		130
		WSPT+FA			(6 128, 789)		133
		EDD+LALF			(5 850, 430)		127
		EDD+FA			(5 829, 428)		130
	混合动态调度	自适应周期+紧急工件驱动	371	38	(6 088, 413)	7	140
		固定周期10+紧急工件驱动	1407	136	(6 263, 572)	12	143
		固定周期30+紧急工件驱动	885	67	(6 361, 776)	6	147

表5

表6

不同混合动态调度方案调度期间的偏离度数据

工件数量	调度期间	自适应周期+ 紧急工件驱动		固定周期10+ 紧急工件驱动		固定周期30+ 紧急工件驱动		工件数量	调度期间	自适应周期+ 紧急工件驱动		固定周期10+ 紧急工件驱动		固定周期30+ 紧急工件驱动
工件数量	调度期间	$d O$	$d M$	$d O$	$d M$	$d O$	$d M$	工件数量	调度期间	$d O$	$d M$	$d O$	$d M$	$d O$	$d M$
10	1	0	0	0	0	0	0	30	1	0	0	0	0	0	0
	2	106	8	139	6	139	6		2	27	4	30	4	0	0
	3	210	12	264	21	264	21		3	30	11	25	1	175	21
	4			191	24				4	175	11	19	8	578	19
20	1	0	0	0	0	0	0		5	26	3	108	14	129	22
	2	9	2	39	8	0	0		6	24	2	102	13	3	5
	3	157	17	75	12	110	20		7	89	7	145	14
	4	129	21	107	19	249	18		8			15	21
	5	90	14	128	19	438	37		9			83	12
	6	16	16	158	21				10			336	19
	7			62	15				11			407	22
	8			165	28				12			137	8
	9			220	27

表6

图5

参考文献 29

1	陈亚绒, 黄佩钰, 李沛, 等. 并行多机开放车间调度问题的模型与算法[J]. 中国机械工程, 2018, 29(22): 2666-2673, 2681.
	Chen Yarong, Huang Peiyu, Li Pei, et al. Model and Algorithm of Parallel Multi-processor Open Shop Scheduling Problem[J]. China Mechanical Engineering, 2018, 29(22): 2666-2673, 2681.
2	Naderi B, Fatemi Ghomi S M T, Aminnayeri M, et al. A Study on Open Shop Scheduling to Minimise Total Tardiness[J]. International Journal of Production Research (S0020-7543), 2011, 49(15): 4657-4678.
3	Bräsel H, Herms A, Mőrig M, et al. Heuristic Constructive Algorithms for Open Shop Scheduling to Minimize Mean Flow Time[J]. European Journal of Operational Research (S0377-2217), 2008, 189(3): 856-870.
4	王军强, 郭银洲, 崔福东, 等. 基于多样性增强的自适应遗传算法的开放式车间调度优化[J]. 计算机集成制造系统, 2014, 20(10): 2479-2493.
	Wang Junqiang, Guo Yinzhou, Cui Fudong, et al.Diversity Enhancement-based Adaptive Genetic Algorithm for Open-shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2014,20(10): 2479-2493.
5	Abreu L R, Cunha J O, Prata B A, et al. A Genetic Algorithm for Scheduling Open Shops with Sequence-dependent Setup Times[J]. Computers & Operations Research (S0305-0548), 2020, 113: 104793.
6	高亮, 高海兵, 周驰. 基于粒子群优化的开放式车间调度[J]. 机械工程学报, 2006, 42(2): 129-134.
	Gao Liang, Gao Haibing, Zhou Chi. PSO Based Scheduling Algorithm for Open Shop Scheduling Problem[J]. Chinses Journal of Mechanical Engineering, 2006, 42(2): 129-134.
7	Sha D Y, Hsu C-Y. A New Particle Swarm Optimization for the Open Shop Scheduling Problem[J]. Computers & Operations Research (S0305-0548), 2008, 35(10): 3243-3261.
8	Jolai F, Goldansaz S M, Zahedi-Anaraki A. Simulated Annealing and Imperialist Competitive Algorithm for Minimising Makespan in An Open Shop[J]. International Journal of Operational Research (S1745-7645), 2013, 17(3): 275-294.
9	Panahi H, Tavakkoli-Moghaddam R. Solving a Multi-objective Open Shop Scheduling Problem by A Novel Hybrid Ant Colony Optimization[J]. Expert Systems with Applications (S0957-4174), 2011, 38(3): 2817-2822.
10	Uhlmann I R, Frazzon E M. Production Rescheduling Review: Opportunities for Industrial Integration and Practical Applications[J]. Journal of Manufacturing Systems (S0278-6125), 2018, 49: 186-193.
11	Ghaleb M, Zolfagharinia H, Taghipour S. Real-time Production Scheduling in the Industry-4.0 Context: Addressing Uncertainties in Job Arrivals and Machine Breakdowns[J]. Computers & Operations Research(S0305-0548), 2020, 123: 105031.
12	张苏雨, 王艳, 纪志成. 基于超启发式遗传规划的动态车间调度方法[J]. 系统仿真学报, 2020, 32(12): 210-222.
	Zhang Suyu, Wang Yan, Ji Zhicheng.Automatic Discovery Method of Dynamic Job Shop Dispatching Rules Based on Hyper-Heuristic Genetic Programming[J]. Journal of System Simulation, 2020, 32(12): 210-222.
13	唐秋华, 陈世杰, 赵萌, 等. 机器故障下加工车间优化重调度方式预测[J].中国机械工程, 2019, 30(2): 188-195.
	Tang Qiuhua, Chen Shijie, Zhao Meng, et al. Prediction of Optimal Rescheduling Mode under Machine Failures within Job Shops[J]. China Mechanical Engineering, 2019, 30(2): 188-195.
14	顾泽平, 杨建军, 周勇. 不确定因素扰动下多目标柔性作业车间鲁棒调度方法[J]. 计算机集成制造系统, 2017, 23(1): 66-74.
	Gu Zeping, Yang Jianjun, Zhou Yong. Multi-objective Flexible Job-shop Robust Scheduling Optimization under Disturbance of Uncertainties[J]. Computer Integrated Manufacturing Systems, 2017, 23(1): 66-74.
15	李聪波, 寇阳, 雷焱绯, 等. 基于动态事件的柔性作业车间重调度节能优化[J]. 计算机集成制造系统, 2020, 26(2): 288-299.
	Li Congbo, Kou Yang, Lei Yanfei, et al. Flexible job Shop Rescheduling Optimization Method for Energy-Saving Based on Dynamic Events[J]. Computer Integrated Manufacturing Systems, 2020, 26(2): 288-299.
16	Li X, Zhao P, Du B, et al. Hybrid Artificial Bee Colony Algorithm with A Rescheduling Strategy for Solving Flexible Job Shop Scheduling Problems[J]. Computers & Industrial Engineering (S0360-8352), 2017, 113:10-26.
17	杨小佳, 刘建军, 陈庆新, 等. 变扰动强度下柔性装配作业车间调度性能分析[J]. 计算机集成制造系统, 2021, 27(3): 800-814.
	Yang Xiaojia, Liu Jianjun, Chen Qingxin, et al. Performance Analysis of Flexible Assembly Job Shop Scheduling under Variable Disturbance Intensity[J]. Computer Integrated Manufacturing Systems, 2021, 27(3): 800-814.
18	Rahmani D, Heydari M. Robust and Stable Flow Shop Scheduling with Unexpected Arrivals of New Jobs and Uncertain Processing Times[J]. Journal of Manufacturing Systems (S0278-6125), 2014, 33(1): 84-92.
19	何小妹, 董绍华. 多目标多约束混合流水车间插单重调度问题研究[J]. 工程科学学报, 2019, 4, 307(11): 93-100.
	He Xiaomei, Dong Shaohua. Research on Rush Order Insertion Rescheduling Problem under Hybrid Flow Shop with Multi-objective and Multi-constraint[J]. Chinese Journal of Engineering, 2019, 4, 307(11): 93-100.
20	Liu L. Outsourcing and Rescheduling for A Two-machine Flow Shop with the Disruption of New Arriving Jobs: A Hybrid Variable Neighborhood Search Algorithm[J]. Computers & Industrial Engineering (S0360-8352), 2019, 130: 198-221.
21	王国新, 宁汝新, 王爱民. 基于仿真的生产调度优化技术研究[J]. 计算机集成制造系统, 2007, 13(7): 1419-1427.
	Wang Guoxin, Ning Ruxin, Wang Aimin. Production Optimal Scheduling Technology based on Simulation[J]. Computer Integrated Manufacturing Systems, 2007, 13(7): 1419-1427.
22	Pfeiffer A, Kádár B, Monostori L, et al. Simulation as One of the Core Technologies for Digital Enterprises: Assessment of Hybrid Rescheduling Methods[J]. International Journal of Computer Integrated Manufacturing (S0951-192X), 2008, 21(2): 206-214.
23	Korytkowski P, Wiśniewski T, Rymaszewski S. An Evolutionary Simulation-based Optimization Approach for Dispatching Scheduling[J]. Simulation Modelling Practice & Theory (S1569-190X), 2013, 35: 69-85.
24	Qiao F, Liu J, Ma Y. Industrial Big-data-driven and CPS-based Adaptive Production Scheduling for Smart Manufacturing[J]. International Journal of Production Research (S0020-7543), 2020, 3: 1-21.
25	Gohareh Morady M, Karimi B, Khademian M. A Simulation-optimization Approach for Open-shop Scheduling Problem with Random Process Times[J]. International Journal of Advanced Manufacturing Technology (S0268-3768), 2014, 70(5-8): 821-831.
26	Nasiri M M, Yazdanparast R, Jolai F. A Simulation Optimisation Approach for Real-time Scheduling in an Open Shop Environment Using a Composite Dispatching Rule[J]. International Journal of Computer Integrated Manufacturing (S0951-192X), 2017, 30(12): 1239-1252.
27	Moratori P, Petrovic S, Vázquez-Rodríguez J A. Match-up Approaches to a Dynamic Rescheduling Problem[J]. International Journal of Production Research (S0020-7543), 2012, 50(1): 261-276.
28	Anand E, Panneerselvam R. A Study of Crossover Operators for Genetic Algorithm and Proposal of a New Crossover Operator to Solve Open Shop Scheduling Problem[J]. American Journal of Industrial & Business Management (S2164-5167), 2016, 6(6): 774-789.
29	朱传军, 邱文, 张超勇, 等. 多目标柔性作业车间稳健性动态调度研究[J]. 中国机械工程, 2017, 28(2): 173-182.
	Zhu Chuanjun, Qiu Wen, Zhang Chaoyong, et al. Multi-objective Flexible Job Shop Dynamic Scheduling Strategy- Aiming at Scheduling Stability and Robustness[J]. China Mechanical Engineering, 2017, 28(2): 173-182.

[1]	陈爱斌, 丁福博, 周国雄, 周波. 基于群体智能的森林火灾蔓延仿真模型[J]. 系统仿真学报, 2022, 34(7): 1439-1448.
[2]	赵也践, 王艳红, 张俊, 于洪霞, 田中大. 改进Q学习算法在作业车间调度问题中的应用[J]. 系统仿真学报, 2022, 34(6): 1247-1258.
[3]	王红微, 杨鹏. 基于深度强化学习的机场货运业务优化研究[J]. 系统仿真学报, 2022, 34(3): 651-660.
[4]	张博远, 龚光红, 王泽, 李妮. 基于深度网络的蓝军装备模型参数生成方法研究[J]. 系统仿真学报, 2022, 34(12): 2629-2638.
[5]	陈发堂, 李贺宾, 张志豪, 梅志强. 基于相对残差的LDPC码动态调度译码算法[J]. 系统仿真学报, 2022, 34(09): 1968-1975.
[6]	李荣强, 文爱兵, 花斌, 李嘉骏, 姜兵. 航空装备虚拟维修训练仿真模型快速开发技术[J]. 系统仿真学报, 2021, 33(5): 1167-1176.
[7]	李笑, 李树, 彭伟鸿, 关婷. 基于工质饱和蒸汽压的排尿助力系统建模仿真[J]. 系统仿真学报, 2021, 33(4): 927-934.
[8]	马文欣, 李瑞敏. 检测数据驱动的交通仿真参数标定方法研究[J]. 系统仿真学报, 2021, 33(12): 2808-2819.
[9]	梁丰, 张志利, 李向阳, 李亦豪, 王蓓, 龙勇. 力反馈特种车辆驾驶舱半实物仿真模型研究[J]. 系统仿真学报, 2021, 33(12): 2935-2943.
[10]	朱峰, 姚益平, 唐文杰, 李进. 复杂系统仿真模型可重用性分析与应用[J]. 系统仿真学报, 2021, 33(10): 2356-2362.
[11]	付建林, 张恒志, 张剑, 姜良奎. 自动导引车调度优化研究综述[J]. 系统仿真学报, 2020, 32(9): 1664-1675.
[12]	张云荣, 张志利, 李向阳, 王红光, 米文鹏, 孔祥通, 刘朋朋. 基于Agent理论的多无人地面平台协同控制仿真研究[J]. 系统仿真学报, 2020, 32(7): 1211-1219.
[13]	胡春生, 许承东, 张鹏飞. 一种高度可配置的模块化仿真系统设计模式[J]. 系统仿真学报, 2020, 32(4): 627-637.
[14]	王艳, 丁宇. 动态柔性作业车间优化调度与决策方法[J]. 系统仿真学报, 2020, 32(11): 2073-2083.
[15]	田琼, 张竞涛. 打车软件服务下出租车市场模型与仿真[J]. 系统仿真学报, 2019, 31(3): 393-402.