Please use this identifier to cite or link to this item:
Kolisch, Rainer
Drexl, Andreas
Year of Publication: 
Series/Report no.: 
Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 360
This paper addresses a general class of nonpreemptive resource-constrained project scheduling problems in which activity durations are discrete functions of committed renewable and nonrenewabe resources. We provide a 0-1 problem formulation and stress the importance of the outlined model by giving applications within production and operations management. Furthermore, we prove that even the problem to derive a feasible solution is NP-complete. As a consequence, solution procedures proposed so far suffer from severe drawbacks: Exact procedures can only solve very small instances to optimality, while heuristic solution approaches fail to generate feasible solutions when problems become highly resource-constrained. Hence, we propose a new local search methodology which first tries to find a feasible solution and second performs a single-neighbourhood search on the set of feasible mode-assignments. In order to evaluate the new procedura we perform a rigorous computational study on the ProGen benchmark-set which is available in the open literature. The experiment includes a comparison of our procedure with other recently proposed heuristics.
Resource-constrained project scheduling
Multiple execution modes
Nonrenewable resource constraints
NP-complete feasibility problem
Local search
Document Type: 
Working Paper

Files in This Item:

Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.