Back to Search
Start Over
Bicriteria two-machine flowshop scheduling: approximation algorithms and their limits.
- Source :
- Journal of Scheduling; Feb2024, Vol. 27 Issue 1, p61-86, 26p
- Publication Year :
- 2024
-
Abstract
- We consider bicriteria flowshop scheduling problems with two machines to simultaneously minimize the makespan and the total completion time without any prioritization between the two objectives. An approximation relative to the optimal value of the problem with regard to each objective is adopted, even though a schedule with both objectives reaching their minimum at the same time may not exist. We consider several problems with ordered aspects on processing times such as job ordered and machine ordered. For each problem, we propose a fast (ρ 1 , ρ 2) -approximation algorithm, where ρ 1 and ρ 2 indicate the approximation ratios with regard to the makespan and the total completion time, respectively, and we explore the problem's inapproximability region that cannot be reached by any algorithm. [ABSTRACT FROM AUTHOR]
- Subjects :
- APPROXIMATION algorithms
SCHEDULING
PRODUCTION scheduling
Subjects
Details
- Language :
- English
- ISSN :
- 10946136
- Volume :
- 27
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Journal of Scheduling
- Publication Type :
- Academic Journal
- Accession number :
- 175358540
- Full Text :
- https://doi.org/10.1007/s10951-023-00781-x