Paper Info
Title
No-idle, no-wait: when shop scheduling meets dominoes, eulerian and hamiltonian paths.
Abstract
In shop scheduling, several applications require that some components perform consecutively. We refer to “no-idle schedules” if machines are required to operate with no inserted idle time and to “no-wait schedules” if tasks cannot wait between the end of an operation and the start of the following one. We consider here no-idle/no-wait shop scheduling problems with makespan as the performance measure and determine related complexity results. We first analyse the two-machine no-idle/no-wait flow shop problem and show that it is equivalent to a special version of the game of dominoes which is polynomially solvable by tackling an Eulerian path problem on a directed graph. We present for this problem an O(n) exact algorithm. As a by-product, we show that the Hamiltonian path problem on a digraph G(V, A) with a special structure (where any two vertices i and j either have all successors in common or have no common successors) reduces to the two-machine no-idle/no-wait flow shop problem. Correspondingly, we provide a new polynomially solvable special case of the Hamiltonian path problem. Then, we show that also the m-machine no-idle/no-wait flow shop problem is polynomially solvable and provide an (O(mn log n)) exact algorithm. Finally, we prove that the decision versions of the two-machine job shop problem and the two-machine open shop problem are NP-complete in the strong sense.
Year
Venue
Field
2017
Journal of Scheduling
Open shop,Discrete mathematics,Combinatorics,Job shop scheduling,Exact algorithm,Job shop,Flow shop scheduling,Directed graph,Eulerian path,Hamiltonian path problem,Mathematics
DocType
Volume
Citations 
Journal
abs/1707.02849
0
PageRank 
References 
Authors
0.34
7
4
Name
Order
Citations
PageRank
Jean-charles Billaut127321.65
Federico Della Croce239941.60
Fabio Salassa3569.79
Vincent T'kindt420321.04