A novel branch-and-bound algorithm for the chance-constrained RCPSP

Morteza Davari and Erik Demeulemeester

No 549419, Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven

Abstract: The resource-constrained project scheduling problem (RCPSP) has been widely studied during the last few decades. In real-world projects, however, not all information is known in advance and uncertainty is an inevitable part of these projects. The chance-constrained resource-constrained project scheduling problem (CC-RCPSP) has been recently introduced to deal with uncertainty in the RCPSP. In this paper, we propose a branch-and-bound (B&B) algorithm and a MILP formulation that solve the CC-RCPSP. We introduce two different branching schemes and eight different priority rules for the proposed B&B algorithm. Since solving CC-RCPSP is computationally intractable, its sample average approximation counterpart is considered to be solved. The computational results suggest that the proposed branch-and-bound procedure clearly outperforms both a proposed MILP formulation and a branch-and-cut algorithm from the literature.

Keywords: Chance-constrained problem; Branch-and-bound; CC-RCPSP (search for similar items in EconPapers)
Date: 2016-09
New Economics Papers: this item is included in nep-cmp and nep-ppm
References: Add references at CitEc
Citations:

Published in FEB Research Report KBI_1620

Downloads: (external link)
https://lirias.kuleuven.be/retrieve/402079 A novel branch-and-bound algorithm for the chance-constrained RCPSP (application/pdf)

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:ete:kbiper:549419

Access Statistics for this paper

More papers in Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven
Bibliographic data for series maintained by library EBIB ().