Exact approaches to late work scheduling on unrelated machines

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

International Journal of Applied Mathematics and Computer Science, Tome 33 (2023) no. 2, pp. 285-295.

Résumé

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.

Détail

Keywords: late work scheduling, unrelated machine, mathematical model, branch algorithm, bound algorithm, dynamic programming
Mots-clés : planowanie pracy, model matematyczny, algorytm podziału, algorytm ograniczeń, programowanie dynamiczne

Bibliographie

[1] [1] 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.

[2] [2] 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.

[3] [3] Błażewicz, J. (1984). Scheduling preemptible tasks on parallel processors with information loss, Technique et Science Informatiques 3(6): 415-420.

[4] [4] Błażewicz, J., Ecker, K.H., Pesch, E., Sterna, M., Schmidt, G. and Weglarz, J. (2019). Handbook on Scheduling. From Theory to Practice (2nd Edn), Springer, Berlin/Heidelberg/New York.

[5] [5] 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.

[6] [6] 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.

[7] [7] 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.

[8] [8] 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.

[9] [9] 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.

[10] [10] 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.

[11] [11] 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.

[12] [12] 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.

[13] [13] 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.

[14] [14] 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.

[15] [15] 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.

[16] [16] Potts, C.N. and Van Wassenhove, L.N. (1992). Single machine scheduling to minimize total late work, Operations Research 40(3): 586-595.

[17] [17] Sterna, M. (2011). A survey of scheduling problems with late work criteria, Omega 39(2): 120-129.

[18] [18] Sterna, M. (2021). Late and early work scheduling: A survey, Omega 104: 102453.

[19] [19] 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.

[20] [20] 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.