A satisfiability and workload-based exact method for the resource constrained project scheduling problem with generalized precedence constraints

Guilherme Henrique Ismael de Azevedo, Artur Alves Pessoa and Anand Subramanian

European Journal of Operational Research, 2021, vol. 289, issue 3, 809-824

Abstract: This paper deals with the resource constrained project scheduling problem (RCPSP) with generalized precedence constraints (RCPSP/Max). We propose an exact method that tackles a relaxed version of the original problem by modeling it as a satisfiability problem (SAT). Several SAT formulations are introduced, as well as workload-based procedures that were developed in order to reduce the domain of the decision variables, and custom propagators that were implemented with a view of improving the efficiency of the SAT solver. Extensive computational experiments involving different configurations of the method were carried out on 2430 RCPSP/Max benchmark instances ranging from 10 to 500 activities and with 5 resources, and on 2040 RCPSP benchmark instances ranging from 30 to 120 activities and with 4 resources. The results obtained suggest that the proposed method is extremely competitive as almost all known optima were found and 86 instances were solved to optimality for the first time. Moreover, a number of bounds were improved for those instances that still remain open.

Keywords: Project scheduling; Resource constraints; Satisfiability problem (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719306356
Full text for ScienceDirect subscribers only

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:eee:ejores:v:289:y:2021:i:3:p:809-824

DOI: 10.1016/j.ejor.2019.07.056

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().