Non-equivalent search strategies for resource-constrained project scheduling

Over the years numerous branch-and-bound procedures for solving the resource-constrained project scheduling problem (RCPSP) have been developed. Enumerating delaying alternatives, extension alternatives, feasible posets, feasible sequences, feasible completion times or feasible subsets, they all aim at finding as fast as possible a makespan minimal schedule among the resource and precedence feasible ones. Some of the enumeration schemes have been modified to solve variants of the so-called resource-constrained project scheduling problem, like the resource-constrained project scheduling problem with multiple modes or with work content defined modes. We compare the enumeration of delaying alternatives and the enumeration of extension alternatives. Roughly considered the concepts that analyze only minimal delaying alternatives and the concept that analyze only maximal extension alternatives seem to be equivalent. Counterexamples will show that - in contrast to claims made in the literature - search tree reduction to minimal delaying alternatives and search tree reduction to maximal extension alternatives are not equivalent. While the former reduction preserves optimality the latter one is neither correct for the RCPSP with single execution modes nor for the RCPSP with work content defined modes.