Многогранник и область оптимальности для обслуживания на одном приборе множества требований с неопределенными длительностями

Abstract

Рассматривается задача минимизации суммарного (среднего) взвешенного времени завершения выполнения работником запланированных работ при условии, что при составлении расписания известны только нижняя и верхняя границы возможной длительности выполнения каждой из запланированных работ. Разработаны алгоритмы, позволяющие вычислять относительный периметр области оптимальности для фиксированной перестановки. Проведенные вычислительные эксперименты показали, что перестановки с наибольшим значением относительного периметра области оптимальности имеют наименьшую относительную погрешность по сравнению с перестановками, построенными известными алгоритмами. Это дает основание предполагать, что такие перестановки более эффективны для решения рассматриваемой задачи, чем перестановки, которые получаются в результате применения опубликованных ранее алгоритмов.