Комбинаторная сложность составления расписаний для работ с простым линейным ростом длительностей

Изучаются задачи теории расписаний, в которых длительность операций прямо пропорциональна времени постановки операции на выполнение. Рассматриваются системы с параллельными машинами и многооперационные системы. Устанавливается NP-трудность для ряда задач с такими критериями оптимальности: минимизация общего времени выполнения всех работ, минимизация суммарного времени выполнения всех работ, минимизация максимального запаздывания.
Библиогр. 11