An iterated-local-search heuristic for the resource-constrained weighted earliness-tardiness project scheduling problem

Abstract

This paper deals with the weighted earliness-tardiness resource-constrained project scheduling problem with minimum and maximum time lags (WET-RCPSP/max). The problem consists of scheduling the activities of a project subject to prescribed resource and temporal constraints such that the total weighted deviation of the activities' completion times from prescribed due dates is minimized. Key applications are planning of just-in-time production and reactive scheduling. For the (approximative) solution of the WET-RCPSP/max, we present a population-based iterated-local-search heuristic. We also report the results of an experimental performance analysis where this heuristic outperformed state-of-the-art methods.

Keywords:

• Reactive scheduling
• Just-in-time production
• Resource-constrained project scheduling
• Weighted earliness-tardiness cost
• Iterated-local-search

Acknowledgements

The authors are very grateful for the many helpful comments and suggestions of the three anonymous referees. This work was performed during the stay of the first author at the Universität Karlsruhe (Germany). This research was partially supported by the Ministerio de Ciencia y Tecnología (Spain) under contract TIC2002-02510.