Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

A Polyhedral Study of Event-Based Models for the Resource-Constrained Project Scheduling Problem

Please always quote using this URN: urn:nbn:de:0297-zib-68485
under review
  • We consider event-based Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP) that represent an alternative to the common time-indexed model (DDT) of Pritsker et al. (1969) for the case where the underlying time horizon is large or job processing times are subject to huge variations. In contrast to the time-indexed model, the size of event-based models does not depend on the time horizon. For two event-based formulations OOE and SEE of Koné et al. (2011) we present new valid inequalities that dominate the original formulation. Additionally, we introduce a new event-based model: the Interval Event-Based Model (IEE). We deduce linear transformations between all three models that yield the strict domination order IEE > SEE > OOE for their linear programming (LP) relaxations, meaning that IEE has the strongest linear relaxation among the event-based models. We further show that the popular DDT formulation can be retrieved from IEE by certain polyhedral operations, thus giving a unifying view on a complete branch of MIP formulations for the RCPSP. In addition, we analyze the computational performance of all presented models on test instances of the PSPLIB (Kolisch and Sprecher 1997).

Download full text files

Export metadata

Author:Alexander TeschORCiD
Document Type:ZIB-Report
Tag:Mixed-Integer Programming; Scheduling
CCS-Classification:G. Mathematics of Computing
Date of first Publication:2018/04/27
Series (Serial Number):ZIB-Report (17-79)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.