Exact Approaches to Late Work Scheduling on Unrelated Machines

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

doi:10.34768/amcs-2023-0021

.blurhash-client-img { display: none !important; }

Exact Approaches to Late Work Scheduling on Unrelated Machines

International Journal of Applied Mathematics and Computer Science

Volume 33 (2023): Issue 2 (June 2023)

By: Xinbo Liu, Wen Wang, Xin Chen, Malgorzata Sterna and Jacek Blazewicz

Open Access

|Jun 2023

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

Articles in this issue

DOI: https://doi.org/10.34768/amcs-2023-0021 | Journal eISSN: 2083-8492 | Journal ISSN: 1641-876X

Journal RSS Feed

Language: English

Page range: 285 - 295

Submitted on: Jun 10, 2022

Accepted on: Jan 12, 2023

Published on: Jun 23, 2023

Published by: University of Zielona Góra

In partnership with: Paradigm Publishing Services

Publication frequency: 4 issues per year

Keywords:

late work scheduling,

unrelated machines,

mathematical model,

branch-and-bound algorithm,

dynamic programming

Related subjects:

Mathematics,

Applied mathematics

© 2023 Xinbo Liu, Wen Wang, Xin Chen, Malgorzata Sterna, Jacek Blazewicz, published by University of Zielona Góra
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 33 (2023): Issue 2 (June 2023)