Heuristics for the Identical Machine Scheduling Problem with Preventive Maintenances

doi:10.1007/s12204-015-1690-z

Abstract

Abstract: In this paper, two mixed integer programming models integrating production scheduling and preventive maintenances are proposed to derive the optimal solutions for the identical machine scheduling problem with unavailability constraints. In the first model, the maintenance activities are performed periodically and the objective is to minimize the makespan. In the second model, the maintenance activities are flexible and the machines’ continuous working time cannot exceed a maximum allowed time T; the objective is to minimize the total completion time of jobs. For the first problem, we propose a heuristic longest batch time (LBT) and prove that the worst case error bound of LBT is 2. For the second problem, we develop a heuristic modified smallest processing time (MSPT) based on some properties of the optimal solutions. Computational experiments show that both of the heuristics are effective and efficient compared with the results obtained by CPLEX and the other algorithms.

Key words: identical machine scheduling| unavailability constraints| heuristic

摘要： In this paper, two mixed integer programming models integrating production scheduling and preventive maintenances are proposed to derive the optimal solutions for the identical machine scheduling problem with unavailability constraints. In the first model, the maintenance activities are performed periodically and the objective is to minimize the makespan. In the second model, the maintenance activities are flexible and the machines’ continuous working time cannot exceed a maximum allowed time T; the objective is to minimize the total completion time of jobs. For the first problem, we propose a heuristic longest batch time (LBT) and prove that the worst case error bound of LBT is 2. For the second problem, we develop a heuristic modified smallest processing time (MSPT) based on some properties of the optimal solutions. Computational experiments show that both of the heuristics are effective and efficient compared with the results obtained by CPLEX and the other algorithms.

关键词: identical machine scheduling| unavailability constraints| heuristic

CLC Number:

F 224.9

JIANG Cailin1 (江才林), LU Zhiqiang1* (陆志强), CUI Weiwei2 (崔维伟). Heuristics for the Identical Machine Scheduling Problem with Preventive Maintenances[J]. Journal of shanghai Jiaotong University (Science), 2016, 21(1): 112-120.

References 14

[1]	YANG S J, YANG D L. Minimizing the totalcompletion time in single-machine scheduling withaging/deteriorating effects and deteriorating maintenanceactivities [J]. Computers and Mathematics withApplications, 2010, 60(7): 2161-2169.
[2]	MOLAEE E, MOSLEHI G, REISI M. Minimizingmaximum earliness and number of tardy jobs in thesingle machine scheduling problem with availabilityconstraint [J]. Computers and Mathematics with Applications,2011, 62(9): 3622-3641.
[3]	CUI W W, LU Z Q. Integrating production schedulingand preventive maintenance planning for a singlemachine [J]. Journal of Shanghai Jiaotong University,2012, 46(12): 2009-2013 (in Chinese).
[4]	LEE C Y. Machine scheduling with an availabilityconstraint [J]. Journal of Global Optimization, 1996,9(3): 395-416.
[5]	LIAO L W, GWO J S. Parallel machine schedulingwith machine availability and eligibility constraints[J]. European Journal of Operational Research, 2008,184(2): 458-467.
[6]	KUBZIN M A, POTTS C N, STRUSEVICH V A.Approximation results for flow shop scheduling problemswith machine availability constraints [J]. Computers& Operations Research, 2009, 36(2): 379-390.
[7]	HSU C J, LOW C, SU C T. A single-machinescheduling problem with maintenance activities tominimize makespan [J]. Applied Mathematics andComputation, 2010, 215(11): 3929-3935.
[8]	XU D H, YANG D L. Makespan minimization fortwo parallel machines scheduling with a periodic availabilityconstraint: Mathematical programming model,average-case analysis, and anomalies [J]. Applied MathematicalModelling, 2013, 37(14): 7561-7567.
[9]	QI X, CHEN T, TU F. Scheduling the maintenanceon a single machine [J]. Journal of the Operational ResearchSociety, 1999, 50(10): 1071-1078.
[10]	CHEN J S. Scheduling of non resumable jobs and flexiblemaintenance activities on a single machine to minimizemakespan [J]. European Journal of OperationalResearch, 2008, 190(1): 90-120.
[11]	LEE C Y, CHEN Z L. Scheduling of jobs and maintenanceactivities on parallel machines [J]. Naval ResearchLogistics, 2000, 47(2): 85-183.
[12]	SUN K B, LI H X. Scheduling problems with multiplemaintenance activities and non-preemptive jobs on twoidentical parallel machines [J]. International Journal ofProduction Economic, 2010, 124(1): 151-158.
[13]	XU D H, SUN K B, LI H X. Parallel machinescheduling with almost periodic maintenance and nonpreemptivejobs to minimize makespan [J]. Computers& Operations Research, 2008, 35(4): 1344-1349.
[14]	JI M, HE Y, CHEN T C E. Single-machine schedulingwith periodic maintenance to minimize makespan[J]. Computers & Operations Research, 2007, 34(6):1764-1770.

