МИНИМИЗАЦИЯ СУММЫ ВЗВЕШЕННЫХ МОМЕНТОВ ЗАВЕРШЕНИЯ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ИНТЕРВАЛЬНЫМИ ДЛИТЕЛЬНОСТЯМИ

Аннотация

Исследуется задача построения расписания с минимальной суммой взвешенных моментов завершения обслуживания n требований одним прибором при условии, что известны нижние и верхние границы возможных значений длительностей операций по обслуживанию требований. Доказывается необходимое и достаточное условие, при выполнении которого требование J_u доминирует требование J_v (иными словами, для каждого множества возможных длительностей операций существует оптимальная перестановка n требований, в которой J_u предшествует J_v). Приводится критерий существования единственной перестановки n требований, которая является оптимальной при любых возможных длительностях операций. Доказывается необходимое и достаточное условие, при котором любая перестановка n требований является единственной оптимальной перестановкой при некотором множестве возможных длительностей операций. Полученные условия проверяются за полиномиальное от n время.