Highly efficient scheduling algorithms for identical parallel machines with sufficient conditions for optimality of the solutions

• Autorzy: Telenyk Sergii , Nowakowski Grzegorz , Pavlov Oleksandr , Misura Olena , Melnikov Oleg , Khalus Olena

Identyfikatory

DOI

10.24425/bpasts.2024.148939

• Języki publikacji: EN

Abstrakty

EN

This paper aims to develop new highly efficient PSC-algorithms (algorithms that contain a polynomial-time sub-algorithm with sufficient conditions for the optimality of the solutions obtained) for several interrelated problems involving identical parallel machine scheduling. These problems share common basic theoretical positions and common principles of their solving. Two main intractable scheduling problems are considered: (“Minimization of the total tardiness of jobs on parallel machines with machine release times and a common due date” (TTPR) and “Minimising the total tardiness of parallel machines completion times with respect to the common due date with machine release times” (TTCR)) and an auxiliary one (“Minimising the difference between the maximal and the minimal completion times of the machines” (MDMM)). The latter is used to efficiently solve the first two ones. For the TTPR problem and its generalisation in the case when there are machines with release times that extend past the common due date (TTPRE problem), new theoretical properties are given, which were obtained on the basis of the previously published ones. Based on the new theoretical results and computational experiments the PSC-algorithm solving these two problems is modified (sub-algorithms A1, A2). Then the auxiliary problem MDMM is considered and Algorithm A0 is proposed for its solving. Based on the analysis of computational experiments, A0 is included in the PSC-algorithm for solving the problems TTPR, TTPRE as its polynomial component for constructing a schedule with zero tardiness of jobs if such a schedule exists (a new third sufficient condition of optimality). Next, the second intractable combinatorial optimization problem TTCR is considered, deducing its sufficient conditions of optimality, and it is shown that Algorithm A0 is also an efficient polynomial component of the PSC-algorithm solving the TTCR problem. Next, the case of a schedule structure is analysed (partially tardy), in which the functionals of the TTPR and TTCR problems become identical. This facilitates the use of Algorithm A1 for the TTPR problem in this case of the TTCR problem. For Algorithm A1, in addition to the possibility of obtaining a better solution, there exists a theoretically proven estimate of the deviation of the solution from the optimum. Thus, the second PSC-algorithm solving the TTCR problem finds an exact solution or an approximate solution with a strict upper bound for its deviation from the optimum. The practicability of solving the problems under consideration is substantiated.

Słowa kluczowe

EN

scheduling; intractable problems of discrete optimisation; sufficient conditions for optimality; parallel machines; common due date

PL

planowanie; trudne do rozwiązania problemy optymalizacji dyskretnej; maszyny równoległe; termin wspólny; warunek dostatecznej optymalności

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2024
• Tom: Vol. 72, nr 1
• Strony: art. no. e148939
• Opis fizyczny: Bibliogr. 23 poz., rys., tab.

Twórcy

autor

Telenyk Sergii

• Faculty of Electrical and Computer Engineering, Cracow University of Technology, Warszawska 24, 31-155 Cracow, Poland

• https://orcid.org/0000-0001-9202-9406

autor

Nowakowski Grzegorz

• Faculty of Electrical and Computer Engineering, Cracow University of Technology, Warszawska 24, 31-155 Cracow, Poland

• https://orcid.org/0000-0002-3086-0947

autor

Pavlov Oleksandr

• National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Prosp. Peremohy 37, Kyiv, Ukraine

• https://orcid.org/0000-0002-6524-6410

autor

Misura Olena

• National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Prosp. Peremohy 37, Kyiv, Ukraine

• https://orcid.org/0000-0002-4210-0996

autor

Melnikov Oleg

• National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Prosp. Peremohy 37, Kyiv, Ukraine

• https://orcid.org/0000-0002-2651-2739

autor

Khalus Olena

• National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Prosp. Peremohy 37, Kyiv, Ukraine

• https://orcid.org/0000-0002-5485-7881

