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

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

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



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






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


Дискретн. анализ и исслед. опер., сер. 1, 2006, том 13, номер 3, страницы 83–102 (Mi da37)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

О некоторых свойствах оптимальных расписаний в задаче Джонсона с прерываниями

С. В. Севастьянов, Д. А. Чемисова, И. Д. Черных

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Исследуются свойства оптимальных расписаний в NP-трудной задаче Джонсона с разрешением прерываний операций. В частности, доказано, что длина оптимального расписания всегда совпадает с суммарной длиной некоторого подмножества операций. С использованием найденных свойств показано, что оптимальное расписание любого примера может быть построено жадным алгоритмом (при подходящем задании приоритетов операций). Впервые описан алгоритм точного решения указанной задачи. Показано, что число прерываний в любом жадном расписании (а следовательно, и в оптимальном) не превосходит числа операций, что существенно лучше известных оценок числа прерываний в оптимальном расписании.
Библ. 4.

Полный текст: PDF файл (363 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2007, 1:3, 386–397

Реферативные базы данных:


Образец цитирования: С. В. Севастьянов, Д. А. Чемисова, И. Д. Черных, “О некоторых свойствах оптимальных расписаний в задаче Джонсона с прерываниями”, Дискретн. анализ и исслед. опер., сер. 1, 13:3 (2006), 83–102; J. Appl. Industr. Math., 1:3 (2007), 386–397

Цитирование в формате AMSBIB
\RBibitem{SevCheChe06}
\by С.~В.~Севастьянов, Д.~А.~Чемисова, И.~Д.~Черных
\paper О некоторых свойствах оптимальных расписаний в~задаче Джонсона с~прерываниями
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2006
\vol 13
\issue 3
\pages 83--102
\mathnet{http://mi.mathnet.ru/da37}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2289373}
\zmath{https://zbmath.org/?q=an:1249.90078}
\transl
\jour J. Appl. Industr. Math.
\yr 2007
\vol 1
\issue 3
\pages 386--397
\crossref{https://doi.org/10.1134/S1990478907030143}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-34548679863}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da37
  • http://mi.mathnet.ru/rus/da/v13/s1/i3/p83

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Д. А. Чемисова, “О свойствах оптимальных расписаний в задаче flow shop с прерываниями и произвольным регулярным критерием”, Дискретн. анализ и исслед. опер., 16:3 (2009), 74–98  mathnet  mathscinet  zmath
    2. Sevastyanov S.V. Chemisova D.A. Chernykh I.D., “On Some Properties of Optimal Schedules in the Job Shop Problem with Preemption and an Arbitrary Regular Criterion”, Ann. Oper. Res., 213:1 (2014), 253–270  crossref  mathscinet  zmath  isi  elib  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:599
    Полный текст:147
    Литература:37
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020