On Eulerian extensions and their application to no-wait flowshop scheduling

DOI10.1007/s10951-011-0241-1zbMath1280.90050OpenAlexW2048832818WikidataQ57399760 ScholiaQ57399760MaRDI QIDQ2434285

Wiebke Höhn, Tobias Jacobs, Nicole Megow

Publication date: 5 February 2014

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

Full work available at URL: https://doi.org/10.1007/s10951-011-0241-1

zbMATH Keywords

complexityapproximation algorithmscontinuous castingno-wait flowshopmachine idle timesEulerian extensions

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (11)

Rural postman parameterized by the number of components of required edges ⋮ Integrated Charge Batching and Casting Width Selection at Baosteel ⋮ A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem ⋮ Finding even subgraphs even faster ⋮ Editing to Eulerian graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A survey of scheduling problems with no-wait in process ⋮ Using shortcut edges to maximize the number of triangles in graphs ⋮ Domino sequencing: scheduling with state-based sequence-dependent setup times ⋮ From Few Components to an Eulerian Graph by Adding Arcs ⋮ No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths

Cites Work

• Unnamed Item
• Compact scheduling of zero-one time operations in multi-stage systems
• No-wait flexible flowshop scheduling with no-idle machines
• Some no-wait shops scheduling problems: Complexity aspect
• Time complexity and linear-time approximation of the ancient two-machine flow shop
• New polynomially solvable classes and a new heuristic for the traveling salesman problem and its generalization
• The traveling salesman problem and its variations
• Routing problems: A bibliography
• Simple algorithms for gilmore-gomory's traveling salesman and related problems
• The Three-Machine No-Wait Flow Shop is NP-Complete
• Complexity of Scheduling Shops with No Wait in Process
• On general routing problems
• A fundamental problem in vehicle routing
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling the production of rolling ingots: industrial context, model, and solution method
• Arc Routing Problems, Part II: The Rural Postman Problem
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• 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
• NP-hardness of compact scheduling in simplified open and flow shops.

This page was built for publication: On Eulerian extensions and their application to no-wait flowshop scheduling