Tytuł artykułu
Treść / Zawartość
Pełne teksty:
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Rocznik
Tom
Strony
285--295
Opis fizyczny
Bibliogr. 20 poz., rys., tab., wykr.
Twórcy
autor
- SolBridge International School of Business, Woosong University, Uam-ro 128, Daejeon 34613, Republic of Korea
autor
- School of Electronics and Information Engineering, Liaoning University of Technology, Shiying 169, Jinzhou 121001, China
autor
- School of Electronics and Information Engineering, Liaoning University of Technology, Shiying 169, Jinzhou 121001, China
autor
- Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965 Poznan, Poland
autor
- 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)
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-241d8cbf-cc4b-467e-9d9d-ad1c4a3cfe05