Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #99010 (April, 1999)

Formulation and Tabu Search Algorithm for the Resource Constrained Project Scheduling Problem (RCPSP)
by Koji Nonobe and Toshihide Ibaraki

Resource constrained project scheduling problem (RCPSP) can formulate many real world scheduling problems including jobshop and flowshop scheduling problems. In this paper, we extend the definition of RCPSP further so that various complicated problems 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 search space and neighborhood. Our code was tested for a number of benchmarks of the jobshop and RCPSP, and also for some problems from real applications. For many RCPSP instances, we found better solutions than the best ones found so far. These computational results indicate the effectiveness and usefulness of our approach.