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.