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 (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