1. Белорусский государственный университет Минск

УДК: 519.95

Реферат:

Для задачи Om ? Cmax существует гипотеза, что в худшем случае для любого плотного распи-сания время завершения выполнения последней работы не более чем в 2 – 1/m раз превосходит время завершения в оптимальном расписании. Предлагается подход, который позволяет доказать гипотезу для случая m ? 9 и некоторых специальных случаев.