Simulation-Based Adaptive Dynamic Scheduling for Bi-objective Parallel Multi-processor Open Shop

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

Abstract

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

CLC Number:

TP391.9

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.

Figures/Tables 11

Table 1

Parameter and variable definition

参数		变量定义
符号	$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

Table 1

Fig. 1

Fig. 2

Fig. 3

Table 2

Data information of 20 jobs with 4 procedures

工件	到达时间	加工时间
工件	到达时间	工序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

Table 2

Table 3

Table 4

Experimental results of independent solution density

工件数量	$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)

Table 4

Fig. 4

Table 5

Experimental results of real-time dynamic scheduling and hybrid dynamic scheduling

工件数量	动态调度方案		$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

Table 5

Table 6

Deviation degree data in each scheduling period of different hybrid dynamic scheduling

工件数量	调度期间	自适应周期+ 紧急工件驱动		固定周期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

Table 6

Fig. 5

References 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]	Aibin Chen, Fubo Ding, Guoxiong Zhou, Bo Zhou. Simulation Model of Forest Fire Spread Based on Swarm Intelligence [J]. Journal of System Simulation, 2022, 34(7): 1439-1448.
[2]	Yejian Zhao, Yanhong Wang, Jun Zhang, Hongxia Yu, Zhongda Tian. Application of Improved Q Learning Algorithm in Job Shop Scheduling Problem [J]. Journal of System Simulation, 2022, 34(6): 1247-1258.
[3]	Hongwei Wang, Peng Yang. Research on Optimization of Airport Cargo Business Based on Deep Reinforcement Learning [J]. Journal of System Simulation, 2022, 34(3): 651-660.
[4]	Boyuan Zhang, Guanghong Gong, Ze Wang, Ni Li. Research on Parameter Construction Method of Blue Army Equipment Model Based on a Deep Network [J]. Journal of System Simulation, 2022, 34(12): 2629-2638.
[5]	Zhang Luan, Luo Zhengjun, Zhou Dequn. Agent- based Research on Power Absorption Simulation Analysis of Renewable Energy [J]. Journal of System Simulation, 2022, 34(1): 170-178.
[6]	Fatang Chen, Hebin Li, Zhihao Zhang, Zhiqiang Mei. Relative-Residual-Based Dynamic Schedule for Decoding of LDPC Codes [J]. Journal of System Simulation, 2022, 34(09): 1968-1975.
[7]	Li Rongqiang, Wen Aibing, Hua Bin, Li Jiajun, Jiang Bing. Rapid Development Technology of Virtual Maintenance Training Simulation Model for Aviation Equipment [J]. Journal of System Simulation, 2021, 33(5): 1167-1176.
[8]	Li Xiao, Li Shu, Peng Weihong, Guan Ting. Modeling and Simulation of Urination Assist System Based on Working Medium Saturated Vapor Pressure [J]. Journal of System Simulation, 2021, 33(4): 927-934.
[9]	Ma Wenxin, Li Ruimin. Research on Detection Data Driven Calibration Method of Traffic Simulation Parameters [J]. Journal of System Simulation, 2021, 33(12): 2808-2819.
[10]	Liang Feng, Zhang Zhili, Li Xiangyang, Li Yihao, Wang Bei, Long Yong. Research on Semi-physical Simulation Model of Special Vehicle Cockpit with Force Feedback [J]. Journal of System Simulation, 2021, 33(12): 2935-2943.
[11]	Zhu Feng, Yao Yiping, Tang Wenjie, Li Jin. Reusability Analysis and Application for Complex System Simulation Model [J]. Journal of System Simulation, 2021, 33(10): 2356-2362.
[12]	Fu Jianlin, Zhang Hengzhi, Zhang Jian, Jiang Liangkui. Review on AGV Scheduling Optimization [J]. Journal of System Simulation, 2020, 32(9): 1664-1675.
[13]	Zhang Yunrong, Zhang Zhili, Li XiangYang, Wang Hongguang, Mi Wenpeng, Kong Xiangtong, Liu Pengpeng. Simulation Research on Cooperative Control of Multi Intelligent Ground Platform Based on Agent Theory [J]. Journal of System Simulation, 2020, 32(7): 1211-1219.
[14]	Hu Chunsheng, Xu Chengdong, Zhang Penfei. One design mode of highly configurable modular simulation system [J]. Journal of System Simulation, 2020, 32(4): 627-637.
[15]	Wang Yan, Ding Yu. Optimal Scheduling and Decision Making Method for Dynamic Flexible Job Shop [J]. Journal of System Simulation, 2020, 32(11): 2073-2083.