Estimating Maximum Resource Load for Resource-Constrained Project Scheduling Problem

Ch. 1987. P. 356–363.

Alexander Lazarev, Dmitry Arkhipov D. I., German Tarasov g.

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.

Keywords: resource, project scheduling, Vector sum problem

Publication based on the results of: Analysis, choice and decision making in socio-economic, political and financial spheres: new models, methods and algorithms (2017)

In book

CEUR Workshop Proceedings (CEUR-WS.org) of the VIII International Conference on Optimization Methods and Applications “OPTIMIZATION AND APPLICATINS” (OPTIMA-2017)

Vol. 1987. , [б.и.], 2017.