Mixed-integer linear programming for resource leveling problems

We consider project scheduling problems subject to general temporal constraints, where the utilization of a set of renewable resources has to be smoothed over a prescribed planning horizon. In particular, we consider the classical resource leveling problem, where the variation in resource utilization during project execution is to be minimized, and the so-called “overload problem”, where costs are incurred if a given resource-utilization threshold is exceeded. For both problems, we present new mixed-integer linear model formulations and domain-reducing preprocessing techniques. In order to strengthen the models, lower and upper bounds for resource requirements at particular points in time, as well as effective cutting planes, are outlined. We use CPLEX 12.1 to solve medium-scale instances, as well as instances of the well-known test set devised by Kolisch et al. (1999). Instances with up to 50 activities and tight project deadlines are solved to optimality for the first time.