Technical Report 188-1988

Title
Scheduling Project Networks with Resource Constraints and Time Windows
Authors
M. Bartusch, Rolf H. Möhring, and Franz J. Radermacher
Publication
Annals of Operations Research, vol. 16, 1988, pp. 201-240
Source
Download as [PDF] [ps.gz]
Classification
not available
Keywords
not available
Abstract
Project networks with time windows are generalizations of the well-known CPM and MPM networks that allow for the introduction of arbitrary minimal and maximal time lags between the starting and completion times of any pair of activities. We consider the problem to schedule such networks subject to arbitrary (even time dependent) resource constraints in order to minimize an arbitrary regular performance measure (i.e. a non-decreasing function of the vector of completion times). This problem arises in many standard industrial construction or production processes and is therefore particularly suited as a background model in general purpose decision support systems. The treatment is done by a strutural approach that involves a generalization of both the disjunctive graph method in job shop scheduling and the order theoretic methods for precedence constrained scheduling. Besides theoretical insights into the problem structure, this approach also leads to rather powerfull branch-and-bound algorithms. Computational experience with this algorithm is reported.