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

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

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



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






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


Сиб. электрон. матем. изв., 2019, том 16, страницы 406–426 (Mi semr1065)  

Вычислительная математика

Some positive news on the proportionate open shop problem

Sergey Sevastyanov

Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia

Аннотация: The special case of the open shop problem in which every job has equal length operations on all machines is known as a proportionate open shop problem. The problem is NP-hard in the case of three machines, which makes topical such traditional research directions as designing efficient heuristics and searching for efficiently solvable cases. In this paper we found several new efficiently solvable cases (wider than known) and designed linear-time heuristics with good performance guarantees (better than those known from the literature). Besides, we computed the exact values of the power of preemption for the three-machine problem, being considered as a function of a parameter $\gamma$ (the ratio of two standard lower bounds on the optimum: the machine load and the maximum job length). We also found out that the worst-case power of preemption for the $m$-machine problem asymptotically converges to 1, as $m$ tends to infinity. Finally, we established the exact complexity status of the three-machine problem by presenting a pseudo-polynomial algorithm for its solution.

Ключевые слова: open shop, proportionate, scheduling, makespan minimization, power of preemption, polynomial time heuristic, dynamic programming.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17-07-00513_а
Сибирское отделение Российской академии наук 0314-2019-0014
The work is supported by the Russian Foundation for Basic Research (grant 17-07-00513) and by the program of fundamental scientific researches of the SB RAS (project 0314-2019-0014).


DOI: https://doi.org/10.33048/semi.2019.16.023

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

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

Тип публикации: Статья
УДК: 519.854.2
MSC: 90B35
Поступила 21 декабря 2018 г., опубликована 29 марта 2019 г.
Язык публикации: английский

Образец цитирования: Sergey Sevastyanov, “Some positive news on the proportionate open shop problem”, Сиб. электрон. матем. изв., 16 (2019), 406–426

Цитирование в формате AMSBIB
\RBibitem{Sev19}
\by Sergey~Sevastyanov
\paper Some positive news on the proportionate open shop problem
\jour Сиб. электрон. матем. изв.
\yr 2019
\vol 16
\pages 406--426
\mathnet{http://mi.mathnet.ru/semr1065}
\crossref{https://doi.org/10.33048/semi.2019.16.023}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000462734100001}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr1065
  • http://mi.mathnet.ru/rus/semr/v16/p406

    ОТПРАВИТЬ: 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
  • Просмотров:
    Эта страница:15
    Полный текст:2
    Литература:2

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019