УДК 519.854.2, 519.856.2
MSC: 90B36
https://doi.org/10.21538/0134-4889-2025-31-3-fon-04
В работе рассматривается стохастическая задача составления расписания для одной машины с ограничениями предшествования, где продолжительность выполнения работ подвержена независимым случайным колебаниям из-за непредвиденных событий. Рассматриваются только симметричные относительно математического ожидания вероятностные распределения. Процесс планирования включает два этапа: сначала создается начальное расписание без временных лагов с фиксированными продолжительностями работ, равными их математическим ожиданиям; затем в случае невыполнимости начального расписания применяется сдвиг работ вправо. Стабильность расписания оценивается с помощью среднего ожидаемого отклонения времени старта работ в результирующем расписании от изначально запланированного времени старта работ. Целью является минимизация этого показателя. В статье вводится понятие надежности работы. Работа определяется как более надежная по сравнению с другой, если положительное отклонение от математического ожидания продолжительности другой работы стохастически доминирует над положительным отклонением этой работы. Мы предлагаем теоретическое обоснование того, почему эвристика, выполняющая сначала более надежные работы, приводит к эффективным решениям задачи планирования, и подтверждаем этот вывод вычислительными экспериментами на различных распределениях вероятностей. Результаты демонстрируют высокую эффективность эвристик, основанных на этом правиле, для повышения стабильности расписания.
Ключевые слова: теория расписаний, стохастическое планирование, однопроцессорная задача, стабильность.
СПИСОК ЛИТЕРАТУРЫ
1. Sabuncuoglu I., Goren S. Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research // Int. J. Comput. Integr. Manuf. 2009. Vol. 22, no. 2. P. 138–157. https://doi.org/10.1080/09511920802209033
2. Jorge L.V., Wu D.S., Storer R.H. Robustness measures and robust scheduling for job shops // IIE transactions. 1994. Vol. 26, no. 5. P. 32–43. https://doi.org/10.1080/07408179408966626
3. Khakifirooz M. et al. Scheduling in Industrial environment toward future: insights from Jean-Marie Proth // Int. J. Prod. Res. 2024. Vol. 62, no. 1-2. P. 291–317. https://doi.org/10.1080/00207543.2023.2245919
4. Lee M. et al. A critical review of planning and scheduling in steel-making and continuous casting in the steel industry // J. Operat. Res. Soc. 2024. Vol. 75, no. 8. P. 1421–1455. https://doi.org/10.1080/01605682.2023.2265416
5. Ghobakhloo M. Industry 4.0, digitization, and opportunities for sustainability // J. Cleaner Prod. 2020. Vol. 252. Art. no. 119869. https://doi.org/10.1016/j.jclepro.2019.119869
6. Lasi H. et al. Industry 4.0 // Bus. Inf. Syst. Eng. 2014. Vol. 6. P. 239–242.
https://doi.org/10.1007/s12599-014-0334-4
7. Martinelli R., Mariano F.C.M.Q., Martins C.B. Single machine scheduling in make to order environments: A systematic review // Comp. Ind. Eng. 2022. Vol. 169. Art. no. 108190. https://doi.org/10.1016/j.cie.2022.108190
8. Lawler E.L. et al. Sequencing and scheduling: Algorithms and complexity // Handbooks in operations research and management science. 1993. Vol. 4. P. 445–522. https://doi.org/10.1016/S0927-0507(05)80189-6
9. Du J., Leung J.Y.T. Minimizing total tardiness on one machine is NP-hard // Math. Operat. Res. 1990. Vol. 15, no. 3. P. 483-495. https://doi.org/10.1287/moor.15.3.483
10. Lawler E.L. Optimal sequencing of a single machine subject to precedence constraints // Manag. Sci. 1973. Vol. 19, no. 5. P. 544–546. https://doi.org/10.1287/mnsc.19.5.544
11. Lawler E.L. Sequencing jobs to minimize total weighted completion time subject to precedence constraints // Ann. Discr. Math. 1978. Vol. 2. P. 75–90. https://doi.org/10.1016/S0167-5060(08)70323-6
12. Chekuri C., Motwani R. Precedence constrained scheduling to minimize sum of weighted completion times on a single machine // Discr. Appl. Math. 1999. Vol. 98, no. 1-2. P. 29–38.
https://doi.org/10.1016/S0166-218X(98)00143-7
13. Moore J.M. An n job, one machine sequencing algorithm for minimizing the number of late jobs // Manag. Sci. 1968. Vol. 15, no. 1. P. 102–109. https://doi.org/10.1287/mnsc.15.1.102
14. Brucker P. Classification of scheduling problems // Scheduling Algorithms. Berlin; Heidelberg: Springer, 2007. P. 1–10. https://doi.org/10.1007/978-3-540-69516-5_1
15. Ertem M., Ozcelik F., Saraç T. Single machine scheduling problem with stochastic sequence-dependent setup times // Inter. J. Prod. Res. 2019. Vol. 57, no. 10. P. 3273–3289. https://doi.org/10.1080/00207543.2019.1581383
16. Jia C. Stochastic single machine scheduling with an exponentially distributed due date // Operat. Res. Letters. 2001. Vol. 28, no. 5. P. 199–203. https://doi.org/10.1016/S0167-6377(01)00065-7
17. Soroush H.M., Fredendall L.D. The stochastic single machine scheduling problem with earliness and tardiness costs // Inter. J. Prod. Res. 1994. Vol. 77, no. 2. P. 287–302.
https://doi.org/10.1016/0377-2217(94)90373-5
18. Al-Turki U., Andijani A., Arifulsalam S. A new dispatching rule for the stochastic single-machine scheduling problem // Simulation. 2004. Vol. 80, no. 3. P. 165–170. https://doi.org/10.1177/0037549704045047
19. Ronconi D.P., Powell W.B. Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming // J. Sched. 2010. Vol. 13, no. 6. P. 597–607.
https://doi.org/10.1007/s10951-009-0160-6
20. Mehta S.V. Predictable scheduling of a single machine subject to breakdowns // Inter. J. Comp. Integr., Manufact. 1999. Vol. 12, no. 1. P. 15–38. https://doi.org/10.1080/095119299130443
21. Lu C.C., Lin S.W., Ying K.C. Robust scheduling on a single machine to minimize total flow time // Comput. Operat. Res. 2012. Vol. 39, no. 7. P. 1682–1691. https://doi.org/10.1016/j.cor.2011.10.003
22. Gutjahr W.J., Hellmayr A., Pflug G.C. Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound // Eur. J. Operat. Res. 1999. Vol. 117, no. 2. P. 396–413.
https://doi.org/10.1016/S0377-2217(98)00279-3
23. Motwani R., Raghavan P. Randomized algorithms // Acm Sigact News. 1995. Vol. 26. no. 3, P. 48–50. ISBN: 0-521-47465-5 .
24. CPOptimizer: IBM ILOG CP Optimizer User’s Manual. IBM [e-resource]. 2022. https://www.ibm.com/docs/ru/icos/22.1.1?topic=optimizer-cp-users-manual
25. Kolisch R., Sprecher A., Drexl A. Characterization and generation of a general class of resource-constrained project scheduling problems // Management science. 1995. Vol. 41, no. 10. P. 1693–1703. https://doi.org/10.1287/mnsc.41.10.1693
Поступила 12.05.2025
После доработки 5.06.2025
Принята к публикации 9.06.2025
Опубликована онлайн 19.06.2025
Гладышев Сергей Игоревич
аспирант
Московский физико-технический институт (национальный исследовательский университет)
г. Москва
e-mail: gladyshev.si@phystech.edu
Мусатова Елена Геннадьевна
канд. физ.-мат. наук
старший науч. сотрудник
Институт проблем управления им. В.А. Трапезникова РАН
г. Москва
e-mail: nekolyap@mail.ru
Ссылка на статью: С.И. Гладышев, Е.Г. Мусатова. Сортировка работ по надежности для решения стохастической однопроцессорной задачи теории расписаний // Тр. Ин-та математики и механики УрО РАН. 2025. Т. 31, № 3. С. 91–104.
English
S.I. Gladyshev, E.G. Musatova. Heuristic “Safe Jobs First” for stochastic single machine scheduling problem
This study explores a stochastic single-machine scheduling problem with precedence constraints, where job durations are subject to randomness due to unforeseen events. Initially, each job’s duration is assumed to equal its expected value, and we consider only symmetric probability distributions about this expectation. The scheduling process consists of two main steps: first, generating an initial schedule without time lags, and second, applying a right-shift control policy to manage disruptions. Stability is measured as the mean expected deviation in job start times, and the objective is to minimize this measure. A job is considered safer than another if the positive deviation in the duration of the other job stochastically dominates that of the safer job. We provide a theoretical rationale for why the “safe jobs first” heuristic leads to effective scheduling solutions and support this insight with computational experiments across various probability distributions. The results demonstrate the strong performance of heuristics based on this rule in improving schedule stability.
Keywords: scheduling theory, stochastic scheduling, single machine problem, stability.
Received May 12, 2025
Revised June 5, 2025
Accepted June 9, 2025
Published online June 19, 2025
Sergei Igorevich Gladyshev, doctoral student, Moscow Institute of Physics and Technology, Moscow, 141701 Russia, e-mail: gladyshev.si@phystech.edu
Elena Gennadievna Musatova, Cand. Sci. (Phys.-Math.), V.A.Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, Moscow, 117997 Russia, e-mail: nekolyap@mail.ru
Cite this article as: S.I. Gladyshev, E.G. Musatova. Heuristic “Safe Jobs First” for stochastic single machine scheduling problem. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 3, pp. 91–104.
[References -> on the "English" button bottom right]