[1]	YE Hongqing, SU Huade, ZHENG Meimei, XIA Tangbin. Joint Optimization of Replacement and Spare Parts Ordering with Dual Sourcing [J]. Journal of Shanghai Jiao Tong University, 2022, 56(10): 1359-1367.
[2]	MENG Lingtong, JIANG Zuhua, TAO Ningrong, LIU Jianfeng, ZHENG Hong. Multi-Stockyard Scheduling Considering Technological Process and Combined Assembly Block [J]. Journal of Shanghai Jiao Tong University, 2020, 54(4): 331-343.
[3]	MENG Lingtong,JIANG Zuhua,TAO Ningrong,LIU Jianfeng,LI Baihe. Combined Assembly Block Scheduling in Storage Yard of Shipbuilding [J]. Journal of Shanghai Jiaotong University, 2019, 53(7): 780-788.
[4]	LI Tantan,LEI Ming. Heuristic Algorithm-Based Initiation Method of Probability Hypothesis Density Filter for Target Tracking [J]. Journal of Shanghai Jiaotong University, 2018, 52(1): 63-69.
[5]	JIAN Lixuan* (简立轩), YIN Dong (尹栋), SHEN Lincheng (沈林成), NIU Yifeng (牛轶峰). Human Machine Collaborative Support Scheduling System of Intelligence Information from Multiple Unmanned Aerial Vehicles Based on Eye Tracker [J]. Journal of shanghai Jiaotong University (Science), 2017, 22(3): 322-328.
[6]	LI Cheng,LI Shuang,FENG Yiping,RONG Gang. Scheduling Flexible Manufacturing System Based on Timed Petri Net and Heuristic Search [J]. Journal of Shanghai Jiaotong University, 2015, 49(05): 708-713.
[7]	ZHANG Bowen1,LU Zhiqiang1,ZHANG Yuejun2. An Integrated Model of Production Planning and Preventive Maintenance for Parallel Systems [J]. Journal of Shanghai Jiaotong University, 2015, 49(04): 564-571.
[8]	DING Peiwen,JIANG Zuhua，HU Jiawen,HAN Lijie. Integrating Production Scheduling and Preventive Maintenance for a Single Machine with Due Window [J]. Journal of Shanghai Jiaotong University, 2015, 49(04): 524-530.
[9]	BIAN Zhan1 (边展), LI Na1 (李娜), LI Xiang-jun2 (李向军), JIN Zhi-hong1* (靳志宏). Operations Scheduling for Rail Mounted Gantry Cranes in a Container Terminal Yard [J]. Journal of shanghai Jiaotong University (Science), 2014, 19(3): 337-345.
[10]	BIAN Zhan1,XU Qi1,JIN Zhihong1,LI Xiangjun2. Optimization of Yard Crane Scheduling with Consideration of Export Container Relocation [J]. Journal of Shanghai Jiaotong University, 2014, 48(1): 146-153.
[11]	LI Xiang,CAO Yuanguo,ZHANG Zhinan,XIE Youbai. An Automated Planning-Based Conceptual Design Synthesis Approach [J]. Journal of Shanghai Jiaotong University, 2014, 48(08): 1134-1141.
[12]	HE Jun-liang1,2* (何军良), ZHANG Wei-min1 (张为民), HUANG You-fang2 (黄有方), YAN Wei2 (严伟). An Efficient Approach for Solving Yard Crane Scheduling in a Container Terminal [J]. Journal of shanghai Jiaotong University (Science), 2013, 18(5): 606-619.
[13]	ZHANG zhiying,XU jianxiang,JI feng. Shipbuilding Yard Scheduling Approach Based on Genetic Algorithm [J]. Journal of Shanghai Jiaotong University, 2013, 47(07): 1036-1042.
[14]	LIU Tian-Tang, JIANG Zhi-Bin, HU Hong-Tao, LIU Ran. An Enhanced Hybrid Genetic Algorithm for the Capacitated Arc Routing Problem [J]. Journal of Shanghai Jiaotong University, 2013, 47(04): 619-625.
[15]	BI Ya-1, LI Wen-Feng-2. Research on the Location-Allocation System with Constraints Based on Covering Location Problem [J]. Journal of Shanghai Jiaotong University, 2013, 47(03): 495-499.