A note on flow-based formulations for solving resource constrained scheduling problems

Abstract

The resource constrained scheduling problem involves the scheduling of a number of activities over time, where each activity consumes one or more resources per time period. For a feasible solution to exist, the total resource consumption per time period must not exceed the available resources. In addition, the order in which activities may be scheduled is determined by a precedence graph. In this paper, valid inequalities proposed for the resource flow-based formulation in previous studies are investigated to determine what effect they may have on
computing times. It is shown empirically that improved computing times may be obtained if these valid inequalities are, in fact, omitted from the resource ow-based formulation. In addition, a heuristic is proposed for the generation of initial starting solutions and for estimating the extent of the scheduling horizon which, in turn, is required to calculate the latest starting times of activities. The computational results are based on well-known problem test instances as well as new randomly generated problem instances.

Keywords: Scheduling, mixed integer linear programming, valid inequalities