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

DOI10.1007/s10951-018-0562-4zbMath1425.90040arXiv1707.02849OpenAlexW2964319900WikidataQ129894466 ScholiaQ129894466MaRDI QIDQ2327957

Fabio Salassa, Vincent T'kindt, Jean-Charles Billaut, Frederico Della Croce

Publication date: 8 October 2019

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.02849

zbMATH Keywords

Hamiltonian pathEulerian pathdominoesnumerical matching with target sumsno-idle/no-wait shop scheduling

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (4)

Relationship between common objective functions, idle time and waiting time in permutation flow shop scheduling ⋮ No-idle parallel-machine scheduling of unit-time jobs with a small number of distinct release dates and deadlines ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Domino sequencing: scheduling with state-based sequence-dependent setup times

Cites Work

• Unnamed Item
• On no-wait and no-idle flow shops with makespan criterion
• The flow shop problem with no-idle constraints: a review and approximation
• Eulerian graphs and related topics. Part 1, Volume 2
• A survey of scheduling problems with no-wait in process
• On Eulerian extensions and their application to no-wait flowshop scheduling
• Optimal two- and three-stage production schedules with setup times included
• The Three-Machine No-Wait Flow Shop is NP-Complete
• The Complexity of Flowshop and Jobshop Scheduling
• Flowshop/no-idle or no-wait scheduling to minimize the sum of completion times
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• On the Flow-Shop Sequencing Problem with No Wait in Process^†
• A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process
• On scheduling with the non-idling constraint
• NP-hardness of compact scheduling in simplified open and flow shops.

This page was built for publication: No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths