A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem

DOI10.1016/S0304-3975(98)00157-1zbMath0943.68009WikidataQ127905455 ScholiaQ127905455MaRDI QIDQ1566707

Gerhard J. Woeginger, Petra Schuurman

Publication date: 4 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

schedulingapproximation algorithmflow shopjob shopworst-case analysispolynomial time approximation scheme

Mathematics Subject Classification ID

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

Related Items (20)

Optimizing resource speed for two-stage real-time tasks ⋮ 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 ⋮ Optimal scheduling of a two-stage hybrid flow shop ⋮ A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops ⋮ Two-stage proportionate flexible flow shop to minimize the makespan ⋮ On scheduling multiple parallel two-stage flowshops with Johnson's rule ⋮ Scheduling of inventory releasing jobs to minimize a regular objective function of delivery times ⋮ Approximating the least core value and least core of cooperative games with supermodular costs ⋮ Grouping techniques for scheduling problems: simpler and faster ⋮ A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan ⋮ A PTAS for a particular case of the two-machine flow shop with limited machine availability ⋮ The minimum feasible tileset problem ⋮ An FPTAS for the parallel two-stage flowshop problem ⋮ The hybrid flow shop scheduling problem ⋮ A hybrid two-stage flexible flowshop scheduling problem with m identical parallel machines and a burn-in processor separately ⋮ Approximation schemes for scheduling and covering on unrelated machines ⋮ Malleable scheduling for flows of jobs and applications to MapReduce ⋮ A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops ⋮ Complexity and algorithms for two-stage flexible flowshop scheduling with availability constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Scheduling algorithms for flexible flowshops: Worst and average case performance
• Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard
• Minimizing makespan in hybrid flowshops
• Optimal two- and three-stage production schedules with setup times included
• Integer Programming with a Fixed Number of Variables
• Two-Stage, Hybrid Flowshop Scheduling Problem
• Algorithms for Scheduling Independent Tasks
• The Complexity of Flowshop and Jobshop Scheduling
• Improved Approximation Algorithms for Shop Scheduling Problems
• Short Shop Schedules
• Analysis of Classes of Heuristics for Scheduling a Two-Stage Flow Shop with Parallel Machines at One Stage
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem