|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ПсковГУ |
||
Bicriteria Approximation Algorithms for Scheduling Problems with Communication Delaysстатья
Статья опубликована в высокорейтинговом журнале
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 8 октября 2025 г.
- Авторы: Bampis E., Kononov A.
- Журнал: Journal of Scheduling
- Том: 8
- Номер: 4
- Год издания: 2005
- Издательство: Springer Nature
- Местоположение издательства: Switzerland
- Первая страница: 281
- Последняя страница: 294
- DOI: 10.1007/s10951-005-1637-6
- Аннотация: We study the problem of simultaneously minimizing the makespan and the average weighted completion time for the precedence multiprocessor constrained scheduling problem with unit execution times and unit communication delays, known as the UET–UCT problem (Munier and Konig, Operations Research, 45(1), 145–148 (1997)). We propose a simple (16/9, 16/9)-approximation algorithm for the problem with an unrestricted number of machines. We improve our algorithm by adapting a technique first introduced by Aslam et al. (Proceedings of ACM-SODA, pp. 846–847, 1999) and provide a (1.745, 1.745)-approximate solution. For the considered scheduling problem, we prove the existence of a (1.445, 1.445)-approximate solution, improving the generic existence result of Aslam et al. (Proceedings of ACM-SODA, pp. 846–847, 1999). Also notice that our results for the case of an unrestricted number of processors hold for the more general scheduling problem with small communication delays (SCT problem), and for two other classical optimality criteria: maximum lateness and weighted lateness. Finally, we propose an approximation algorithm for the UET–UCT problem with a restricted number of processors.
- Добавил в систему: Кононов Александр Вениаминович