Approximation algorithms for two-stage flexible flow shop scheduling (Q2292124): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q332134 |
Changed an Item |
||
Property / author | |||
Property / author: Ming-Hui Zhang / rank | |||
Normal rank |
Revision as of 04:03, 13 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximation algorithms for two-stage flexible flow shop scheduling |
scientific article |
Statements
Approximation algorithms for two-stage flexible flow shop scheduling (English)
0 references
3 February 2020
0 references
This paper deals with a two-stage flexible flow shop problem with a single machine at the first stage and \(m\) identical parallel machines at the second stage. The optimization criterion is the minimization of the makespan. First, a \((2 + \epsilon)\)-approximation algorithm is given. Then a 3-approximation and an \((2.5 + \epsilon)\)-approximation algorithm are given for the case when contiguous addresses are required at the second stage. In addition, the special cases with two and three identical parallel machines are considered, and approximation algorithms with a ratio of 2.5 and 2.67, respectively, are given which can be applied both to the contiguous and noncontiguous cases. The paper concludes with a new lower bound on the optimal function value.
0 references
scheduling
0 references
flexible flow shop
0 references
identical parallel machines
0 references
approximation algorithm
0 references