A Branch and Bound Algorithm

Whereas exact methods for solving the single-mode resource-constrained project scheduling problem are well documented in the literature (cf. e.g. [7], [18], [25], [27], [32], [33], [33], [95], [101], [112], [113]), the multi-mode extension has attracted less attention (cf. [88], [89], [109], [114], [115], [116]). In this chapter we present and analyze an algorithm for the multi-mode resource-const rained project scheduling problem. The stepping stone of the algorithm is a proposal from Patterson et al. (cf. [88]) who introduced an enumeration procedure of the Branch and Bound (B&B) type. The basic ideas were, of course, given by Talbot and Patterson (cf. [116]) and Talbot (cf. [115]). For getting deeper insight the algorithm is completely restructured, where main differences will be identified by remarks.