A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan

DOI10.1007/978-3-319-39817-4_22zbMath1475.90024OpenAlexW2482316384MaRDI QIDQ4632189

Guo-Hui Lin, Weitian Tong, Randy Goebel, Eiji Miyano

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-39817-4_22

zbMATH Keywords

multiprocessor schedulingmakespanlinear programpolynomial-time approximation schemeflow-shop scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items

Scheduling two-stage jobs on multiple flowshops ⋮ A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops ⋮ Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments ⋮ On Approximation Algorithms for Two-Stage Scheduling Problems ⋮ On scheduling inclined jobs on multiple two-stage flowshops

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for the parallel flow shop problem
• An FPTAS for the parallel two-stage flowshop problem
• A new polynomial-time algorithm for linear programming
• Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard
• Approximability of flow shop scheduling
• Minimizing makespan in hybrid flowshops
• Scheduling a two-stage hybrid flow shop with parallel machines at the first stage
• A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem
• The hybrid flow shop scheduling problem
• Optimal two- and three-stage production schedules with setup times included
• Two-Stage, Hybrid Flowshop Scheduling Problem
• Algorithms for Scheduling Independent Tasks
• Flowshop and Jobshop Schedules: Complexity and Approximation
• The Complexity of Flowshop and Jobshop Scheduling
• A New Heuristic for Three-Machine Flow Shop Scheduling
• Short Shop Schedules
• Analysis of Classes of Heuristics for Scheduling a Two-Stage Flow Shop with Parallel Machines at One Stage
• Bounds for Certain Multiprocessing Anomalies