A Scheme of Approximation Solution of Problem 1 | rj | Lmax

Авторы: Лазарев А.А., Садыков Р.Р., Севастьянов С.В.
Журнал: Diskretn. Anal. Issled. Oper
Том: 2
Номер: 1
Год издания: 2006
Первая страница: 57
Последняя страница: 76
DOI: 10.1134/S1990478907040102
Аннотация: The strongly NP-hard scheduling problem of minimizing the maximum lateness on one machine subject to job release dates is under study. We present a general scheme of approximation solution of the problem which is based on searching for a given problem instance another instance, closest to the original in some metric and belonging to a known polynomially solvable class of instances. For a few concrete variants of the scheme (using different polynomially solvable classes of instances) some analytic formulas are found that make it possible, given a problem instance, to compute easily an upper bound on the absolute error of the solution obtained by a chosen scheme.
Добавил в систему: Лазарев Александр Алексеевич

№	Имя	Описание	Имя файла	Размер	Добавлен
1.	art3A10.11342FS1990478907040102.pdf		art3A10.11342FS1990478907040102.pdf	669,1 КБ	18 сентября 2013 [Lazarev]

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

ИСТИНА