Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

24.02.2020 | Ausgabe 2/2020 Open Access

Journal of Scheduling 2/2020

A polyhedral study of event-based models for the resource-constrained project scheduling problem

Zeitschrift:
Journal of Scheduling > Ausgabe 2/2020
Autor:
Alexander Tesch
Wichtige Hinweise

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

In this paper, we study event-based mixed-integer programming (MIP) formulations for the resource-constrained project scheduling problem (RCPSP) that represent an alternative to the more common time-indexed model (DDT) (Pritsker et al. in Manag Sci 16(1):93–108, 1969; Christofides et al. in Eur J Oper Res 29(3):262–273, 1987) for the case when the scheduling horizon is large. In contrast to time-indexed models, the size of event-based models does not depend on the time horizon. For two event-based models OOE and SEE introduced by Koné et al. (Comput Oper Res 38(1):3–13, 2011), we first present new valid inequalities that strengthen the original formulation. Furthermore, we state a new event-based model, the Interval Event-Based Model (IEE), and deduce natural linear transformations between all three models. Those transformations yield the strict domination order \(IEE \succ SEE \succ OOE\) for their respective linear programming relaxations, meaning that the new IEE model has the strongest linear relaxation among all known event-based models. In addition, we show that DDT can be retrieved from IEE by subsequent expansion and projection of the underlying solution space. This yields a unified polyhedral view on a complete branch of MIP models for the RCPSP. Finally, we also compare the computational performance between all models on common test instances of the PSPLIB (Kolisch and Sprecher in Eur J Oper Res 96(1):205–216, 1997).
Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 2/2020

Journal of Scheduling 2/2020 Zur Ausgabe

Premium Partner

    Bildnachweise