Tonius Baar, Peter Brucker, Sigrid Knust
Tabu-Search Algorithms and Lower Bounds for the Resource-Constrained Project Scheduling Problem
The paper is published:
in: S.Voss, S.Martello, I.Osman, C.Roucairol (eds.): Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer, 1998, 1-18.
- MSC:
- 90B35 Scheduling theory, See also {68M20}
Abstract: We present two tabu search algorithms for the resource-constrained
project scheduling problem. Given are n activities which have to be
processed without preemptions. During the processing period of an activity
constant amounts of renewable resources are needed where the available capacity
of each resource type is limited. Furthermore, finish-start precedence
relations between the activities are given. The objective is to determine
a schedule with minimal makespan.
The first tabu search approach relies on elimination of critical arcs and
list-scheduling techniques. The second neighborhood is based on schedule
schemes, where neighbors are generated by placing activities in parallel or
deleting a parallelity relation.
Furthermore, a column-generation approach for a linear programming-based
lower bound is presented and computational results are reported.
Keywords: tabu-search method, parallelity concept, resource-constrained, scheduling problem