42730

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Доклад

Название: 

Estimating Maximum Resource Load for Resource-Constrained Project Scheduling Problem

Электронная публикация: 

Да

ISBN/ISSN: 

1613-0073

Наименование конференции: 

  • 8th International Conference on Optimization Methods and Applications “OPTIMIZATION AND APPLICATINS” (OPTIMA-2017, Petrovac, Montenegro)

Наименование источника: 

  • Proceedings of the 8th International Conference on Optimization Methods and Applications “OPTIMIZATION AND APPLICATINS” (OPTIMA-2017)

Обозначение и номер тома: 

Vol-1987

Город: 

  • Москва

Издательство: 

  • ВЦ РАН

Год издания: 

2017

Страницы: 

356-363 http://CEUR-WS.org/Vol-1987/paper52.pdf
Аннотация
In Resource-Constrained Project Scheduling Problem (RCPSP), two kinds of constraints are considered: the precedence constraints, which can be eliminated by using critical path method, and the resource con- straints. This paper focuses on the latter, specifically, on estimating max- imum resource loads. We examine a variant of vector sum problem with fractions: considering preemptions allowed, determine what part of each of n jobs should be accomplished in order to minimize quadratic sum of non-consumed amounts of resources subject to resource constraints along with minimizing the number of preemptions. We prove that in case of 2 resources, the optimal solution contains only 2 or less preemptions, and present two polynomial algorithms of finding such solution with complex- ities O(nlogn) and O(n 2 ) operations, the latter leaves space for modifi- cation, e. g. for a weighted variant of the problem. We also present an investigation on the general case of arbitrary number of resources

Библиографическая ссылка: 

Архипов Д.И., Лазарев А.А., Тарасов Г.В. Estimating Maximum Resource Load for Resource-Constrained Project Scheduling Problem / Proceedings of the 8th International Conference on Optimization Methods and Applications “OPTIMIZATION AND APPLICATINS” (OPTIMA-2017). М.: ВЦ РАН, 2017. Vol-1987. С. 356-363 http://CEUR-WS.org/Vol-1987/paper52.pdf.