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

Alexander Tesch ()
Additional contact information
Alexander Tesch: Zuse Institute Berlin (ZIB)

Journal of Scheduling, 2020, vol. 23, issue 2, No 5, 233-251

Abstract: 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$$IEE≻SEE≻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).

Keywords: Scheduling; Resource-constrained project scheduling; Mixed-integer programming; Polyhedral study; Event-based models; Affine transformations (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-020-00647-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:23:y:2020:i:2:d:10.1007_s10951-020-00647-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-020-00647-6

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().