Exact approaches to late work scheduling on unrelated machines

• Autorzy: Liu Xinbo , Wang Wen , Chen Xin , Sterna Malgorzata , Blazewicz Jacek

Identyfikatory

DOI

10.34768/amcs-2023-0021

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

late work scheduling; unrelated machine; mathematical model; branch algorithm; bound algorithm; dynamic programming

PL

planowanie pracy; model matematyczny; algorytm podziału; algorytm ograniczeń; programowanie dynamiczne

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2023
• Tom: Vol. 33, no. 2
• Strony: 285--295
• Opis fizyczny: Bibliogr. 20 poz., rys., tab., wykr.

Twórcy

autor

Liu Xinbo

• SolBridge International School of Business, Woosong University, Uam-ro 128, Daejeon 34613, Republic of Korea

autor

Wang Wen

• School of Electronics and Information Engineering, Liaoning University of Technology, Shiying 169, Jinzhou 121001, China

autor

Chen Xin

• School of Electronics and Information Engineering, Liaoning University of Technology, Shiying 169, Jinzhou 121001, China

autor

Sterna Malgorzata

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland

autor

Blazewicz Jacek

• Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland
• European Centre for Bioinformatics and Genomics, Polish Academy of Sciences, ul. Piotrowo 2, 60-965 Poznan, Poland

Bibliografia

• [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] 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] Błażewicz, J. (1984). Scheduling preemptible tasks on parallel processors with information loss, Technique et Science Informatiques 3(6): 415-420.
• [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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] Potts, C.N. and Van Wassenhove, L.N. (1992). Single machine scheduling to minimize total late work, Operations Research 40(3): 586-595.
• [17] Sterna, M. (2011). A survey of scheduling problems with late work criteria, Omega 39(2): 120-129.
• [18] Sterna, M. (2021). Late and early work scheduling: A survey, Omega 104: 102453.
• [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] 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.

Uwagi

PL

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)