An FPTAS for the parallel two-stage flowshop problem

DOI10.1016/j.tcs.2016.04.046zbMath1356.68023OpenAlexW2409994095MaRDI QIDQ507441

Jueliang Hu, Jianming Dong, Xueshi Wang, Weitian Tong, Taibo Luo, Yin-Feng Xu, Guo-Hui Lin

Publication date: 6 February 2017

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.04.046

zbMATH Keywords

dynamic programmingmultiprocessor schedulingmakespanfully polynomial-time approximation schemetwo-stage flowshop scheduling

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) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (18)

Scheduling multiple two-stage flowshops with a deadline ⋮ An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops ⋮ 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 ⋮ Maximizing total early work in a distributed two‐machine flow‐shop ⋮ 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 ⋮ 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
• Unnamed Item
• Unnamed Item
• Approximation algorithms for the parallel flow shop problem
• 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

This page was built for publication: An FPTAS for the parallel two-stage flowshop problem