Author:

Keywords:

Resource loading, Dynamic programming, NP-complete, Preemption, Approximation algorithms

Abstract:

Resource loading appears in many variants in tactical (mid-term) capacity planning in multiproject environments. It deals with the development of a rough sketch of the resource usage and timing of the work packages of a portfolio of orders. The orders need to be executed within a time horizon organized into periods, where each period has a known number of workers available. Each order has a time window during which it must be executed and an upper and a lower bound on the number of workers that can work on that order in a period. The duration of the order is not fixed beforehand but depends on the number of workers (intensity) with which it is executed. In this article we define three fundamental variants of resource loading and we study six special cases that are common to the three variants of the problem. We present algorithms for the cases that can be solved either in polynomial time or in pseudo-polynomial time. We prove that the remaining cases are np-complete in the strong sense and we also discuss the existence of approximation algorithms for some of these cases. Finally, we comment on the validity of our results when orders must be executed without preemption.