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.
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
.
DOI: 10.1007/s12204-015-1690-z
[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.
