Heuristics and applications for Ressource-Constrained Project Scheduling with Minimal and Maximal Time Lags

Priority-rule methods for approximately minimizing the duration of a project subject to minimal and maximal time lags between the activities of the project and limited availability of renewable resources are considered. Such a project can be modelled by a cyclic activity-on-node network. Two generation schemes for constructing feasible schedules are discussed: the serial and parallel schemes. Two different kinds of heuristic procedures are proposed. The sequential or direct method processes the activities or respectively nodes of the project network one after another without considering the strong components separately. The contraction method uses a bottom-up technique. First, a feasible subschedule is determined for each strong component. Second, each strong component is replaced by a single node and the resulting acyclic network is treated by the direct method. In conclusion, some results from an experimental performance analysis of the heuristics are given using a new network generator.