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

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

0.00 Avg rating0 Votes
Article ID: iaor2002698
Country: United States
Volume: 29
Issue: 11
Start Page Number: 987
End Page Number: 999
Publication Date: Nov 1997
Journal: IIE Transactions
Authors: ,
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.

Reviews

Required fields are marked *. Your email address will not be published.