LOCAL SEARCH FOR NONPREEMPTIVE MULTIMODE RESOURCE-CONSTRAINED PROJECTSCHEDULING

This paper addresses a general class of nonpreemptive resource-constra ined project scheduling problems in which activity durations are discr ete functions of committed renewable and nonrenewable resources. We pr ovide a well known 0-1 problem formulation and stress the importance o f the model by giving applications within production and operations ma nagement. Furthermore, we prove that the feasibility problem is alread y NP-complete. Solution procedures proposed so far have the following shortcomings: exact methods can solve only very small instances to opt imality; heuristic solution approaches fail to generate feasible solut ions when problems become highly resource-constrained. Hence, we propo se a new local search method that first tries to rnd a feasible soluti on and secondly performs a single-neighborhood search on the set of fe asible mode assignments. To evaluate the new procedure we perform a ri gorous computational study on two benchmark sets. The experiment inclu des a comparison of our procedure with other heuristics.