Domino sequencing: scheduling with state-based sequence-dependent setup times
DOI10.1016/j.orl.2019.04.004zbMath1476.90114OpenAlexW2941444704MaRDI QIDQ2294316
Erik Diessel, Heiner Ackermann
Publication date: 10 February 2020
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2019.04.004
dynamic programmingsequence-dependent setup timesfixed-parameter tractabilityjob familiesEulerian extension problem
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Cites Work
- The third comprehensive survey on scheduling problems with setup times/costs
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- Parameterized complexity of machine scheduling: 15 open problems
- No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths
- On Eulerian extensions and their application to no-wait flowshop scheduling
- The significance of reducing setup times/setup costs
- A survey of scheduling problems with setup times or costs
- Low-complexity algorithms for sequencing jobs with a fixed number of job-classes
- Dynamic Programming Treatment of the Travelling Salesman Problem
- A Dynamic Programming Approach to Sequencing Problems
- The Planar Hamiltonian Circuit Problem is NP-Complete
- On the complexity of edge traversing
- The spanning subgraphs of eulerian graphs
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Arc Routing Problems, Part II: The Rural Postman Problem
- A time- and space-optimal algorithm for the many-visits TSP
- Efficient Algorithms for Eulerian Extension and Rural Postman
- Mathematical Foundations of Computer Science 2004
- Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
- Scheduling
- On the complexity of \(k\)-SAT
This page was built for publication: Domino sequencing: scheduling with state-based sequence-dependent setup times