Multistage hybrid flowshop scheduling with identical jobs and uniform parallel machines
The single-stage scheduling problem to minimize the makespan of identical jobs with general release times on uniform parallel machines is known to be solvable in polynomial time using the Latest Start Time (LST) rule to determine the optimal schedule. In this paper, the authors first show that the two-stage problem is NP-hard using a known result that the three-stage problem with equal job release times is NP-hard. The rest of the paper consists of two parts. In the first part, they compare the extension of the LST rule to the general multistage problem with other heuristics. The authors compare the heuristics based on the theoretically determined worst-case absolute error bound and on the experimentally determined average deviation from a developed lower bound. The analysis shows that in the presence of many stages, the LST rule does not perform as well as the other heuristics even though they are suboptimal for the single-stage problem. In the second part of this paper, the authors present a \((2+\varepsilon)\)-approximation algorithm for the multi-stage problem.
- Flowshop scheduling with identical jobs and uniform parallel machines
- Flexible flow shop scheduling with uniform parallel machines
- Two-Stage, Hybrid Flowshop Scheduling Problem
- Two-stage flowshop scheduling problems with identical and batch processors
- Geometrical heuristics for multiprocessor flowshop scheduling with uniform machines at each stage
- A state-of-the-art review of parallel-machine scheduling research
- Flowshop scheduling with identical jobs and uniform parallel machines
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- Minimizing makespan in hybrid flowshops
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Scheduling a two-stage hybrid flowshop with separable setup and removal times
- Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time
- Scheduling identical jobs on uniform parallel machines
- Two-Stage, Hybrid Flowshop Scheduling Problem
- Flowshop scheduling with identical jobs and uniform parallel machines
- Scheduling a two-stage hybrid flow shop with parallel machines at the first stage
- The hybrid flow shop scheduling problem
- Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective
- Flexible flow shop scheduling with uniform parallel machines
- scientific article; zbMATH DE number 4152123 (Why is no real title available?)
- A taxonomy of flexible flow line scheduling procedures
This page was built for publication: Multistage hybrid flowshop scheduling with identical jobs and uniform parallel machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1295836)
