Журнал вычислительной математики и математической физики
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Ж. вычисл. матем. и матем. физ.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Журнал вычислительной математики и математической физики, 2007, том 47, номер 6, страницы 1087–1098 (Mi zvmmf4603)  
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях)

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

А. А. Лазарев

119991 Москва, ул. Вавилова, 40, ВЦ РАН
PDF полного текста (1773 kB) Список цитирования (5)
Список литературы:
PDF
HTML
Аннотация: Рассматривается классическая NP-трудная в обычном смысле задача теории расписаний для одного прибора минимизации суммарного запаздывания $1\|\sum T_j$. Проведен полный анализ NP-трудного случая задачи. Предлагается процедура разбиения исходного множества требований на подмножества. Построены алгоритмы нахождения оптимального расписания в зависимости от количества подмножеств. Трудоемкость алгоритмов не превышает $O(n^2\sum p_j)$ операций, где $n$ – количество требований, а $p_j$ – продолжительность обслуживания $j$-го требования, $j=1,2,\dots,n$. Библ. 11.
Ключевые слова: теория расписания, один прибор, минимизация суммарного запаздывания, псевдополиномиальные алгоритмы.
Поступила в редакцию: 15.08.2006
Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2007, Volume 47, Issue 6, Pages 1039–1049
DOI: https://doi.org/10.1134/S0965542507060139
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.853.6
Образец цитирования: А. А. Лазарев, “Решение NP-трудной задачи теории расписаний минимизации суммарного запаздывания”, Ж. вычисл. матем. и матем. физ., 47:6 (2007), 1087–1098; Comput. Math. Math. Phys., 47:6 (2007), 1039–1049
Цитирование в формате AMSBIB
\RBibitem{Laz07}
\by А.~А.~Лазарев
\paper Решение NP-трудной задачи теории расписаний минимизации суммарного запаздывания
\jour Ж. вычисл. матем. и матем. физ.
\yr 2007
\vol 47
\issue 6
\pages 1087--1098
\mathnet{http://mi.mathnet.ru/zvmmf4603}
\transl
\jour Comput. Math. Math. Phys.
\yr 2007
\vol 47
\issue 6
\pages 1039--1049
\crossref{https://doi.org/10.1134/S0965542507060139}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-34547255341}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/zvmmf4603
  • https://www.mathnet.ru/rus/zvmmf/v47/i6/p1087
    • Эта публикация цитируется в следующих 5 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024