Advertisement
Published in:
2019 | OriginalPaper | Chapter
Routing Open Shop with Two Nodes, Unit Processing Times and Equal Number of Jobs and Machines
Authors : Mikhail Golovachev, Artem V. Pyatkin
Published in: Mathematical Optimization Theory and Operations Research
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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=K_2\) 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.