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

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

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



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






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


Дискретн. анализ и исслед. опер., 2019, том 26, номер 4, страницы 56–73 (Mi da937)  

Сложность задачи построения циклического расписания обработки партии идентичных деталей с технологическими ограничениями

А. А. Романоваa, В. В. Сервахb

a Омский гос. университет им. Ф. М. Достоевского, пр. Мира, 55а, 644077 Омск, Россия
b Омский филиал Института математики им. С. Л. Соболева, ул. Певцова, 13, 644099 Омск, Россия

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

Ключевые слова: теория расписаний, циклическое расписание, идентичные детали, теория сложности, полиномиальный алгоритм, псевдополиномиальный алгоритм.

Финансовая поддержка Номер гранта
Сибирское отделение Российской академии наук I.5.1 (проект № 0314–2019–0019)
Работа В. В. Серваха выполнена при финансовой поддержке Программы фундаментальных научных исследований СО РАН № I.5.1 (проект № 0314–2019–0019).


DOI: https://doi.org/10.33048/daio.2019.26.629

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

Тип публикации: Статья
УДК: 519.8
Статья поступила: 27.08.2018
Переработанный вариант: 29.07.2019
Принята к публикации: 28.08.2019

Образец цитирования: А. А. Романова, В. В. Сервах, “Сложность задачи построения циклического расписания обработки партии идентичных деталей с технологическими ограничениями”, Дискретн. анализ и исслед. опер., 26:4 (2019), 56–73

Цитирование в формате AMSBIB
\RBibitem{RomSer19}
\by А.~А.~Романова, В.~В.~Сервах
\paper Сложность задачи построения циклического расписания обработки партии идентичных деталей с технологическими ограничениями
\jour Дискретн. анализ и исслед. опер.
\yr 2019
\vol 26
\issue 4
\pages 56--73
\mathnet{http://mi.mathnet.ru/da937}
\crossref{https://doi.org/10.33048/daio.2019.26.629}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da937
  • http://mi.mathnet.ru/rus/da/v26/i4/p56

    ОТПРАВИТЬ: 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
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:27
    Литература:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020