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

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

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



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






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


Сибирские электронные математические известия, 2022, том 19, выпуск 2, страницы 528–539
DOI: https://doi.org/10.33048/semi.2022.19.044
(Mi semr1519)
 

Дискретная математика и математическая кибернетика

On complexity of two-machine routing propotionate open shop

A. V. Pyatkin, I. D. Chernykh

Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
Список литературы:
Аннотация: In the routing open shop problem a fleet of mobile machines has to traverse the given transportation network, to process immovable jobs located at its nodes and to return back to the initial location in the shortest time possible. The problem is known to be NP-hard even for the simplest case with two machines and two nodes. We consider a special proportionate case of this problem, in which processing time for any job does not depend on a machine. We prove that the problem in this simplified setting is still NP-hard for the same simplest case. To that end, we introduce the new problem we call $2$-$\mathrm{Summing}$ and reduce it to the problem under consideration. We also suggest a $\frac76$-approximation algorithm for the two-machine proportionate problem with at most three nodes.
Ключевые слова: routing open shop, proportionate open shop, complexity, approximation algorithm, standard lower bound, optima localization.
Финансовая поддержка Номер гранта
Министерство науки и высшего образования Российской Федерации FWNF-2022-0019
Российский фонд фундаментальных исследований 20-01-00045
20-07-00458
This research was was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project FWNF-2022-0019), and supported by the Russian Foundation for Basic Research, projects 20-01-00045 and 20-07-00458.
Поступила 21 апреля 2022 г., опубликована 25 августа 2022 г.
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.854.2
MSC: 90B35
Язык публикации: английский
Образец цитирования: A. V. Pyatkin, I. D. Chernykh, “On complexity of two-machine routing propotionate open shop”, Сиб. электрон. матем. изв., 19:2 (2022), 528–539
Цитирование в формате AMSBIB
\RBibitem{PyaChe22}
\by A.~V.~Pyatkin, I.~D.~Chernykh
\paper On complexity of two-machine routing propotionate open shop
\jour Сиб. электрон. матем. изв.
\yr 2022
\vol 19
\issue 2
\pages 528--539
\mathnet{http://mi.mathnet.ru/semr1519}
\crossref{https://doi.org/10.33048/semi.2022.19.044}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4478145}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/semr1519
  • https://www.mathnet.ru/rus/semr/v19/i2/p528
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Статистика просмотров:
    Страница аннотации:91
    PDF полного текста:25
    Список литературы:19
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024