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

zbMATH Keywords

dynamic programmingsequence-dependent setup timesfixed-parameter tractabilityjob familiesEulerian extension problem

Mathematics Subject Classification ID

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)

A hierarchical approach for solving an integrated packing and sequence-optimization problem in production of glued laminated timber ⋮ Scheduling a proportionate flow shop of batching machines

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