Breadth-first and best-first exact procedures for regular measures of the multi-mode RCPSP

Abstract

The multi-mode resource constrained project scheduling problem (MM RCPSP) is a NP-hard problem representing a generalization of the well-studied RCPSP. Depth-first tree search approach by Sprecher & Drexl (1998) is the best known exact solution tree search procedure for this problem. In this paper we present two exact solution single-processor approaches: a breadth-first approach and a best-first monotone heuristic. The comparison with depth-first and CPLEX show promising results on small problem sets. We report extension of the breadth-first approach to yield exact multi-objective solutions for the PSPLIB (Project Scheduling Problem Library, Kolisch & Sprecher, 1997) problem sets which is the first of its kind.