Local search for nonpreemptive multi-mode resource-constrained project scheduling

Abstract

This paper addresses a general class of nonpreemptive resource-constrained project scheduling problems in which activity durations are discrete functions of committed renewable and nonrenewable resources. We provide a well known 0-1 problem formulation and stress the importance of the model by giving applications within production and operations management. Furthermore, we prove that the feasibility problem is already NP-complete. Solution procedures proposed so far have the following shortcomings: exact methods can solve only very small instances to optimality; heuristic solution approaches fail to generate feasible solutions when problems become highly resource-constrained. Hence, we propose a new local search method that first tries to find a feasible solution and secondly performs a single-neighborhood search on the set of feasible mode assignments. To evaluate the new procedure we perform a rigorous computational study on two benchmark sets. The experiment includes a comparison of our procedure with other heuristics.