×

zbMATH — the first resource for mathematics

Makespan minimization for two parallel machines scheduling with a periodic availability constraint: mathematical programming model, average-case analysis, and anomalies. (English) Zbl 1426.90145
Summary: A mathematical programming model is proposed for the two parallel machines scheduling problem where one machine is periodically unavailable, jobs are non-preemptive, and the objective is minimizing the makespan. The model is established by transforming the two parallel machine setting into a single machine setting. Average-case analyses of the classical Longest Processing Time first (LPT) algorithm and the List Scheduling (LS) are presented. Computational experiments show that the LPT algorithm beats the LS algorithm in all the 96 combinations of two main parameters from an average-case error point of view and that the average-case error of the LPT algorithm is less than 2% when the number of jobs is greater than twenty. Unexpectedly, there also exist instances showing that the LS algorithm may beat the LPT algorithm from the average-case error point of view.

MSC:
90B35 Deterministic scheduling theory in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Xu, D.; Cheng, Z.; Yin, Y.; Li, H., Makespan minimization for two parallel machines scheduling with a periodic availability constraint, Comput. Oper. Res., 36, 1809-1812, (2009) · Zbl 1179.90166
[2] D. Xu, M. Qu, Makespan minimization for two parallel machines scheduling with a periodic availability constraint: the preemptive offline version, in: The Third International Joint Conference on Computational Sciences and Optimization, Huangshan, China, vol. 2, 2010, pp. 177-181.
[3] Akturk, M. S.; Ghosh, J. B.; Gunes, E. D., Scheduling with tool changes to minimize total completion time: a study of heuristics and their performance, Naval Res. Logist., 50, 15-30, (2003) · Zbl 1044.90031
[4] Akturk, M. S.; Ghosh, J. B.; Gunes, E. D., Scheduling with tool changes to minimize total completion time: basic results and SPT performance, Eur. J. Oper. Res., 157, 784-790, (2004) · Zbl 1067.90038
[5] Chen, J. S., Single-machine scheduling with flexible and periodic maintenance, J. Oper. Res. Soc., 57, 703-710, (2006) · Zbl 1121.90052
[6] Chen, J. S., Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, Eur. J. Oper. Res., 190, 90-102, (2008) · Zbl 1146.90028
[7] Chen, J. S., Optimization models for the tool change scheduling problem, Omega-Int. J. Manag. Sci., 36, 888-894, (2008) · Zbl 1197.90310
[8] Chen, W. J., Minimizing total flow time in the single-machine scheduling problem with periodic maintenance, J. Oper. Res. Soc., 57, 410-415, (2006) · Zbl 1086.90020
[9] Chen, W. J., Scheduling of jobs and maintenance in a textile company, Int. J. Adv. Manuf. Technol., 31, 737-742, (2007)
[10] Chen, W. J., Minimizing number of tardy jobs on a single machine subject to periodic maintenance, Omega-Int. J. Manag. Sci., 37, 591-599, (2009)
[11] Ji, M.; He, Y.; Cheng, T. C.E., Single-machine scheduling with periodic maintenance to minimize makespan, Comput. Oper. Res., 34, 1764-1770, (2007) · Zbl 1159.90404
[12] Liao, C. J.; Chen, W. J., Single-machine scheduling with periodic maintenance and nonresumable jobs, Comput. Oper. Res., 30, 1335-1347, (2003) · Zbl 1037.90031
[13] Qi, X.; Chen, T.; Tu, F., Scheduling the maintenance on a single machine, J. Oper. Res. Soc., 50, 1071-1078, (1999) · Zbl 1054.90550
[14] Qi, X., A note on worst-case performance of heuristics for maintenance scheduling problems, Discrete Appl. Math., 155, 416-422, (2007) · Zbl 1147.90008
[15] Sbihi, M.; Varnier, C., Single-machine scheduling with periodic and flexible periodic maintenance to minimize maximum tardiness, Comput. Ind. Eng., 55, 830-840, (2008)
[16] Xu, D.; Sun, K.; Li, H., Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan, Comput. Oper. Res., 35, 1344-1349, (2008) · Zbl 1171.90411
[17] Xu, D.; Yin, Y.; Li, H., A note on scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan, Eur. J. Oper. Res., 197, 825-827, (2009) · Zbl 1159.68359
[18] Xu, D.; Yin, Y.; Li, H., Scheduling jobs under increasing linear machine maintenance time, J. Sched., 13, 443-449, (2010) · Zbl 1231.90222
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.