Online First 2025
УДК 519.854.2, 519.856.2
MSC: 90B36
https://doi.org/10.21538/0134-4889-2025-31-3-fon-04
(Full Text)
В работе рассматривается стохастическая задача составления расписания для одной машины с ограничениями предшествования, где продолжительность выполнения работ подвержена независимым случайным колебаниям из-за непредвиденных событий. Рассматриваются только симметричные относительно математического ожидания вероятностные распределения. Процесс планирования включает два этапа: сначала создается начальное расписание без временных лагов с фиксированными продолжительностями работ, равными их математическим ожиданиям; затем в случае невыполнимости начального расписания применяется сдвиг работ вправо. Стабильность расписания оценивается с помощью среднего ожидаемого отклонения времени старта работ в результирующем расписании от изначально запланированного времени старта работ. Целью является минимизация этого показателя. В статье вводится понятие надежности работы. Работа определяется как более надежная по сравнению с другой, если положительное отклонение от математического ожидания продолжительности другой работы стохастически доминирует над положительным отклонением этой работы. Мы предлагаем теоретическое обоснование того, почему эвристика, выполняющая сначала более надежные работы, приводит к эффективным решениям задачи планирования, и подтверждаем этот вывод вычислительными экспериментами на различных распределениях вероятностей. Результаты демонстрируют высокую эффективность эвристик, основанных на этом правиле, для повышения стабильности расписания.
Ключевые слова: теория расписаний, стохастическое планирование, однопроцессорная задача, стабильность.
Поступила 12.05.2025
После доработки 5.06.2025
Принята к публикации 9.06.2025
Опубликована онлайн 19.06.2025
Гладышев Сергей Игоревич
аспирант
Московский физико-технический институт (национальный исследовательский университет)
г. Москва
e-mail: gladyshev.si@phystech.edu
Мусатова Елена Геннадьевна
канд. физ.-мат. наук
старший науч. сотрудник
Институт проблем управления им. В.А.Трапезникова РАН
г. Москва
e-mail: nekolyap@mail.ru
Ссылка на статью: С.И. Гладышев, Е.Г. Мусатова. Сортировка работ по надежности для решения стохастической однопроцессорной задачи теории расписаний // Тр. Ин-та математики и механики УрО РАН. 2025. https://doi.org/10.21538/0134-4889-2025-31-3-fon-04
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.
https://doi.org/10.21538/0134-4889-2025-31-3-fon-04
