Approximation algorithms for two-machine flow shop scheduling with batch setup times

DOI10.1007/BF01585875zbMath0920.90070OpenAlexW2025039409MaRDI QIDQ1290646

Bo Chen, Vitaly A. Strusevich, Chris N. Potts

Publication date: 3 June 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585875

zbMATH Keywords

approximation algorithmmakespanworst-case performanceNP-hardheuristic algorithmstwo-machine flow shopindependent jobsbatch setup time

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, Unbounded parallel-batch scheduling with family jobs and delivery coordination, Scheduling with batching: A review, Integrated problem of soaking pit heating and hot rolling scheduling in steel plants, Flow shop scheduling to minimize the total completion time with a permanently present operator: Models and ant colony optimization metaheuristic, Group technology approach to the open shop scheduling problem with batch setup times

Cites Work

• Two-machine shop scheduling problems with batch processing
• Optimal two- and three-stage production schedules with setup times included
• Integrating Scheduling with Batching and Lot-Sizing: A Review of Algorithms and Complexity
• Open Shop Scheduling to Minimize Finish Time
• On the Complexity of Scheduling with Batch Setup Times
• A Better Heuristic for Preemptive Parallel Machine Scheduling with Batch Setup Times
• Analysis of Heuristics for Preemptive Parallel Machine Scheduling with Batch Setup Times