An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint

DOI10.1016/j.ipl.2004.03.004zbMath1178.68097OpenAlexW1999266123MaRDI QIDQ2390265

Joachim Breit

Publication date: 21 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.03.004

zbMATH Keywords

worst-case analysisapproximation algorithmsflow shop scheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (18)

A PTAS for non-resumable open shop scheduling with an availability constraint ⋮ Mixed integer programming formulations for two-machine flow shop scheduling with an availability constraint ⋮ Heuristics for two-machine flowshop scheduling with setup times and an availability constraint ⋮ Two-machine flow shop scheduling with an operator non-availability period to minimize makespan ⋮ An approximation scheme for two-machine flowshop scheduling with setup times and an availability constraint ⋮ An improved algorithm for the two machine flow shop problem with several availability constraints ⋮ The two-stage assembly flow shop scheduling with an availability constraint: worst case analysis ⋮ Approximation results for flow shop scheduling problems with machine availability constraints ⋮ A polynomial-time approximation scheme for the two machine flow shop problem with several availability constraints ⋮ An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs ⋮ A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint ⋮ Setting a common due date in a constrained flowshop: a variable neighbourhood search approach ⋮ Flow shops with machine maintenance: ordered and proportionate cases ⋮ Two-machine flow shop and open shop scheduling problems with a single maintenance window ⋮ Approximation results for the two-machine job shop under limited machine availability ⋮ A (\(\frac {4}{3}\))-approximation algorithm for a special case of the two machine flow shop problem with several availability constraints ⋮ Scheduling permutation flowshops with initial availability constraint: Analysis of solutions and constructive heuristics ⋮ Optimality of Jackson's permutations with respect to limited machine availability

Cites Work

• Machine scheduling with availability constraints
• Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint
• An improved heuristic for two-machine flowshop scheduling with an availability constraint
• Two-machine flowshop scheduling with consecutive availability constraints
• Scheduling with limited machine availability
• Optimal two- and three-stage production schedules with setup times included
• Two-machine flow shops with limited machine availability

This page was built for publication: An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint