4423

Автор(ы): 

Автор(ов): 

1

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Решение NP-трудной задачи теории расписаний минимизации суммарного запаздывания

Наименование источника: 

  • Журнал Вычислительной математики и математической физики

Обозначение и номер тома: 

Т.47, №6

Город: 

  • Москва

Издательство: 

  • Наука

Год издания: 

2007

Страницы: 

1087-1099
Аннотация
Рассматривается классическая $NP$-трудная в обычном смысле задача теории расписаний для одного прибора минимизации суммарного запаздывания $1~\mid~\mid~\sum T_j$. Проведен полный анализ$NP$-трудного случая задачи. Предлагается процедура разбиения исходного множества требований на подмножества. Построены алгоритмы нахождения оптимального расписания в зависимости от количества подмножеств. Трудоемкость алгоритмов не превышает$O(n^2\sum p_j)$ операций, где $n$-- количество требований, а$p_j$-- продолжительность обслуживания$j-$го требования, $j=1,2,\dots,n$.

Библиографическая ссылка: 

Лазарев А.А. Решение NP-трудной задачи теории расписаний минимизации суммарного запаздывания // Журнал Вычислительной математики и математической физики. 2007. Т.47, №6. С. 1087-1099.