Approximation algorithms for coupled task scheduling minimizing the sum of completion times
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913338353516544 |
|---|---|
| author | Fischer, David Györgyi, Péter |
| author_facet | Fischer, David Györgyi, Péter |
| contents | 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 NP-hard, while also proving NP-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_00394 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Approximation algorithms for coupled task scheduling minimizing the sum of completion times Fischer, David Györgyi, Péter Optimization and Control 90B35 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 NP-hard, while also proving NP-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. |
| title | Approximation algorithms for coupled task scheduling minimizing the sum of completion times |
| topic | Optimization and Control 90B35 |
| url | https://arxiv.org/abs/2207.00394 |