Том 2, номер 1, 1995 г., Стр. 21-35
УДК 519.8
А. В. Кононов
О расписаниях работ на одной машине с длительностями, нелинейно зависящими от времени
Аннотация:
Рассматривается задача построения расписания работ на одной машине. Каждая работа имеет директивный срок, и ее длительность определяется суммой фиксированной части и некоторой штрафной добавки за нарушение директивного срока. Критерием оптимальности выступает время завершения выполнения всех работ. Устанавливается, что задача NP-трудна в сильном смысле. Когда директивные сроки для всех работ одинаковы, задача остается NP-трудной, но для ее решения удается построить псевдополиномиальный алгоритм.
Библиогр. 5.
Кононов А. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 13 января 1994 г.
