Сортировка работ по надежности для решения стохастической однопроцессорной задачи теории расписаний

В работе рассматривается стохастическая задача составления расписания для одной машины с ограничениями предшествования, где продолжительность выполнения работ подвержена независимым случайным колебаниям из-за непредвиденных событий. Рассматриваются только симметричные относительно математического ожидания вероятностные распределения. Процесс планирования включает два этапа: сначала создается начальное расписание без временных лагов с фиксированными продолжительностями работ, равными их математическим ожиданиям; затем в случае невыполнимости начального расписания применяется сдвиг работ вправо. Стабильность расписания оценивается с помощью среднего ожидаемого отклонения времени старта работ в результирующем расписании от изначально запланированного времени старта работ. Целью является минимизация этого показателя. В статье вводится понятие надежности работы. Работа определяется как более надежная по сравнению с другой, если положительное отклонение от математического ожидания продолжительности другой работы стохастически доминирует над положительным отклонением этой работы. Мы предлагаем теоретическое обоснование того, почему эвристика, выполняющая сначала более надежные работы, приводит к эффективным решениям задачи планирования, и подтверждаем этот вывод вычислительными экспериментами на различных распределениях вероятностей. Результаты демонстрируют высокую эффективность эвристик, основанных на этом правиле, для повышения стабильности расписания.