Robust single machine scheduling problem with uncertain job due dates for industrial mass production

doi:10.23919/JSEE.2020.000012

Journal of Systems Engineering and Electronics ›› 2020, Vol. 31 ›› Issue (2): 350-358.doi: 10.23919/JSEE.2020.000012

收稿日期:2018-09-03 出版日期:2020-04-01 发布日期:2020-04-30

Robust single machine scheduling problem with uncertain job due dates for industrial mass production

Fan YUE^1,²(), Shiji SONG^2,*(), Peng JIA³(), Guangping WU¹(), Han ZHAO^2,⁴()

¹ Department of Automation, Tsinghua University, Beijing 100084, China
² Research Institute of Systems Engineering, Beijing 100072, China
³ Jiuquan Satellite Launch Centre, Jiuquan 735000, China
⁴ Department of Basic Science, Army Logistics Academy, Chongqing 401311, China

Received:2018-09-03 Online:2020-04-01 Published:2020-04-30
Contact: Shiji SONG E-mail:yyff1981@126.com;shijis@mail.tsinghua.edu.cn;jack_1699@sina.com;wgp20121314@163.com;zhao-h15@mails.tsinghua.edu.cn
About author:YUE Fan was born in 1981. She received her Ph.D. degree in control science and engineering with the Department of Automation, Institute of System Integration in Tsinghua University, Beijing, China, in 2019. Her research interests include robust optimization, optimization algorithm, and system optimization. E-mail: yyff1981@126.com|SONG Shiji was born in 1965. He is currently aprofessor with the Department of Automation, Tsinghua University, Beijing, China. His research interests include system modeling, optimization andcontrol, computational intelligence, and pattern recognition.E-mail: shijis@mail.tsinghua.edu.cn|JIA Peng was born in 1980. He received his B.S degree in opto-electronic engineering from Space Engineering University in 2003. He is currently a senior engineer at Jiuquan Satellite Launch Centre. His research interest inclucles application of unmanned aerial vehicle. E-mail: jack_1699@sina.com|WU Guangping was born in 1986. He received his M.S. degree from the Academy of Armored Forces Engineering (AAFE) in 2011. He is currently an engineer at Institute of Systems Engineering. His research interests include signal processing, mechatronics engineering, and equipment demonstration. E-mail: wgp20121314@163.com|ZHAO Han was born in 1982. He received his Ph.D. degree in control science and engineering with the Department of Automation, Institute of System Integration in Tsinghua University. His research interests include supply chain management and optimization approach. E-mail: zhao-h15@mails.tsinghua.edu.cn
Supported by:
the National Natural Science Foundation of China(61503211);the National Natural Science Foundation of China(U1660202);This work is supported by the National Natural Science Foundation of China (61503211; U1660202)

摘要/Abstract

Abstract:

The single machine scheduling problem which involves uncertain job due dates is one of the most important issues in the real make-to-order environment. To deal with the uncertainty, this paper establishes a robust optimization model by minimizing the maximum tardiness in the worst case scenario over all jobs. Unlike the traditional stochastic programming model which requires exact distributions, our model only needs the information of due date intervals. The worst case scenario for a given sequence that belongs to a set containing only $n$ scenarios is proved, where $n$ is the number of jobs. Then, the model is simplified and reformulated as an equivalent mixed 0-1 integer linear programming (MILP) problem. To solve the MILP problems efficiently, a heuristic approach is proposed based on a robust dominance rule. The experimental results show that the proposed method has the advantages of robustness and high calculating efficiency, and it is feasible for large-scale problems.

Key words: robust optimization, single machine scheduling, maximum tardiness, uncertain due date

