?
Estimating Maximum Resource Load for Resource-Constrained Project Scheduling Problem
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.