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

DOI10.1007/978-3-319-39817-4_22MaRDI QIDQ4632189zbMATH OpenOpenAlexFDO

Authors Weitian Tong, Randy Goebel, Guohui Lin, 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

flow-shop schedulinglinear programmakespanmultiprocessor schedulingpolynomial-time approximation scheme

Mathematics Subject Classification ID

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

Recommendations

• An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops
• A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops
• scientific article; zbMATH DE number 1500536
• An FPTAS for the parallel two-stage flowshop problem
• Approximation algorithms for the parallel flow shop problem

Cites work

• A New Heuristic for Three-Machine Flow Shop Scheduling
• A new polynomial-time algorithm for linear programming
• A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem
• Algorithms for Scheduling Independent Tasks
• An FPTAS for the parallel two-stage flowshop problem
• Analysis of Classes of Heuristics for Scheduling a Two-Stage Flow Shop with Parallel Machines at One Stage
• Approximability of flow shop scheduling
• Approximation algorithms for the parallel flow shop problem
• Bounds for Certain Multiprocessing Anomalies
• Flowshop and Jobshop Schedules: Complexity and Approximation
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1500536 (Why is no real title available?)
• scientific article; zbMATH DE number 2146482 (Why is no real title available?)
• Minimizing makespan in hybrid flowshops
• Optimal two- and three-stage production schedules with set-up time included
• Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard
• Scheduling a two-stage hybrid flow shop with parallel machines at the first stage
• Short Shop Schedules
• The Complexity of Flowshop and Jobshop Scheduling
• The hybrid flow shop scheduling problem
• Two-Stage, Hybrid Flowshop Scheduling Problem

Cited in

(7)

• Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments
• On scheduling inclined jobs on multiple two-stage flowshops
• Scheduling two-stage jobs on multiple flowshops
• A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops
• An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops
• On Approximation Algorithms for Two-Stage Scheduling Problems
• A polynomial-time approximation scheme for an arbitrary number of parallel identical multi-stage flow-shops

This page was built for publication: A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632189)