Задача одного станка с равными длительностями работ и возможностью прерываний

Задача одного станка с равными длительностями работ и возможностью прерываний

Ляшкова К. А., Сервах В. В.
Дискретный анализ и исследование операций, 31, 3, 105–122 (2024)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2024.31.750

Аннотация:

Рассматривается задача минимизации среднего взвешенного времени для выполнения работ одинаковой длительности на одном станке при заданных временах поступления работ и возможности их прерывания. В настоящее время вычислительная сложность этой задачи неизвестна. В работе предложен алгоритм предобработки входных данных, что позволяет свести задачу к более узкому и регулярному классу примеров. Обоснованы свойства оптимальных решений, на основе которых разработан алгоритм построения конечного подмножества решений, содержащего оптимальное расписание. Описан подход к проведению параметрического анализа расписаний из этого подмножества, который позволяет сформировать подкласс расписаний, оптимальных при некоторых значениях весов. Выделен полиномиально разрешимый случай задачи. 
Табл. 1, ил. 10, библиогр. 16.

Литература:
  1. Pinedo M. L. Scheduling: Theory, algorithms, and systems. New York: Springer, 2008. 678 p. DOI: 10.1007/978-0-387-78935-4.
     
  2. Lenstra J. K., Rinnooy Kan A. H. G., Brucker P. Complexity of machine scheduling problems // Ann. Discrete Math. 1977. V. 1. P. 343–362. DOI: 10.1016/S0167-5060(08)70743-X.
     
  3. Baptiste P. Scheduling equal-length jobs on identical parallel machines // Discrete Appl. Math. 2000. V. 103, No. 1–3. P. 21–32. DOI: 10.1016/ S0166-218X(99)00238-3.
     
  4. Labetoulle J., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Preemptive scheduling of uniform machines subject to release dates // Progress in combinatorial optimization. Toronto: Acad. Press, 1984. P. 245–261. DOI: 10.1016/B978-0-12-566780-7.50020-9.
     
  5. Baker K. R. Introduction to sequencing and scheduling. New York: John Wiley & Sons, 1974. 318 p.
     
  6. Баптист Ф., Карлье Ж., Кононов А. В., Керан М., Севастьянов С. В., Свириденко М. И. Структурные свойства оптимальных расписаний с прерываниями операций // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 1. P. 3–36.
     
  7. Batsyn M., Goldengorin B., Pardalos P. M., Sukhov P. Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time // Optim. Methods Softw. 2014. V. 29. P. 955–963. DOI: 10.1080/10556788.2013.854360.
     
  8. Batsyn M., Goldengorin B., Sukhov P., Pardalos P. M. Lower and upper bounds for the preemptive single machine scheduling problem with equal processing times // Models, algorithms, and technologies for network analysis. Proc. 2nd Int. Conf. Network Analysis (Nizhny Novgorod, Russia, May 7–9, 2012). New York: Springer, 2013. P. 11–27. (Springer Proc. Math. Stat.; V. 59). DOI: 10.1007/978-1-4614-8588-9_2.
     
  9. Goemans M.-X., Queyranne M., Schulz A.-S., Skutella M., Wang Y. Single machine scheduling with release dates // SIAM J. Discrete Math. 2002. V. 15, No. 2. P. 165–192. DOI: 10.1137/S089548019936223X.
     
  10. Kravchenko S. A., Werner F. Scheduling jobs with equal processing times // IFAC Proc. Volumes. 2009. V. 42, No. 4. P. 1262–1267. DOI: 10.3182/20090603-3-RU-2001.0042.
     
  11. Fomin A., Goldengorin B. An efficient model for the preemptive single machine scheduling of equal-length jobs. Ithaca, NY: Cornell Univ., 2020. (Cornell Univ. Libr. e-Print Archive; arXiv:2012.08152). DOI: 10.48550/arXiv.2012. 08152.
     
  12. Chernykh K. A., Servakh V. V. The structure of the optimal solution of the problem of one machine with the possibility of interruptions of jobs // Proc. 14th Int. Asian School-Seminar «Optimization Problems of Complex Systems» (Kara-Oi, Kyrgyzstan, July 20–31, 2018). Piscataway: IEEE, 2018. P. 312–321.
     
  13. Chernykh K. A., Servakh V. V. Combinatorial structure of optimal solutions to the problem of a single machine with preemption // Proc. 15th Int. Asian School-Seminar «Optimization Problems of Complex Systems» (Novosibirsk, Russia, Aug. 26–30, 2019). Piscataway: IEEE, 2019. P. 21–26. DOI: 10.1109/OPCS.2019.8880148.
     
  14. Chernykh K. A., Servakh V. V. Analysis of optimal solutions to the problem of a single machine with preemption // Mathematical optimization theory and operations research: Recent trends. Rev. Sel. Pap. 20th Int. Conf. (Irkutsk, Russia, July 5–10, 2021). Cham: Springer, 2021. P. 163–174. (Commun. Comput. Inf. Sci.; V. 1476). DOI: 10.1007/978-3-030-86433-0_11.
     
  15. Jaramillo F., Erkoc M. Minimizing total weighted tardiness and overtime costs for single machine preemptive scheduling // Comput. Ind. Eng. 2017. V. 107. P. 109–119. DOI: 10.1016/j.cie.2017.03.012.
     
  16. Jaramillo F., Keles B., Erkoc M. Modeling single machine preemptive scheduling problems for computational efficiency // Ann. Oper. Res. 2020. V. 285. P. 197–222. DOI: 10.1007/s10479-019-03298-9.

Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0020).

Ляшкова Ксения Андреевна
  1. Омский филиал Института математики им. С. Л. Соболева, 
    ул. Певцова, 13, 644099 Омск, Россия

