Approximation algorithms for coupled task scheduling minimizing the sum of completion times
Fischer, D and Györgyi, Péter (2023) Approximation algorithms for coupled task scheduling minimizing the sum of completion times. ANNALS OF OPERATIONS RESEARCH, 328. pp. 1387-1408. ISSN 0254-5330 10.1007/s10479-023-05322-5
|
Text
Fischer_1387_33781238_ny.pdf Download (970kB) | Preview |
Abstract
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 \mathcal{N}\mathcal{P} N P -hard, while also proving \mathcal{N}\mathcal{P} 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.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science > QA Mathematics and Computer Science > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| Divisions: | Research Laboratory on Engineering & Management Intelligence |
| SWORD Depositor: | MTMT Injector |
| Depositing User: | MTMT Injector |
| Date Deposited: | 28 Aug 2023 07:02 |
| Last Modified: | 11 Sep 2023 14:56 |
| URI: | https://eprints.sztaki.hu/id/eprint/10563 |
 |
Update Item |
