New Task Domain Propagators with Polynomial Complexity for Resource-Constrained Project Scheduling Problem

Авторы: Архипов Д.И., Battaia O., Лазарев А.А., Тарасов Г.В., Тарасов И.А.
Сборник: DEStech Transactions on COMPUTER SCIENCE and ENGINEERING
Год издания: 2019
Место издания: DESTech Publications, Inc Lancaster
Первая страница: 3
Последняя страница: 13
DOI: 10.12783/dtcse/optim2018/27917
Аннотация: We consider a classic Resource-Constrained Project Scheduling Problem (RCPSP) which is known to be NP-hard. For defined project deadline T , each task of the project can be associated with its temporal domain – a time interval in which this task can be processed. In this research, we adopt existing resource-based methods of task domain propagation to generalized statement with time-dependent resource capacity and show how to improve its propagation efficiency. We also present new polynomial-time algorithms (propagators) to tighten such temporal task domains in order to make the optimization problem easier to solve. Moreover, we show how these propagators can be used to calculate lower bound on project makespan.
Добавил в систему: Лазарев Александр Алексеевич

№	Имя	Описание	Имя файла	Размер	Добавлен
1.	1_DEStech_AR_BAT.pdf		1_DEStech_AR_BAT.pdf	2,6 МБ	13 декабря 2019 [Lazarev]
2.	2_DEStech_AR_BAT.pdf		2_DEStech_AR_BAT.pdf	347,8 КБ	13 декабря 2019 [Lazarev]

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

ИСТИНА