1. Объединенный институт проблем информатики Минск, Сурганова, 6

УДК: 519.8

Реферат:

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