Improved Compact Models for the Resource-Constrained Project Scheduling Problem

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

A chapter in Operations Research Proceedings 2016, 2018, pp 25-30 from Springer

Abstract: Abstract In this article, we study compact Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP). Compared to the classical time-indexed formulation, the size of compact models is strongly polynomial in the number of jobs. In addition to two compact models from the literature, we propose a new compact model. We can show that all three compact models are equivalent by successive linear transformations. For their LP-relaxations, however, we state a full inclusion hierarchy where our new model dominates the previous models in terms of polyhedral strength. Moreover, we reveal a polyhedral relationship to the common time-indexed model. Furthermore, a general class of valid cutting planes for the compact models is introduced and finally all models are evaluated by computational experiments.

Keywords: Resource-constrained Project Scheduling Problem; Compact Model; Time-indexed Model; Sophisticated Preprocessing Techniques; Pritsker (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:oprchp:978-3-319-55702-1_4

Ordering information: This item can be ordered from
http://www.springer.com/9783319557021

DOI: 10.1007/978-3-319-55702-1_4

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().