Worst-case analysis of a modification of the Brucker-Garey-Johnson algorithm

Авторы: Memar J., Zinder Y., Kononov A.V.
Сборник: Optimization Problems and Their Applications. OPTA 2018
Серия: Communications in Computer and Information Science
Том: 871
Тезисы
Год издания: 2018
Место издания: Springer, Cham Cham
Первая страница: 78
Последняя страница: 92
DOI: 10.1007/978-3-319-93800-4_7
Аннотация: The paper presents the worst-case analysis of a polynomialtime approximation algorithm for the maximum lateness scheduling problem with parallel identical machines, arbitrary processing times and arbitrary precedence constraints. The algorithm is a modification of the Brucker-Garey-Johnson algorithm originally developed as an exact algorithm for the case of the problem with unit execution time tasks and precedence constraints represented by an in-tree. For the case when the largest processing time does not exceed the number of machines, we obtain a worst-case performance guarantee which is tight for arbitrary large instances of the considered maximum lateness problem. It is shown that, if the largest processing time is greater than the number of machines, then the worst-case performance guarantee for the list algorithm, obtained by Hall and Shmoys, is tight.
Добавил в систему: Кононов Александр Вениаминович

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ПсковГУ
	Главная Поиск Статистика О проекте Помощь

ИСТИНА