Routing open shop with two nodes, unit processing times and equal number of jobs and machines

Mikhail Golovachev, Artem V. Pyatkin

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

2 Цитирования (Scopus)

Аннотация

In the Routing Open Shop problem n jobs are located in the nodes of an edge-weighted graph G=(V,E) and m machines must process all jobs in such a way that each machine processes only one job at a time and each job is processed by only one machine at a time. The goal is to minimize the makespan, i. e. the time when the last machine comes back to the initial node called a depot (at the beginning all machines are in the depot). This problem is NP-hard even when the graph contains only two nodes. In this paper we consider the case of G=K2 when all processing times and travel times are unit. We pose the conjecture that the problem is polynomially solvable in this case, i.e. that the makespan depends only on the number of machines and the loads of the nodes and can be calculated in time O(log mn). We provide some bounds on the makespan for the case of m=n depending on the loads distribution.

Язык оригиналаанглийский
Название основной публикацииMathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings
РедакторыMichael Khachay, Panos Pardalos, Yury Kochetov
ИздательSpringer-Verlag GmbH and Co. KG
Страницы264-276
Число страниц13
ISBN (печатное издание)9783030226282
DOI
СостояниеОпубликовано - 1 янв 2019
Событие18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019 - Ekaterinburg, Российская Федерация
Продолжительность: 8 июл 201912 июл 2019

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11548 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019
СтранаРоссийская Федерация
ГородEkaterinburg
Период08.07.201912.07.2019

Fingerprint Подробные сведения о темах исследования «Routing open shop with two nodes, unit processing times and equal number of jobs and machines». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Golovachev, M., & Pyatkin, A. V. (2019). Routing open shop with two nodes, unit processing times and equal number of jobs and machines. В M. Khachay, P. Pardalos, & Y. Kochetov (Ред.), Mathematical Optimization Theory and Operations Research - 18th International Conference, MOTOR 2019, Proceedings (стр. 264-276). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11548 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-030-22629-9_19