Isomorphic scheduling problems

Gawiejnowicz, S.; Kononov, A.

Авторы: Gawiejnowicz S., Kononov A.
Журнал: Annals of Operations Research
Том: 213
Год издания: 2014
Издательство: Springer Nature
Местоположение издательства: Switzerland
Первая страница: 131
Последняя страница: 145
DOI: 10.1007/s10479-012-1222-2
Аннотация: We consider general properties of isomorphic scheduling problems that constitutea new class of pairs of mutually related scheduling problems. Any such a pair is composed of a scheduling problem with fixed job processing times and its time-dependent counterpart with processing times that are proportional-linear functions of the job starting times. In order to introduce the class formally, first we formulate a generic scheduling problem with fixed job processing times and define isomorphic problems by a one-to-one transformation of instances of the generic problem into instances of time-dependent scheduling problems with proportional-linear job processing times. Next, we prove basic properties of isomorphic scheduling problems and show how to convert polynomial algorithms for schedulingproblems with fixed job processing times into polynomial algorithms for proportional-linearcounterparts of the original problems. Finally, we show how are related approximation algorithms for isomorphic problems. Applying the results, we establish new worst-case results for time-dependent parallel-machine scheduling problems and prove that many single- and dedicated-machine time-dependent scheduling problems with proportional-linear job processing times are polynomially solvable.
Добавил в систему: Кононов Александр Вениаминович

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

ИСТИНА

ИСТИНА ПсковГУ

Isomorphic scheduling problemsстатья