Scheduling jobs with equal processing times on a single machine: minimizing maximum lateness and makespan

Лазарев, А.А.; Архипов, Д.И.; Werner, F.

Информация о цитировании статьи получена из Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 26 сентября 2016 г.

Авторы: Лазарев А.А., Архипов Д.И., Werner F.
Журнал: Optimization Letters
Номер: 4
Год издания: 2016
Издательство: Springer Verlag
Местоположение издательства: Germany
Первая страница: 1
Последняя страница: 13
DOI: 10.1007/s11590-016-1003-y
Аннотация: The following special case of the classical NP-hard scheduling problem 1|r_j |Lmax is considered. There is a set of jobs N = {1, 2, . . . , n} with identical processing times p_j = p for all jobs j ∈ N. All jobs have to be processed on a single machine. The optimization criterion is the minimization of maximum lateness Lmax. We analyze algorithms for the makespan problem 1|r_j |Cmax, presented by Garey et al. (SIAM J Comput 10(2):256–269, 1981), Simons (A fast algorithm for single processor scheduling. In: 19th Annual symposium on foundations of computer science (Ann Arbor, Mich., 1978, 1978) and Benson’s algorithm (J Glob Optim 13(1):1–24, 1998) and give two polynomial algorithms to solve the problem under consideration and to construct the Pareto set with respect to the criteria Lmax and Cmax. The complexity of the presented algorithms is O(Q · n log n) and O(n^3 log n), respectively, where 10^−Q is the accuracy of the input-output parameters.
Добавил в систему: Лазарев Александр Алексеевич

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

ИСТИНА

ФНКЦ РР

Scheduling jobs with equal processing times on a single machine: minimizing maximum lateness and makespanстатья

Прикрепленные файлы