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

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

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



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






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


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

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

On the two-machine routing open shop on a tree with preemption allowed

P. M. Agzyamovaa, I. D. Chernykhb

a Novosibirsk State University, 1, Pirogova str., Novosibirsk, 630090, Russia
b Sobolev Institute of Mathematics, 4, Koptyuga ave., Novosibirsk, 630090, Russia
Список литературы:
Аннотация: The routing open shop problem is a natural generalization of the metric TSP and a classical open shop scheduling problem. Jobs are located at the nodes of a given transportation network, and mobile machines have to perform operations on those jobs while traveling over the edges. Machines are obligated to return to the initial location after completing all operations. The goal is to minimize the makespan. We consider the two-machine routing open shop on a tree with preemption in a general setting, where travel times are machine- and direction-dependent. For this problem we describe a wide polynomially solvable special case, for which the optimal makespan is guaranteed to coincide with the standard lower bound. To that end, we introduce a new problem setting with restricted preemption.
Ключевые слова: shop scheduling, routing open shop, restricted preemption, individual travel times, asymmetric transportation network, polynomially solvable cases, standard lower bound.
Финансовая поддержка Номер гранта
Министерство науки и высшего образования Российской Федерации FWNF-2022-0019
Российский фонд фундаментальных исследований 20-01-00045
20-07-00458
This research 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 г., опубликована 26 августа 2022 г.
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.854.2
MSC: 90B35
Язык публикации: английский
Образец цитирования: P. M. Agzyamova, I. D. Chernykh, “On the two-machine routing open shop on a tree with preemption allowed”, Сиб. электрон. матем. изв., 19:2 (2022), 548–561
Цитирование в формате AMSBIB
\RBibitem{AgzChe22}
\by P.~M.~Agzyamova, I.~D.~Chernykh
\paper On the two-machine routing open shop on a tree with preemption allowed
\jour Сиб. электрон. матем. изв.
\yr 2022
\vol 19
\issue 2
\pages 548--561
\mathnet{http://mi.mathnet.ru/semr1520}
\crossref{https://doi.org/10.33048/semi.2022.19.046}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4478147}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/semr1520
  • https://www.mathnet.ru/rus/semr/v19/i2/p548
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Статистика просмотров:
    Страница аннотации:83
    PDF полного текста:21
    Список литературы:20
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024