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

Arbeitspapier

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.

Object Details

• Language: Englisch

References and Relationships

• Bibliographic citation: Series: Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel ; No. 360

Classification and Topics

• Classification: Management
• Subject: Resource-constrained project scheduling ; Multiple execution modes ; Nonrenewable resource constraints ; NP-complete feasibility problem ; Local search ; Produktionssteuerung ; Produktionskapazität ; Theorie

Contributors, Places and Time

• Event: Geistige Schöpfung
• (who): Kolisch, Rainer ; Drexl, Andreas
• Event: Veröffentlichung
• (who): Universität Kiel, Institut für Betriebswirtschaftslehre ; ZBW – Leibniz Information Centre for Economics
• (where): Kiel
• (when): 1994

Further information

• Handle: http://hdl.handle.net/10419/155429
• Last update: 10.03.2025, 11:44 AM CET