Минимизация суммарного взвешенного времени обслуживания требований с неопределенными данными: метод, основанный на устойчивости

Исследуется задача построения расписания для одного прибора при неопределенных исходных данных: длительность обслуживания требования может оказаться равной любому действительному числу из заданного отрезка. Критерий оптимальности – минимизация суммарного взвешенного времени обслуживания $n$ требований. В качестве решения задачи с неопределенными данными рассматривается минимальное доминирующее множество перестановок требований, содержащее хотя бы одну оптимальную перестановку для каждой возможной реализации длительностей обслуживания требований. Для реализации оптимальной или близкой к оптимальной перестановки требований строится перестановка с наибольшим объемом многогранника устойчивости, который является подмножеством области устойчивости. Для поиска перестановки с наибольшим многогранником устойчивости разработан метод ветвей и границ. Если несколько перестановок имеют наибольший объем многогранника устойчивости, то среди них выбирается перестановка, удовлетворяющая одному из двух простых эвристических правил. Качество построенных перестановок (насколько они близки к фактически оптимальным перестановкам) и эффективность разработанных программ (среднее время работы процессора при решении одного примера) продемонстрированы на множестве случайно сгенерированных примеров с количеством требований, заключенным в пределах $5\le n\le100$.

Статья представлена к публикации членом редколлегии: А. А. Лазарев