Diplomarbeit Dipl.Inf. Thomas Huelse

Huelse, Thomas (1998):  „Taboo-Search Methods for Project Scheduling with Scarce Resources – Intelligent Solution Strategies for the Rcpsp/Pi“, Christian-Albrechts-Universität of Kiel, defended and evaluated by the examiners, grade: 1.0 (best of class), borrowable in the university library of the CAU-Kiel, publication of the results in the PhD Thesis od Dr. Andreas Schirmer

A wide range of applications has developed for project management, which originally originated in the handling of large-scale construction projects. Examples include projects for reorganisation, product development, make-to-order production and projects from the R&D sector and innovation management.

One of the central tasks of functional project management – within the framework of process and workflow organisation – is the preparation of a project schedule, which defines the exact chronological sequence of the individual project tasks. Simultaneously to the project schedule, resource management must be carried out, which usually takes into account scarce resources in the form of operating resources or personnel capacity. Accordingly, time and capacity planning are mentioned in the literature as core questions of project planning and numerous different models and procedures are proposed for solving them.

The Resource-Constraint Project Scheduling Problem (RCPSP) has become known as the classical model for project planning in the case of scarce resources. Despite its generality, it allows clear and efficient modelling of numerous real problems. Recent work shows, however, that the classical resource concepts used in RCPSP cannot represent all real-world situations. Only the introduction of a new resource concept, the partially renewable resources, could eliminate these modelling deficits. In some cases, efficient modelling is only possible if the concept of partially renewable resources is extended by capacity profiles.

The starting point of this work is the RCPSP/Pi, a model for project planning with scarce resources on the basis of the partially renewable resources concept. The aim is the development, implementation and evaluation of suitable taboo search methods for the RCPSP/Pi. Taboo-Search is an intelligent meta-strategy for the heuristic solution of complex optimisation problems, which is used to control local search procedures. In contrast to the amnesic process design, as for example in branch-and-bound or priority control procedures, adaptable memory structures are used in taboo search procedures, which enable a reactive exploration of the solution space. A large number of successful applications of Taboo-Search in various fields as well as the results of this work justify the description as “currently the best strategy for solving combinatorial optimisation problems”.