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

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

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



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






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


Дискретн. анализ и исслед. опер., 2009, том 16, номер 1, страницы 3–36 (Mi da559)  

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

Структурные свойства оптимальных расписаний с прерываниями операций

Ф. Баптистa, Ж. Карльеa, А. В. Кононовb, М. Керанc, С. В. Севастьяновbd, М. Свириденкоe

a Université de Technologie de Compiégne
b Институт математики им. С. Л. Соболева СО РАН
c Faculty of Commerce and Business Administration, University of British Columbia
d Новосибирский государственный университет
e IBM T. J. Watson Research Center

Аннотация: Рассматриваются задачи на построение расписаний с разрешением прерываний операций, в которых каждая операция может быть прервана и возобновлена позднее без какого-либо штрафа. Исследуются фундаментальные свойства оптимальных решений этих задач такие, как существование оптимального решения (при условии, что множество допустимых решений непусто), конечность/полиномиальность числа прерываний в оптимальном решении, существование оптимального решения с прерываниями лишь в целочисленных точках и т.п. Такие теоретические вопросы представляют и практический интерес, поскольку структурные свойства оптимальных решений могут быть использованы для уменьшения пространства поиска в практических задачах на построение расписаний. В статье даются ответы на некоторые из этих фундаментальных вопросов для достаточно общей модели теории расписаний (включающей в качестве её частных случаев классические модели на параллельных машинах, цеховые модели и модели календарного планирования с ресурсными ограничениями) и для широкого множества целевых функций, включающего почти все известные. Для двух специальных классов целевых функций (включающих, тем не менее, все классические целевые функции) доказывается существование оптимального решения, обладающего специальной “рациональной” структурой. Важным следствием этого свойства является то, что распознавательные версии многих известных задач теории расписаний с допущением прерываний операций принадлежат классу NP. Библиогр. 13.

Ключевые слова: теория расписаний, прерываниe, оптимальное расписаниe.

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

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2010, 4:4, 455–474

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

УДК: 519.854.2
Статья поступила: 13.10.2008
Переработанный вариант: 12.12.2008

Образец цитирования: Ф. Баптист, Ж. Карлье, А. В. Кононов, М. Керан, С. В. Севастьянов, М. Свириденко, “Структурные свойства оптимальных расписаний с прерываниями операций”, Дискретн. анализ и исслед. опер., 16:1 (2009), 3–36; J. Appl. Industr. Math., 4:4 (2010), 455–474

Цитирование в формате AMSBIB
\RBibitem{BapCarKon09}
\by Ф.~Баптист, Ж.~Карлье, А.~В.~Кононов, М.~Керан, С.~В.~Севастьянов, М.~Свириденко
\paper Структурные свойства оптимальных расписаний с~прерываниями операций
\jour Дискретн. анализ и исслед. опер.
\yr 2009
\vol 16
\issue 1
\pages 3--36
\mathnet{http://mi.mathnet.ru/da559}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2543160}
\zmath{https://zbmath.org/?q=an:1249.90066}
\transl
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 4
\pages 455--474
\crossref{https://doi.org/10.1134/S1990478910040010}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-78650066330}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da559
  • http://mi.mathnet.ru/rus/da/v16/i1/p3

    ОТПРАВИТЬ: 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. Baptiste Ph., Cartier J., Kononov A., Queyranne M., Sevastyanov S., Sviridenko M., “Properties of optimal schedules in preemptive shop scheduling”, Discrete Appl. Math., 159:5 (2011), 272–280  crossref  mathscinet  zmath  isi  elib  scopus
    3. Cheng T.C.E., Lin B.M.T., Huang H.L., “Resource-constrained flowshop scheduling with separate resource recycling operations”, Comput. Oper. Res., 39:6 (2012), 1206–1212  crossref  mathscinet  zmath  isi  elib  scopus
    4. Baptiste Ph., Carlier J., Kononov A., Queyranne M., Sevastyanov S., Sviridenko M., “Integer Preemptive Scheduling on Parallel Machines”, Oper. Res. Lett., 40:6 (2012), 440–444  crossref  mathscinet  zmath  isi  elib  scopus
    5. Р. Ю. Симанчёв, Н. Ю. Шерешик, “Целочисленные модели обслуживания требований одним прибором с прерываниями”, Дискретн. анализ и исслед. опер., 21:4 (2014), 89–101  mathnet  mathscinet
    6. Gawiejnowicz S., Kononov A., “Isomorphic Scheduling Problems”, Ann. Oper. Res., 213:1 (2014), 131–145  crossref  mathscinet  zmath  isi  elib  scopus
    7. Н. Ю. Шерешик, “Релаксации многогранника оптимальных расписаний обслуживания требований одним прибором с прерываниями”, Дискретн. анализ и исслед. опер., 22:6 (2015), 78–90  mathnet  crossref  mathscinet  elib
    8. Coffman Jr. E. G., Ng C.T., Timkovsky V.G., “How Small Are Shifts Required in Optimal Preemptive Schedules?”, J. Sched., 18:2 (2015), 155–163  crossref  mathscinet  zmath  isi  elib  scopus
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:683
    Полный текст:138
    Литература:68
    Первая стр.:22
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020