Approximation algorithms for the parallel flow shop problem

DOI10.1016/j.ejor.2011.08.007zbMath1237.90104OpenAlexW2022186118MaRDI QIDQ421785

Xiandong Zhang, Steef L. van de Velde

Publication date: 14 May 2012

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: http://repub.eur.nl/pub/25743

zbMATH Keywords

schedulingworst-case analysisapproximation algorithmshybrid flow shopparallel flow shop

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (20)

A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process ⋮ Scheduling multiple two-stage flowshops with a deadline ⋮ An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops ⋮ Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches ⋮ Scheduling on multiple two-stage flowshops with a deadline ⋮ An effective Benders decomposition algorithm for solving the distributed permutation flowshop scheduling problem ⋮ A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint ⋮ Scheduling two-stage jobs on multiple flowshops ⋮ A review and classification on distributed permutation flowshop scheduling problems ⋮ A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops ⋮ On scheduling multiple parallel two-stage flowshops with Johnson's rule ⋮ Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments ⋮ A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan ⋮ On Approximation Algorithms for Two-Stage Scheduling Problems ⋮ On scheduling multiple two-stage flowshops ⋮ An FPTAS for the parallel two-stage flowshop problem ⋮ Improved approximation algorithms for two-stage flowshops scheduling problem ⋮ On scheduling inclined jobs on multiple two-stage flowshops ⋮ A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops ⋮ Corrigendum to: ``An FPTAS for the parallel two-stage flowshop problem

Cites Work

• Unnamed Item
• Algorithms for a realistic variant of flowshop scheduling
• Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard
• Minimizing makespan in hybrid flowshops
• Scheduling a two-stage hybrid flow shop with parallel machines at the first stage
• The hybrid flow shop scheduling problem
• Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective
• Optimal two- and three-stage production schedules with setup times included
• Two-Stage, Hybrid Flowshop Scheduling Problem
• Parallel flowshop scheduling using Tabu search
• Analysis of Classes of Heuristics for Scheduling a Two-Stage Flow Shop with Parallel Machines at One Stage

This page was built for publication: Approximation algorithms for the parallel flow shop problem