Insertion techniques for static and dynamic resource-constrained project scheduling. (Q1399570)

In the paper the Resource-Constrained Project Scheduling Problem (RCPSP) minimizing the makespan in static and dynamic environments is considered. Based on a flow network model for feasible schedules a polynomial insertion algorithm is developed which inserts one activity into an existing schedule. This algorithm is used for robust rescheduling in a dynamic environment and as a subroutine in a tabu search procedure for the static RCPSP. Computational results are presented for the PSPLIB benchmark instances of \textit{R. Kolisch, A. Sprecher} and \textit{A. Drexl} [Manage. Sci. 41, 1693--1703 (1995; Zbl 0870.90070)] showing the potential of the proposed concept.