A Single Machine Scheduling Problem Considering Machine Availability Constraints

doi:10.16183/j.cnki.jsjtu.2019.173

Abstract

Abstract:

The study described in this paper is derived from a real rotor production workshop where low reliability leads to poor quality of workpieces. A single machine scheduling problem considering machine availability constraints is addressed. The availability is defined by the machine reliability, which can be restored by preventive maintenance. Preventive maintenance with different improvement factors is defined in the mathematical model to minimize the total tardiness. A genetic algorithm is designed to solve the problem. Numerical results show that the proposed approach can effectively deal with the impact of machine availability constraints on production scheduling. Sensitivity analyses provide valuable managerial insights for real workshop scheduling.

Key words: single machine scheduling, availability, preventive maintenance, total tardiness, genetic algorithm

CLC Number:

F406.2

WANG Jinfeng, CHEN Lu, YANG Wenhui. A Single Machine Scheduling Problem Considering Machine Availability Constraints[J]. Journal of Shanghai Jiao Tong University, 2021, 55(1): 103-110.

Figures/Tables 9

Fig.1

Fig.2

Fig.3

Tab.1

Tab.2

Fig.4

Fig.5

Fig.6

Fig.7

References 19

[1]	YU X Y, ZHANG Y L, STEINER G. Single-machine scheduling with periodic maintenance to minimize makespan revisited[J]. Journal of Scheduling, 2014, 17(3): 263-270.
[2]	蒋凯丽，陆志强，崔维伟. 考虑周期预防性维护的两阶段混合流水线调度[J]. 计算机集成制造系统，2017, 23(3): 616-623.
	JIANG Kaili, LU Zhiqiang, CUI Weiwei. Two-stage hybrid flow shop scheduling with periodic preventive maintenance[J]. Computer Integrated Manufacturing Systems, 2017, 23(3): 616-623.
[3]	SALMASNIA A, MIRABADI-DASTJERD D. Joint production and preventive maintenance scheduling for a single degraded machine by considering machine failures[J]. TOP, 2017, 25(3): 544-578.
[4]	DIEULLE L, BÉRENGUER C, GRALL A, et al. Sequential condition-based maintenance scheduling for a deteriorating system[J]. European Journal of Operational Research, 2003, 150(2): 451-461.
[5]	PANDEY D, KULKARNI M S, VRAT P. A methodology for joint optimization for maintenance planning, process quality and production scheduling[J]. Computers & Industrial Engineering, 2011, 61(4): 1098-1106.
[6]	LIU Q M, DONG M, CHEN F F, et al. Single-machine-based joint optimization of predictive maintenance planning and production scheduling[J]. Robotics and Computer-Integrated Manufacturing, 2019, 55: 173-182.
[7]	陶辛阳，夏唐斌，奚立峰. 基于健康指数的预防性维护与多目标生产调度联合优化建模[J]. 上海交通大学学报，2014, 48(8): 1170-1174.
	TAO Xinyang, XIA Tangbin, XI Lifeng. Health-index-based joint optimization of preventive maintenance and multi-attribute production scheduling[J]. Journal of Shanghai Jiao Tong University, 2014, 48(8): 1170-1174.
[8]	LEE C Y. Machine scheduling with an availability constraint[J]. Journal of Global Optimization, 1996, 9(3/4): 395-416.
[9]	KUBZIN M A, STRUSEVICH V A. Planning machine maintenance in two-machine shop scheduling[J]. Operations Research, 2006, 54(4): 789-800.
[10]	廖雯竹，潘尔顺，奚立峰. 基于设备可靠性的动态预防维护策略[J]. 上海交通大学学报，2009, 43(8): 1332-1336.
	LIAO Wenzhu, PAN Ershun, XI Lifeng. Research on dynamic predictive maintenance policy based on system reliability[J]. Journal of Shanghai Jiao Tong University, 2009, 43(8): 1332-1336.
[11]	AHMADI R, NEWBY M. Maintenance scheduling of a manufacturing system subject to deterioration[J]. Reliability Engineering & System Safety, 2011, 96(10): 1411-1420.
[12]	YILDIRIM M B, NEZAMI F G. Integrated maintenance and production planning with energy consumption and minimal repair[J]. The International Journal of Advanced Manufacturing Technology, 2014, 74(9/10/11/12): 1419-1430.
[13]	CHEN X H, XIAO L, ZHANG X H. A production scheduling problem considering random failure and imperfect preventive maintenance[J]. Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 2015, 229(1): 26-35.
[14]	丁珮雯，蒋祖华，胡家文，等. 带有交货期时间窗的生产与维护联合调度优化[J]. 上海交通大学学报，2015, 49(4): 524-530.
	DING Peiwen, JIANG Zuhua, HU Jiawen, et al. Integrating production scheduling and preventive maintenance for a single machine with due window[J]. Journal of Shanghai Jiao Tong University, 2015, 49(4): 524-530.
[15]	郝虹斐，郭伟，桂林，等. 非完美维修情境下的预防性维修多目标决策模型[J]. 上海交通大学学报，2018, 52(5): 518-524.
	HAO Hongfei, GUO Wei, GUI Lin, et al. A multi-objective preventive maintenance decision-making model for imperfect repair process[J]. Journal of Shanghai Jiao Tong University, 2018, 52(5): 518-524.
[16]	ASCHER H, FEINGOLD H. Repairable systems reliability modeling, inference, misconceptions and their causes [J]. Microelectronics Reliability, 1986, 26(5): 993.
[17]	SCHMIDT G. Scheduling with limited machine availability[J]. European Journal of Operational Research, 2000, 121(1): 1-15.
[18]	EMMONS H. One-machine sequencing to minimize certain functions of job tardiness[J]. Operations Research, 1969, 17(4): 701-715.
[19]	KANET J J. New precedence theorems for one-machine weighted tardiness[J]. Mathematics of Operations Research, 2007, 32(3): 579-588.

\|N\|	Lingo		GA
\|N\|	O_Lin/h	t_CPU/s	O_GA/h	t_CPU/s
3	0	1.32	0	1.35
4	0	12.93	0	1.40
5	0	68.70	0	1.44
6	0	421.49	0	1.57
7	2.33	1 394.61	0	1.65
8	6.13	5 057.13	0	1.75
9	9.34	5 400.00	0	1.84
10	15.90	5 400.00	0	1.91

\|N\|	GA		GA-IPM			GA-PPM
\|N\|	O_TPM/h	t_CPU/s	O_IPM/h	t_CPU/s	D_IPM/%	O_PPM/h	t_CPU/s	D_PPM/%
20	8	3.21	21	3.01	162.50	14	2.87	75.00
30	17	4.64	36	4.08	111.76	26	3.91	52.94
40	94	5.88	140	5.04	48.94	137	4.86	45.74
50	237	6.72	335	6.35	41.35	308	5.79	29.96
60	295	6.94	407	6.94	37.97	320	6.93	8.47
70	470	8.35	603	8.14	28.30	499	7.31	6.17
80	711	9.21	924	9.41	29.96	742	9.45	4.36
90	1 142	10.37	1 458	9.88	27.67	1 198	9.53	4.90
100	1 445	10.28	1 793	10.56	24.08	1 511	10.78	4.57