An FPTAS for the parallel two-stage flowshop problem

DOI10.1016/J.TCS.2016.04.046zbMATH Open1356.68023OpenAlexW2409994095MaRDI QIDQ507441FDOQ507441

Authors: Jianming Dong, Weitian Tong, Taibo Luo, Xueshi Wang, Jueliang Hu, Yinfeng Xu, Guohui 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

Recommendations

• A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops
• Approximation algorithms for the parallel flow shop problem
• A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem
• Approximation algorithms for two-stage flexible flow shop scheduling
• An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops

zbMATH Keywords

dynamic programmingmakespanmultiprocessor schedulingfully polynomial-time approximation schemetwo-stage flowshop scheduling

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• The hybrid flow shop scheduling problem
• Title not available (Why is that?)
• Optimal two- and three-stage production schedules with set-up time included
• Algorithms for Scheduling Independent Tasks
• The Complexity of Flowshop and Jobshop Scheduling
• Two-Stage, Hybrid Flowshop Scheduling Problem
• Short Shop Schedules
• 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
• Flowshop and Jobshop Schedules: Complexity and Approximation
• A New Heuristic for Three-Machine Flow Shop Scheduling
• Title not available (Why is that?)
• Analysis of Classes of Heuristics for Scheduling a Two-Stage Flow Shop with Parallel Machines at One Stage
• A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem

Cited In (24)

• A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops
• An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops
• A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint
• Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments
• On scheduling multiple two-stage flowshops
• On Approximation Algorithms for Two-Stage Scheduling Problems
• FPTAS for the two identical parallel machine problem with a single operator under the free changing mode
• Corrigendum to: ``An FPTAS for the parallel two-stage flowshop problem
• Scheduling on multiple two-stage flowshops with a deadline
• Approximation algorithms for the parallel flow shop problem
• Maximizing total early work in a distributed two‐machine flow‐shop
• Scheduling multiple two-stage flowshops with a deadline
• On scheduling inclined jobs on multiple two-stage flowshops
• A review and classification on distributed permutation flowshop scheduling problems
• A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan
• A FPTAS for a two-stage hybrid flow shop problem and optimal algorithms for identical jobs
• Improved approximation algorithms for two-stage flowshops scheduling problem
• On scheduling multiple parallel two-stage flowshops with Johnson's rule
• A multi-stage parallel-processor flowshop problem with minimum flowtime
• Scheduling two-stage jobs on multiple flowshops
• An effective Benders decomposition algorithm for solving the distributed permutation flowshop scheduling problem
• Applying Johnson's rule in scheduling multiple parallel two-stage flowshops
• A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops
• A polynomial-time approximation scheme for an arbitrary number of parallel identical multi-stage flow-shops

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

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