E-mail: ksech@bk.ru

Сервах Владимир Вицентьевич
  1. Омский филиал Института математики им. С. Л. Соболева, 
    ул. Певцова, 13, 644099 Омск, Россия

E-mail: svv_usa@rambler.ru

Статья поступила 26 июля 2022 г 
После доработки — 17 января 2024 г.
Принята к публикации 22 марта 2024 г.

Abstract:

We consider the problem of minimizing the weighted average execution time of equal-length jobs performance on one machine at the specified time of job arrival and the possibility of their interruption. The computational complexity of this problem is currently unknown. The article proposes an algorithm for preprocessing input data that allows reducing the problem to a narrower and more regular class of examples. The properties of optimal solutions are substantiated. Based on them, an algorithm for constructing a finite subset of solutions containing an optimal schedule has been developed. A parametric analysis of the schedules in this subset has been carried out that makes it possible to form a subclass of schedules that are optimal at some values of weights. A polynomially solvable case of the problem is isolated. 
Tab. 1, illustr. 10, bibliogr. 16.

References:
  1. M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems (Springer, New York, 2008), DOI: 10.1007/978-0-387-78935-4.
     
  2. J. K. Lenstra, A. H. G. Rinnooy Kan, and P. Brucker, Complexity of machine scheduling problems, Ann. Discrete Math. 1, 343–362 (1977), DOI: 10.1016/S0167-5060(08)70743-X.
     
  3. P. Baptiste, Scheduling equal-length jobs on identical parallel machines, Discrete Appl. Math. 103 (1–3), 21–32 (2000), DOI: 10.1016/S0166-218X(99) 00238-3.
     
  4. J. Labetoulle, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Preemptive scheduling of uniform machines subject to release dates, in Progress in Combinatorial Optimization (Acad. Press, Toronto, 1984), pp. 245–261, DOI: 10.1016/B978-0-12-566780-7.50020-9.
     
  5. K. R. Baker, Introduction to Sequencing and Scheduling (John Wiley & Sons, New York, 1974).
     
  6. P. Baptiste, J. Carlier, A. V. Kononov, M. Queyranne, S. V. Sevast’yanov, and M. I. Sviridenko, Structural properties of optimal schedules with preemption, Diskretn. Anal. Issled. Oper. 16 (1), 3–36 (2009) [Russian] [J. Appl. Ind. Math. 4 (4), 455–474 (2010)].
     
  7. M. Batsyn, B. Goldengorin, P. M. Pardalos, and P. Sukhov, Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time, Optim. Methods Softw. 29, 955–963 (2014), DOI: 10.1080/10556788.2013.854360.
     
  8. M. Batsyn, B. Goldengorin, P. Sukhov, and P. M. Pardalos, Lower and upper bounds for the preemptive single machine scheduling problem with equal processing times, in Models, Algorithms, and Technologies for Network Analysis (Proc. 2nd Int. Conf. Network Analysis, Nizhny Novgorod, Russia, May 7– 9, 2012) (Springer, New York, 2013), pp. 11–27 (Springer Proc. Math. Stat., Vol. 59), DOI: 10.1007/978-1-4614-8588-9_2.
     
  9. M.-X. Goemans, M. Queyranne, A.-S. Schulz, M. Skutella, and Y. Wang, Single machine scheduling with release dates, SIAM J. Discrete Math. 15 (2), 165–192 (2002), DOI: 10.1137/S089548019936223X.
     
  10. S. A. Kravchenko and F. Werner, Scheduling jobs with equal processing times, IFAC Proc. Volumes 42 (4), 1262–1267 (2009), DOI: 10.3182/ 20090603-3-RU-2001.0042.
     
  11. A. Fomin and B. Goldengorin, An efficient model for the preemptive single machine scheduling of equal-length jobs (Cornell Univ., Ithaca, NY, 2020) (Cornell Univ. Libr. e-Print Archive, arXiv:2012.08152), DOI: 10.48550/arXiv. 2012.08152.
     
  12. K. A. Chernykh and V. V. Servakh, The structure of the optimal solution of the problem of one machine with the possibility of interruptions of jobs, in Proc. 14th Int. Asian School-Seminar “Optimization Problems of Complex Systems”, Kara-Oi, Kyrgyzstan, July 20–31, 2018 (IEEE, Piscataway, 2018), pp. 312–321.
     
  13. K. A. Chernykh and V. V. Servakh, Combinatorial structure of optimal solutions to the problem of a single machine with preemption, in Proc. 15th Int. Asian School-Seminar “Optimization Problems of Complex Systems”, Novosibirsk, Russia, Aug. 26–30, 2019 (IEEE, Piscataway, 2019), pp. 21–26, DOI: 10.1109/OPCS.2019.8880148.
     
  14. K. A. Chernykh and V. V. Servakh, Analysis of optimal solutions to the problem of a single machine with preemption, in Mathematical Optimization Theory and Operations Research: Recent Trends (Rev. Sel. Pap. 20th Int. Conf., Irkutsk, Russia, July 5–10, 2021) (Springer, Cham, 2021), pp. 163–174 (Commun. Comput. Inf. Sci., Vol. 1476), DOI: 10.1007/978-3-030-86433-0_11.
     
  15. F. Jaramillo and M. Erkoc, Minimizing total weighted tardiness and overtime costs for single machine preemptive scheduling, Comput. Ind. Eng. 107, 109–119 (2017), DOI: 10.1016/j.cie.2017.03.012.
     
  16. F. Jaramillo, B. Keles, and M. Erkoc, Modeling single machine preemptive scheduling problems for computational efficiency, Ann. Oper. Res. 285, 197– 222 (2020), DOI: 10.1007/s10479-019-03298-9.