67. Analysis of an Approximation Algorithm for Coupled Task Scheduling with Equal Lengths of Tasks for Minimizing the Sum of Completion Times
Invited abstract in session FB-3: Approximation algorithms for scheduling problems, stream Approximation algorithms.
Friday, 10:15 - 11:45Room: C 104
Authors (first author is the speaker)
| 1. | József Békési
|
| Department of Computer Algorithms and Artificial Intelligence, Faculty of Science and Informatics, University of Szeged | |
| 2. | Gyorgy Dosa
|
| Mathematical Department, University of Pannonia | |
| 3. | Gábor Galambos
|
| Applied Informatics, University of Szeged |
Abstract
In the considered coupled task problem (CTP) we have to schedule n jobs on a single machine, each of them consisting of two tasks with exact time delays in between, while the objective is to minimize the total of job completion times. We analyze a greedy type algorithm -- called A -- from worst case point of view, and we give bounds for the asymptotic behavior of A for the special case where each task has equal length p. For this case, the best-known upper bound on the asymptotic performance ratio of algorithm A has been smaller or equal than 5/3. We improve this bound to 1.5426... and we give a closed formula for the upper bound for every p >= 1. We use constructions to calculate lower bounds and thus give narrow intervals for the asymptotic behavior of the algorithm A as a function of the parameter p. The bounds are tight for p=1 and p=2, the values are 1.18350341... and 1.348612... respectively.
Keywords
- Complexity and efficiency of optimization algorithms
Status: accepted
Back to the list of papers