Exact Approaches to Late Work Scheduling on Unrelated Machines

Liu, Xinbo; Wang, Wen; Chen, Xin; Sterna, Malgorzata; Blazewicz, Jacek

doi:10.34768/amcs-2023-0021

Abstract

We consider the scheduling problem on unrelated parallel machines in order to minimize the total late work. Since the problem is NP-hard, we propose a mathematical model and two dedicated exact approaches for solving it, based on the branching and bounding strategy and on enumerating combined with a dynamic programming algorithm. The time efficiencies of all three approaches are evaluated through computational experiments.

References

Abasian, F., Ranjbar, M., Salari, M., Davari, M. and Khatami, S.M. (2014). Minimizing the total weighted late work in scheduling of identical parallel processors with communication delays, Applied Mathematical Modelling 38(15): 3975–3986.
Search in Google Scholar Back to article
Afzalirad, M. and Rezaeian, J. (2016). Design of high-performing hybrid meta-heuristics for unrelated parallel machine scheduling with machine eligibility and precedence constraints, Engineering Optimization 48(4): 706–726.
Search in Google Scholar Back to article
Błażewicz, J. (1984). Scheduling preemptible tasks on parallel processors with information loss, Technique et Science Informatiques 3(6): 415–420.
Search in Google Scholar Back to article
Błażewicz, J., Ecker, K.H., Pesch, E., Sterna, M., Schmidt, G. and Weglarz, J. (2019). Handbook on Schedul ing. From Theory to Practice (2nd Edn), Springer, Berlin/Heidelberg/New York.
Search in Google Scholar Back to article
Błażewicz, J., Pesch, E., Sterna, M. and Werner, F. (2005). The two-machine flow-shop problem with weighted late work criterion and common due date, European Journal of Operational Research 165(2): 408–415.
Search in Google Scholar Back to article
Błażewicz, J., Pesch, E., Sterna, M. and Werner, F. (2007). A note on the two machine job shop with the weighted late work criterion, Journal of Scheduling 10(2): 87–95.
Search in Google Scholar Back to article
Chen, X., Liang, Y., Sterna, M., Wang, W. and Błażewicz, J. (2020a). Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date, European Journal of Operational Research 284(1): 67–74.
Search in Google Scholar Back to article
Chen, X., Miao, Q., Lin, B.M., Sterna, M. and Blazewicz, J. (2022). Two-machine flow shop scheduling with a common due date to maximize total early work, European Journal of Operational Research 300(2): 504–511.
Search in Google Scholar Back to article
Chen, X., Sterna, M., Han, X. and Błażewicz, J. (2016). Scheduling on parallel identical machines with late work criterion: Offline and online cases, Journal of Scheduling 19(6): 729–736.
Search in Google Scholar Back to article
Chen, X., Wang, W., Xie, P., Zhang, X., Sterna, M. and Błażewicz, J. (2020b). Exact and heuristic algorithms for scheduling on two identical machines with early work maximization, Computers & Industrial Engineering 144: 106449.
Search in Google Scholar Back to article
Garey, M.R. and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co, New York.
Search in Google Scholar Back to article
Graham, R., Lawler, E., Lenstra, J. and Kan, A.R. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5: 287–326.
Search in Google Scholar Back to article
Janiak, A., Kwiatkowski, T. and Lichtenstein, M. (2013). Scheduling problems with a common due window assignment: A survey, International Journal of Applied Mathematics and Computer Science 23(1): 231–241, DOI: 10.2478/amcs-2013-0018.
Search in Google Scholar Back to article
Lin, B.M.T., Lin, F.-C. and Lee, R.C.T. (2006). Two-machine flow-shop scheduling to minimize total late work, Engineering Optimization 38(4): 501–509.
Search in Google Scholar Back to article
Liu, Z., Yu, B., Zhang, L. and Wang, W. (2022). A hybrid control strategy for a dynamic scheduling problem in transit networks, International Journal of Applied Mathematics and Computer Science 32(4): 553–567, DOI: 10.34768/amcs-2022-0039.
Search in Google Scholar Back to article
Potts, C.N. and Van Wassenhove, L.N. (1992). Single machine scheduling to minimize total late work, Operations Research 40(3): 586–595.
Search in Google Scholar Back to article
Sterna, M. (2011). A survey of scheduling problems with late work criteria, Omega 39(2): 120–129.
Search in Google Scholar Back to article
Sterna, M. (2021). Late and early work scheduling: A survey, Omega 104: 102453.
Search in Google Scholar Back to article
Sterna, M. and Czerniachowska, K. (2017). Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work, Journal of Optimization Theory & Applications 174(3): 927–944.
Search in Google Scholar Back to article
Wang, W., Chen, X., Musial, J. and Blazewicz, J. (2020). Two meta-heuristic algorithms for scheduling on unrelated machines with the late work criterion, International Journal of Applied Mathematics and Computer Science 30(3): 573–584, DOI: 10.34768/amcs-2020-0042.
Search in Google Scholar Back to article

Exact Approaches to Late Work Scheduling on Unrelated Machines

Abstract

Paradigm

My account