|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Approximation Algorithms for Scheduling Problems with Exact Delaysтезисы доклада
- Авторы: Ageev A., Kononov A.
- Сборник: Approximation and Online Algorithms. WAOA 2006
- Серия: Lecture Notes in Computer Science
- Том: 4368
- Тезисы
- Год издания: 2006
- Издательство: Springer Berlin
- Местоположение издательства: Heidelberg, Germany
- Первая страница: 1
- Последняя страница: 14
- DOI: 10.1007/11970125_1
- Аннотация: We give first constant-factor approximations for various cases of the coupled-task single machine and two-machine flow shop scheduling problems with exact delays and makespan as the objective function. In particular, we design 3.5- and 3-approximation algorithms for the general cases of the single-machine and the two-machine problems, respectively. We also prove that the existence of a (2−ε)-approximation algorithm for the single-machine problem as well as the existence of a (1.5−ε)-approximation algorithm for the two-machine problem implies P=NP. The inapproximability results are valid for the cases when the operations of each job have equal processing times and for these cases the approximation ratios achieved by our algorithms are very close to best possible: we prove that the single machine problem is approximable within a factor of 2.5 and the two-machine problem is approximable within a factor of 2.
- Добавил в систему: Кононов Александр Вениаминович