Approximation algorithms for the multiprocessor open shop scheduling problem

DOI10.1016/S0167-6377(99)00005-XzbMath0967.90049MaRDI QIDQ1306353

Petra Schuurman, Gerhard J. Woeginger

Publication date: 3 September 2001

Published in: Operations Research Letters (Search for Journal in Brave)

zbMATH Keywords

schedulingapproximation algorithmopen shopworst case analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (15)

Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches ⋮ Flexible open shop scheduling problem to minimize makespan ⋮ A new three-machine shop scheduling: complexity and approximation algorithm ⋮ A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops ⋮ A tabu search approach for proportionate multiprocessor open shop scheduling ⋮ Large-scale medical examination scheduling technology based on intelligent optimization ⋮ Minimizing makespan in a two-stage hybrid flow shop scheduling problem with open shop in one stage ⋮ Linear time approximation scheme for the multiprocessor open shop problem ⋮ A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop ⋮ An approximation algorithm for proportionate scheduling in the two-stage hybrid flow shop ⋮ A genetic algorithm for the proportionate multiprocessor open shop ⋮ Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop ⋮ Two-stage open shop scheduling with a bottleneck machine ⋮ A linear time approximation scheme for makespan minimization in an open shop with release dates ⋮ Approximation algorithms for shop scheduling problems with minsum objective

Cites Work

• Unnamed Item
• Scheduling open shops with parallel machines
• Makespan minimization in open shops: A polynomial time approximation scheme
• Worst-case analysis of heuristics for open shops with parallel machines
• Open Shop Scheduling to Minimize Finish Time
• Short Shop Schedules
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: Approximation algorithms for the multiprocessor open shop scheduling problem