Handling Alternative Activities in Resource-Constrained Project Scheduling Problems

Jürgen Kuster, Jannach Dietmar, Gerhard Friedrich

In the context of operative disruption management, decision support systems have to evaluate the typically manifold options of responding to disturbances: The temporal shift of activities and the allocation of alternative resources can be assessed by the application of generic scheduling frameworks such as the Resource-Constrained Project Scheduling Problem (RCPSP). However, switches from one process variant to another one are usually not supported by the corresponding models, even though they represent a common way of repairing broken schedules in many practical domains. In this paper, we thus show how the RCPSP can be extended by the concept of alternative activities, making it possible to model and search within alternative process execution paths. Beside a formal description of the conceptual extension, we show how such generalized rescheduling problems can be solved by a novel genetic algorithm and summarize the promising results of a detailed evaluation.

Subjects: 1.12 Scheduling; 15.7 Search

Submitted: Oct 2, 2006