. [J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 350-358.

Fan YUE, Shiji SONG, Peng JIA, Guangping WU, Han ZHAO. Robust single machine scheduling problem with uncertain job due dates for industrial mass production[J]. Journal of Systems Engineering and Electronics, 2020, 31(2): 350-358.

图/表 5

$c$	$n$	W-$T_{\max}$			Gap /%			CPU time/s
$c$	$n$	$\mbox{RDH}$	$\mbox{VNS}$	$\mbox{CPLEX}$	$\mbox{RDH}$	$\mbox{VNS}$	$\mbox{CPLEX}$	$\mbox{RDH}$	$\mbox{VNS}$	$\mbox{CPLEX}$
2	10	19.36	19.38	$\bf{19.17}$	0.99	1.10	$\bf{0.00}$	$\bf{0.06}$	0.06	24.46
	50	24.49	24.55	$\bf{24.19}$	1.24	1.49	$\bf{0.00}$	$\bf{0.21}$	0.22	137.30
	100	31.64	31.81	$\bf{31.28}$	1.15	1.69	$\bf{0.00}$	$\bf{0.83}$	0.85	845.42
	150	39.17	39.34	$\bf{38.50}$	1.74	2.18	$\bf{0.00}$	$\bf{1.46}$	1.50	1 239.27
	200	$\bf{46.23}$	46.41	48.37	$\bf{0.00}$	0.38	4.63	$\bf{2.10}$	2.18	1 800.00
	250	$\bf{59.66}$	60.02	64.17	$\bf{0.00}$	0.61	7.56	$\bf{2.65}$	2.76	1 800.00
	300	$\bf{70.42}$	70.98	79.65	$\bf{0.00}$	0.80	13.11	$\bf{3.22}$	4.52	1 800.00
	400	$\bf{81.61}$	82.45	-	$\bf{0.00}$	1.03	-	$\bf{3.87}$	5.83	1 800.00
	500	$\bf{93.54}$	94.77	-	$\bf{0.00}$	1.31	-	$\bf{4.33}$	6.45	1 800.00
5	10	16.55	16.61	$\bf{20.49}$	0.98	1.34	$\bf{0.00}$	$\bf{0.06}$	0.06	162.72
	50	23.72	23.85	$\bf{23.48}$	1.02	1.58	$\bf{0.00}$	$\bf{0.22}$	0.23	137.30
	100	29.13	29.26	$\bf{28.77}$	1.25	1.70	$\bf{0.00}$	$\bf{0.95}$	1.05	937.46
	150	36.39	36.51	$\bf{35.81}$	1.62	1.95	$\bf{0.00}$	$\bf{1.74}$	2.01	1 353.61
	200	$\bf{43.76}$	43.96	45.25	$\bf{0.00}$	0.46	3.40	$\bf{2.37}$	3.42	1 800.00
	250	$\bf{56.34}$	56.81	60.72	$\bf{0.00}$	0.83	7.77	$\bf{2.95}$	4.18	1 800.00
	300	$\bf{67.15}$	68.13	75.38	$\bf{0.00}$	1.46	12.26	$\bf{3.57}$	5.02	1 800.00
	400	$\bf{77.28}$	78.56	-	$\bf{0.00}$	1.70	-	$\bf{4.22}$	6.39	1 800.00
	500	$\bf{89.63}$	91.62	-	$\bf{0.00}$	2.22	-	$\bf{4.61}$	7.51	1 800.00
8	10	13.92	13.97	$\bf{13.81}$	0.80	1.16	$\bf{0.00}$	$\bf{0.06}$	0.06	25.39
	50	19.54	19.63	$\bf{19.27}$	1.40	1.87	$\bf{0.00}$	$\bf{0.22}$	0.24	152.47
	100	26.36	26.47	$\bf{25.96}$	1.54	1.96	$\bf{0.00}$	$\bf{1.26}$	1.37	875.25
	150	33.27	33.32	$\bf{32.68}$	1.81	1.95	$\bf{0.00}$	$\bf{1.78}$	2.56	1 299.53
	200	$\bf{40.85}$	41.03	42.66	$\bf{0.00}$	0.44	4.43	$\bf{2.53}$	3.21	1 800.00
	250	$\bf{53.19}$	53.67	57.24	$\bf{0.00}$	0.90	7.61	$\bf{3.24}$	4.09	1 800.00
	300	$\bf{64.35}$	65.25	73.75	$\bf{0.00}$	1.39	14.61	$\bf{3.67}$	5.27	1 800.00
	400	$\bf{75.53}$	76.87	-	$\bf{0.00}$	1.77	-	$\bf{4.15}$	6.93	1 800.00
	500	$\bf{87.79}$	89.91	-	$\bf{0.00}$	2.41	-	$\bf{4.92}$	8.14	1 800.00

参考文献 37

1	PHILIP K. Due date quotation models and algorithms. Scheduling Algorithms Methods & Models, 2005, 11 (3): 187- 204.
2	TANG L, WANG G, LIU J. A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry. Elsevier, Computers & Operations Research, 2007, 34 (10): 3001- 3015.
3	CLAUDE D, DAWID S, BRETT H. Molten metal treatment improvements at JW aluminum used as a method to guarantee metal quality. Light Metals, 2015, 31 (6): 979- 982.
4	MICHAEL P. Single machine models with release dates (stochastic). Scheduling, 2016, 42 (3): 293- 317.
5	CHANG Z, SONG S, ZHANG Y, et al. Distributionally robust single machine scheduling with risk aversion. European Journal of Operational Research, 2017, 256 (1): 261- 274.
6	YU S, FRANK W. Sequencing and scheduling with inaccuratedata. New York: Nova Science Publishers, 2014.
7	ROMAN S, MACIEJ H. Scheduling under fuzziness. Physica-Verlag, 2000, 5 (1): 98- 99.
8	ADAM K, PAWE Z. Robust single machine scheduling problem with weighted number of late jobs criterion. Operations Research Proceedings, 2014, 279- 284.
9	MICHAEL D. Deterministic and stochastic scheduling. Proc. of the NATO Advanced Study and Research Institute on Theoretical Approaches to Scheduling Problems, 2012, 6 (2): 84- 92.
10	ZHANG L, LIN Y, XIAO Y, et al. International journal of machine learning and cybernetics. New York: Springer, 2017.
11	ANDREW D, CHRISTOPHE G, CHRIS B. Slack-based techniques for robust schedules. Proc. of the 6th European Conference on Planning, 2014, 115- 128.
12	XIONG J, XING L, CHEN Y. Robust scheduling for multiobjective flexible job-shop problems with random machine breakdowns. International Journal of Production Economics, 2013, 141 (1): 112- 126. doi: 10.1016/j.ijpe.2012.04.015
13	YUE F, SONG S, ZHANG Y, et al. Single machine scheduling with uncertain release times. Proc. of the 36th Control Conference, 2017, 2729- 2734.
14	RICHARD D, PANAGIOTIS K. Robust scheduling to hedge against processing time uncertainty in single-stage production. Management Science, 1995, 41 (2): 363- 376. doi: 10.1287/mnsc.41.2.363
15	SOTSKOV Y N, LAI T C. Minimizing total weighted flow time under uncertainty using dominance and a stability box. Computers & Operations Research, 2012, 39 (6): 1271- 1289.
16	LAI D, CHYAN T, YU S, et al. The optimality box in uncertain data for minimising the sum of the weighted job completion times. International Journal of Production Research, 2017, 7 (5): 529- 557.
17	JORDI P. The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective. Computers & Operations Research, 2016, 66 (8): 141- 152.
18	MONALDO M, NIKOLAUS M, OLA S. Approximating single machine scheduling with scenarios, 2008, 40(3): 153-164.
19	MOGHADDAM S, KAVEH A, SEYED S, et al. A scenario-based robust optimization approach for batch processing scheduling. Proc. of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 2016, 230 (12): 2286- 2295. doi: 10.1177/0954405415584977
20	CHRISTIAN B, JENS K. Extended GRASP for the job shop scheduling problem with total weighted tardiness objective. European Journal of Operational Research, 2017, 261 (3): 835- 848. doi: 10.1016/j.ejor.2017.03.030
21	XU X, CUI W, LIN J, et al. Robust makespan minimisation in identical parallel machine scheduling problem with interval data. International Journal of Production Research, 2013, 51 (12): 3532- 3548. doi: 10.1080/00207543.2012.751510
22	NING C, YOU F. Adaptive robust optimization with minimax regret criterion: multiobjective optimization framework and computational algorithm for planning and scheduling under uncertainty. Computers & Chemical Engineering, 2017, 108 (5): 425- 447.
23	JAN L, RINNOOY K, PETER B. Complexity of machine scheduling problems. Journal of Scheduling, 1977, 1 (4): 343- 362.
24	KENNETH B, ZAW S. Sequencing with due-dates and early start times to minimize maximum tardiness. Naval Research Logistics, 1974, 21 (1): 171- 176. doi: 10.1002/nav.3800210112
25	HOOGEVEEN J A, VAN DE VELDE S L. A branch-and-bound algorithm for single-machine earliness-tardiness scheduling with idle time. Informs Journal on Computing, 1996, 8 (4): 402- 412. doi: 10.1287/ijoc.8.4.402
26	GHAITH R, MANSOOREH M, GEORGIOS A. A branch-and-bound algorithm for the early/tardy machine scheduling problem with a common due-date and sequence dependent setup time. Computers & Operations Research, 2004, 31 (10): 1727- 1751.
27	ASIYE A, HARUN A, ALI A. Minimising maximum tardiness in assembly flowshops with setup times. International Journal of Production Research, 2017, 16 (11): 25- 37.
28	PARISA A, BARZOKI R. Minimizing sum of the due date assignment costs, maximum tardiness and distribution costs in a supply chain scheduling problem. Applied Soft Computing, 2016, 47 (6): 343- 356.
29	JAFARI A A, LOTFIM M. Single machine scheduling to minimize the maximum tardiness under piecewise linear deteriorating jobs. Scientia Iranica, 2018, 25 (1): 370- 385.
30	MOHAMED A, CROCE D. Complexity of single machine scheduling problems under scenario-based uncertainty. Operations Research Letters, 2008, 36 (3): 338- 342. doi: 10.1016/j.orl.2007.11.005
31	IGOR A. Minmax regret solutions for minimax optimization problems with uncertainty. Operations Research Letters, 2000, 27 (2): 57- 65.
32	EHSAN A, MOSTAFA Z, MOJTABA F, et al. A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms. Computers & Operations Research, 2016, 73 (9): 56- 66.
33	WANG B, WANG X, LAN F, et al. A hybrid local search algorithm for robust job shop scheduling under scenarios. Applied Soft Computing, 2018, 62 (4): 259- 271.
34	NITISH U, ALAN E, MICHEL B. The robust single machine scheduling problem with uncertain release and processing times. Journal of Scheduling, 2014, 34 (15): 149- 163.
35	ARROYO JEC, OTTONI RDS, OLIVEIRAAD P. Multi-objective variable neighborhood search algorithms for a single machine scheduling problem with distinct due windows. Electronic Notes in Theoretical Computer Science, 2011, 281 (1): 5- 19.
36	GUO P, CHEN W, WANG Y. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 10 (4): 1071- 1090.
37	JOAQU P, SANTIAGO P, SILVIA C, et al. Variable neighborhood search with memory for a singlemachine scheduling problem with periodic maintenance and sequence-dependent set-up times. Journal of Scheduling, 2013, 16 (6): 661- 673. doi: 10.1007/s10951-012-0280-2

$n$	$ {\rm{W}} - {T_{{\rm{max}}}}(\hat{\boldsymbol{x}})$	${\rm{W}} - {T_{{\rm{max}}}}(\boldsymbol{x}^*)$	$\mbox{DEV} $	$\mbox{R-DEV}/\%$
10	25.42	$\bf{19.36}$	6.06	31.30
50	32.73	$\bf{24.49}$	8.24	33.65
100	41.59	$\bf{31.64}$	9.95	31.45
150	49.82	$\bf{39.17}$	10.65	27.19
200	59.47	$\bf{46.23}$	13.24	28.64
250	76.31	$\bf{59.66}$	16.65	27.91
300	85.94	$\bf{70.24}$	15.52	22.04
400	98.25	$\bf{81.61}$	16.64	20.39
500	111.31	$\bf{93.54}$	17.77	19.00

Distribution	${\rm{W}} - {T_{{\rm{max}}}}(\hat{\boldsymbol{x}})$	${\rm{W}} - {T_{{\rm{max}}}}(\boldsymbol{x}^*)$	$\mbox{SD}(\hat{\boldsymbol{x}})$	$\mbox{SD}(\boldsymbol{x}^*)$	${\rm{R - DE}}{{\rm{V}}_1}/\% $	${\rm{R - DE}}{{\rm{V}}_2}/\% $
Uniform	21.37	$\bf{20.52}$	3.47	$\bf{2.52}$	4.09	27.38
Normal	21.44	$\bf{19.32}$	3.59	$\bf{2.28}$	6.26	36.49
Poisson	20.91	$\bf{19.96}$	3.25	$\bf{2.24}$	4.76	31.08
Geometric	25.26	$\bf{23.77}$	4.32	$\bf{2.77}$	5.97	35.87

Robust single machine scheduling problem with uncertain job due dates for industrial mass production

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 37

相关文章 0

编辑推荐

Metrics

本文评价