A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing

Antonina P. Khramova () and Ilya Chernykh ()
Additional contact information
Antonina P. Khramova: Sobolev Institute of Mathematics
Ilya Chernykh: Sobolev Institute of Mathematics

Journal of Scheduling, 2021, vol. 24, issue 4, No 3, 405-412

Abstract: Abstract The two-machine open shop problem was proved to be solvable in linear time by Teofilo Gonzalez and Sartaj Sahni in 1976. Several algorithms for solving that problem have been proposed since that time. We introduce another optimal algorithm for that classical problem with an interesting property: it allows to process jobs in almost arbitrary order, unlike the Gohzalez–Sahni algorithm where jobs have to be partitioned into two specific subsets. This new algorithm in turn helps us to solve a much more general problem: the easy-TSP version of the routing open shop with a variable depot, in which unmovable jobs are located in the nodes of a transportation network (with optimal route known), and mobile machines have to travel between the nodes to process jobs in the open shop environment. The common initial location of the machines is not fixed but has to be chosen, and all machines have to return to that location—the depot—to minimize finish time. We also consider the generalization of this problem in which travel times are individual for each machine. This contributes to the discussion on the differences between different scheduling models with transportation delays: classic transportation delays (in our terms, with no depot at all), with a variable depot, and with a fixed depot. It turns out that the depot makes the difference and makes the problem harder to solve.

Keywords: Open shop; Problems with transportation delays; Routing open shop; Unrelated travel times; Variable depot; Polynomially solvable subcases (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-021-00694-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:24:y:2021:i:4:d:10.1007_s10951-021-00694-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-021-00694-7

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().