No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths

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 o...

Full description

Saved in:
Bibliographic Details
Published in:Journal of scheduling 2019-02, Vol.22 (1), p.59-68
Main Authors: Billaut, J.-C., Della Croce, F., Salassa, F., T’kindt, V.
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Business and Management
Calculus of Variations and Optimal Control
Optimization
Computer Science
Graph theory
Idling
Job shops
Operations Research
Operations Research/Decision Theory
Optimization
Production scheduling
Schedules
Supply Chain Management
Task scheduling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ( m n 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.
ISSN:1094-6136
1099-1425
DOI:10.1007/s10951-018-0562-4