Bibliografia

• [1] J. Leng and P. Jiang, “Dynamic scheduling in RFID-driven discrete manufacturing system by using multi-layer network metrics as heuristic information,” J. Intell. Manuf., vol. 30, no. 3, pp. 979–994, Feb. 2017, doi: 10.1007/s10845-017-1301-y.
• [2] T. O’Brien, “Discrete Manufacturing Systems: High-Level Requirements.” [Online]. Available: https://www.visualsouth.com/blog/discrete-manufacturing-systems-requirements [Accessed: 12. Mar. 2023].
• [3] X. Li and L. Gao, “Introduction for Integrated Process Planning and Scheduling,” in Effective Methods for Integrated Process Planning and Scheduling, 1st ed., X. Li and L. Gao, Eds. Engineering Applications of Computational Methods, vol. 2. Berlin, Heidelberg: Springer, 2020, pp. 1–15, doi: 10.1007/978-3-662-55305-3_1.
• [4] S. Ceschia, L. Di Gaspero, and A. Schaerf, “Solving discrete lotsizing and scheduling by simulated annealing and mixed integer programming,” Comput. Ind. Eng., vol. 114, pp. 235–243, Dec. 2017, doi: 10.1016/j.cie.2017.10.017.
• [5] X. Chi, S. Liu, and C. Li, “Research on optimization of unrelated parallel machine scheduling based on IG-TS algorithm,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 70, no. 4, p. e141724, Jun. 2022, doi: 10.24425/bpasts.2022.141724.
• [6] A. Burduk, K. Musiał, A. Balashov, A. Batako, and A. Safonyk, “Solving scheduling problems with integrated online sustainability observation using heuristic optimization,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 70, no. 6, p. e143830, Dec. 2022, doi: 10.24425/bpasts.2022.143830.
• [7] M.Z. Zgurovsky and A.A. Pavlov, Trudnoreshayemyye zadachi kombinatornoy optimizatsii v planirovanii i prinyatii resheniy (Intractable Combinatorial Optimization Problems in Planning and Decision Making). Kyiv: Naukova dumka, 2016. (in Russian).
• [8] M.Z. Zgurovsky and A.A. Pavlov, “Introduction,” in Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications, 1st ed., M.Z. Zgurovsky and A.A. Pavlov, Eds. Studies in Systems, Decision and Control, vol. 173. Cham: Springer, 2019, pp. 1–14, doi: 10.1007/978-3-319-98977-8_1.
• [9] A.A. Pavlov, E.B. Misura, and T.N. Lisetsky, “Sostavleniye raspisaniya vypolneniya nezavisimykh zadaniy identichnymi parallel’nymi priborami, momenty zapuska kotorykh men’she obshchego direktivnogo sroka (Scheduling independent tasks on the identical parallel machines which starting times are smaller than a common due date),” Visnyk NTUU “KPI”. Informatics, Operation and Computer Science, no. 58, pp. 24–28, 2013. [Online]. Available: https://ela.kpi.ua/handle/123456789/15486 [Accessed: 12 Mar 2023]. (in Russian).
• [10] M.Z. Zgurovsky and A.A. Pavlov, “The total tardiness of tasks minimization on identical parallel machines with arbitrary fixed times of their start and a common due date,” in Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications, 1st ed., M.Z. Zgurovsky and A.A. Pavlov, Eds. Studies in Systems, Decision and Control, vol. 173. Cham: Springer, 2019, pp. 265–290, doi: 10.1007/978-3-319-98977-8_6.
• [11] M.R. Garey and D.S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1990.
• [12] Yu.P. Adler, E.V. Markova, and Yu.V. Granovskiy. Planirovaniye eksperimenta pri poiske optimal’nykh usloviy (Planning an Experiment in the Search for Optimal Conditions), 2nd ed. Moscow: Nauka, 1976. (in Russian).
• [13] A.A. Pavlov and E.B. Misura, “Minimizatsiya summarnogo zapazdyvaniya pri vypolnenii nezavisimykh zadaniy s obshchim direktivnym srokom identichnymi parallel’nymi priborami, momenty zapuska kotorykh proizvol’ny (The total tardiness minimization when processing independent tasks with a common due date on the identical parallel machines with an arbitrary starting times),” Visnyk NTUU “KPI”. Informatics, Operation and Computer Science, no. 59, pp. 28–34, 2013. [Online]. Available: https://ela.kpi.ua/handle/123456789/15526 [Accessed: 12 Mar 2023]. (in Russian).
• [14] Z. Jia, Y. Cui, and K. Li, “An ant colony-based algorithm for integrated scheduling on batch machines with non-identical capacities,” Appl. Intell., vol. 52, no. 2, pp. 1752–1769, Jan 2022, doi: 10.1007/s10489-021-02336-z.
• [15] M. Haroune, C. Dhib, E. Neron, A. Soukhal, H.M. Babou, and F.M. Nanne, “A Hybrid Heuristic for a Two-Agent Multi-Skill Resource-Constrained Scheduling Problem,” Int. J. Adv. Comput. Sci. Appl., vol. 13, no. 5, 2022, doi: 10.14569/ijacsa.2022.01305104.
• [16] J.C.S.N. Pinheiro, J.E.C. Arroyo, and L.B. Fialho, “Scheduling unrelated parallel machines with family setups and resource constraints to minimize total tardiness,” in Proc. 2020 Genetic and Evolutionary Computation Conference Companion (GECCO), 2020, pp. 1409–1417, doi: 10.1145/3377929.3398150.
• [17] M. Ðurasević and D. Jakobović, “Heuristic and metaheuristic methods for the parallel unrelated machines scheduling problem: a survey,” Artif. Intell. Rev., vol. 56, no. 4, pp. 3181–3289, 2022, doi: 10.1007/s10462-022-10247-9.
• [18] V.S. Tanaev and V.V. Shkurba, Vvedeniye v teoriyu raspisaniy (Introduction to scheduling theory). Moscow: Nauka, 1975. (in Russian).
• [19] Y. Ouazene, F. Yalaoui, H. Chehade, and A. Yalaoui, “Work-load balancing in identical parallel machine scheduling using a mathematical programming method,” Int. J. Comput. Intell. Syst., vol. 7, no. Supplement 1, p. 58, 2014, doi: 10.1080/18756891.2013.853932.
• [20] A.A. Pavlov, O.G. Zhdanova, and M.O. Sperkach, “Zadacha sostavleniya dopustimogo raspisaniya s maksimal’no pozdnim momentom zapuska vypolneniya identichnymi parallel’nymi priborami rabot s obshchim direktivnym srokom (The problem of creating a feasible schedule with maximum late moment of starting the jobs with common due date on identical parallel machines),” Visnyk NTUU “KPI”. Informatics, Operation and Computer Science, no. 61, pp. 93–102, 2014. [Online]. Available: https://ela.kpi.ua/handle/123456789/16721 [Accessed: 12 Mar 2023]. (in Russian).
• [21] M.Z. Zgurovsky and A.A. Pavlov, “Algorithms and Software of the Four-Level Model of Planning and Decision Making,” in Combinatorial Optimization Problems in Planning and Decision Making: Theory and Applications, 1st ed., M.Z. Zgurovsky and A.A. Pavlov, Eds. Studies in Systems, Decision and Control, vol. 173. Cham: Springer, 2019, pp. 407–518, doi: 10.1007/978-3-319-98977-8_9.
• [22] M. Sterna, “Late and early work scheduling: A survey,” Omega, vol. 104, p. 102453, 2021, doi: 10.1016/j.omega.2021.102453.
• [23] X. Chen, M. Sterna, X. Han, and J. Blazewicz, “Scheduling on parallel identical machines with late work criterion: Offline and online cases,” J. Sched., vol. 19, no. 6, pp. 729–736, 2015, doi: 10.1007/s10951-015-0464-7.

Uwagi

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