×

Formulation and tabu search algorithm for the resource constrained project scheduling problem. (English) Zbl 1048.90116

Ribeiro, Celso C. et al., Essays and surveys in metaheuristics. Boston: Kluwer Academic Publishers (ISBN 0-7923-7520-3). Oper. Res./Comput. Sci. Interfaces Ser. 15, 557-588 (2002).
Summary: The Resource Constrained Project Scheduling Problem (RCPSP) can formulate many scheduling problems including jobshop and flowshop scheduling problems. In this paper, we extend the definition of RCPSP further so that various complicated constraints and objective functions arising in practice can be handled; for example, each activity can be processed in one of the selectable modes, the available amounts of renewable resources may vary depending on the periods, setup activities can be dealt with, and complex objective functions can be handled. Then, we develop a tabu search based heuristic algorithm, which contains elaborations in representing solutions and in constructing neighborhood. Our code was tested for many benchmarks of RCPSP, and also for some problems from real applications. For a number of RCPSP instances, we found better solutions than the best ones found so far. These computational results indicate the effectiveness and usefulness of our approach.
For the entire collection see [Zbl 0976.00017].

MSC:

90B40 Search theory
90B35 Deterministic scheduling theory in operations research

Software:

PSPLIB
PDFBibTeX XMLCite