Options
Approximation algorithms for coupled task scheduling minimizing the sum of completion times
Citation Link: https://doi.org/10.15480/882.8478
Publikationstyp
Journal Article
Date Issued
2023-04-25
Sprache
English
Author(s)
Fischer, David Simon
TORE-DOI
Journal
Volume
328
Start Page
1387
End Page
1408
Citation
Annals of Operations Research 328: 1387-1408 (2023)
Publisher DOI
Scopus ID
Publisher
Springer
In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We
provide constant-factor approximation algorithms for several variants of this problem that are known to be N P-hard, while also proving N P-hardness for two variants whose complexity
was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective
approximation in the coupled task setting.
provide constant-factor approximation algorithms for several variants of this problem that are known to be N P-hard, while also proving N P-hardness for two variants whose complexity
was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective
approximation in the coupled task setting.
Subjects
Approximation algorithms
Coupled task problem
Single machine scheduling
Total completion times
DDC Class
510: Mathematics
600: Technology
Publication version
publishedVersion
Loading...
Name
s10479-023-05322-5.pdf
Size
947.49 KB
Format
Adobe PDF