Реферат: Рассматривается задача построения расписания работ на одной машине. Каждая работа имеет директивный срок, и ее длительность определяется суммой фиксированной части и некоторой штрафной добавки за нарушение директивного срока. Критерием оптимальности выступает время завершения выполнения всех работ. Устанавливается, что задача NP-трудна в сильном смысле. Когда директивные сроки для всех работ одинаковы, задача остается NP-трудной, но для ее решения удается построить псевдополиномиальный алгоритм.

Библиографическая ссылка: Кононов А.В.
О расписаниях работ на одной машине с длительностями, нелинейно зависящими от времени
Дискретный анализ и исследование операций. 1995. Т.2. №1. С.21-35.

Даты:

Поступила в редакцию:

13 янв. 1994 г.

Идентификаторы БД: Нет идентификаторов

Цитирование в БД: Пока нет цитирований