A Hyper-Heuristic for the Preemptive Single Machine Scheduling Problem to Minimize the Total Weighted Tardiness

Romanuke, Vadim

doi:10.2478/acss-2022-0001

Abstract

A problem of minimizing the total weighted tardiness in the preemptive single machine scheduling for discrete manufacturing is considered. A hyper-heuristic is presented, which is composed of 24 various heuristics, to find an approximately optimal schedule whenever finding the exact solution is practically intractable. The three heuristics are based on the well-known rules, whereas the 21 heuristics are introduced first. Therefore, the hyper-heuristic selects the best heuristic schedule among 24 schedule versions, whose total weighted tardiness is minimal. Each of the 24 heuristics can solely produce a schedule which is the best one for a given scheduling problem. Despite the percentage of zero gap instances decreases as the greater number of jobs is scheduled, the average and maximal gaps decrease as well. In particular, the percentage is not less than 80 % when up to 10 jobs are scheduled. The average gap calculated over nonzero gaps does not exceed 4 % in the case of scheduling 7 jobs. When manufacturing consists of hundreds of jobs, the hyper-heuristic is made an online scheduling algorithm by applying it only to a starting part of the manufacturing process.

References

[1] Z. Wang and C. Lu, “An integrated job shop scheduling and assembly sequence planning approach for discrete manufacturing,” Journal of Manufacturing Systems, vol. 61, pp. 27–44, Oct. 2021. https://doi.org/10.1016/j.jmsy.2021.08.003
Search in Google Scholar Back to article
[2] J. C. Serrano-Ruiz, J. Mula, and R. Poler, “Smart manufacturing scheduling: A literature review,” Journal of Manufacturing Systems, vol. 61, pp. 265–287, Oct. 2021. https://doi.org/10.1016/j.jmsy.2021.09.011
Search in Google Scholar Back to article
[3] M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer, 2016. https://doi.org/10.1007/978-3-319-26580-3
Search in Google Scholar Back to article
[4] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, “Optimization and approximation in deterministic sequencing and scheduling: A survey,” Annals of Discrete Mathematics, vol. 5, pp. 287–326, 1979. https://doi.org/10.1016/S0167-5060(08)70356-X
Search in Google Scholar Back to article
[5] J. Du and J. Y. T. Leung, “Minimizing total tardiness on one machine is NP-hard,” Mathematics of Operations Research, vol. 15, no. 3, pp. 483–495, Aug. 1990. https://doi.org/10.1287/moor.15.3.483
Search in Google Scholar Back to article
[6] W. Y. Ku and J. C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational analysis,” Computers & Operations Research, vol. 73, pp. 165–173, Sep. 2016. https://doi.org/10.1016/j.cor.2016.04.006
Search in Google Scholar Back to article
[7] V. V. Romanuke, “Minimal total weighted tardiness in tight-tardy single machine preemptive idling-free scheduling,” Applied Computer Systems, vol. 24, no. 2, pp. 150–160, Dec. 2019. https://doi.org/10.2478/acss-2019-0019
Search in Google Scholar Back to article
[8] P. Brucker, Scheduling Algorithms, 5th ed. Springer-Verlag Berlin Heidelberg, 2007. https://doi.org/10.1007/978-3-540-69516-5
Search in Google Scholar Back to article
[9] M. Batsyn, B. Goldengorin, P. Pardalos, and P. Sukhov, “Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time,” Optimization Methods & Software, vol. 29, no. 5, pp. 955–963, 2014. https://doi.org/10.1080/10556788.2013.854360
Search in Google Scholar Back to article
[10] S. Haruhiko and S. Hiroaki, Online Scheduling in Manufacturing: A Cumulative Delay Approach. Springer-Verlag London, 2013. https://doi.org/10.1007/978-1-4471-4561-5
Search in Google Scholar Back to article
[11] M. C. Georgiadis, A. A. Levis, P. Tsiakis, I. Sanidiotis, C. C. Pantelides, and L. G. Papageorgiou, “Optimisation-based scheduling: A discrete manufacturing case study,” Computers & Industrial Engineering, vol. 49, no. 1, pp. 118–145, Aug. 2005. https://doi.org/10.1016/j.cie.2005.02.004
Search in Google Scholar Back to article
[12] M. Aicardi, A. Di Febbraro, and R. Minciardi, “Combined scheduling and routing in discrete manufacturing systems,” IFAC Proceedings Volumes, vol. 23, no. 3, pp. 671–676, Sep. 1990. https://doi.org/10.1016/S1474-6670(17)52637-3
Search in Google Scholar Back to article
[13] F. Jaramillo and M. Erkoc, “Minimizing total weighted tardiness and overtime costs for single machine preemptive scheduling,” Computers & Industrial Engineering, vol. 107, pp. 109–119, May 2017. https://doi.org/10.1016/j.cie.2017.03.012
Search in Google Scholar Back to article
[14] B. Goldengorin and V. Romanuke, “Online heuristic for the preemptive single machine scheduling problem to minimize the total weighted tardiness,” Computers & Industrial Engineering, vol. 155, May 2021, Art no. 107090. https://doi.org/10.1016/j.cie.2020.107090
Search in Google Scholar Back to article
[15] R. Panneerselvam, “Simple heuristic to minimize total tardiness in a single machine scheduling problem,” The International Journal of Advanced Manufacturing Technology, vol. 30, no. 7–8, pp. 722–726, 2006. https://doi.org/10.1007/s00170-005-0102-1
Search in Google Scholar Back to article
[16] B. Goldengorin and V. Romanuke, “Experimental analysis of tardiness in preemptive single machine scheduling,” Expert Systems with Applications, vol. 186, Dec. 2021, Art no. 114947. https://doi.org/10.1016/j.eswa.2021.114947
Search in Google Scholar Back to article

A Hyper-Heuristic for the Preemptive Single Machine Scheduling Problem to Minimize the Total Weighted Tardiness

Abstract

Paradigm

My account