A tabu search procedure for the resource-constrained project scheduling problem with alternative subgraphs

Tom Servranckx and Mario Vanhoucke

European Journal of Operational Research, 2019, vol. 273, issue 3, 841-860

Abstract: This paper investigates the resource-constrained project scheduling problem with alternative subgraphs (RCPSP-AS). In this scheduling problem, there exist alternative ways to execute subsets of activities that belong to work packages. One alternative execution mode must be selected for each work package and, subsequently, the selected activities in the project structure should be scheduled. Therefore, the RCPSP-AS consists of two subproblems: a selection and a scheduling subproblem. A key feature of this research is the categorisation of different types of alternative subgraphs in a comprehensive classification matrix based on the dependencies that exist between the alternatives in the project structure. As the existing problem-specific datasets do not support this framework, we propose a new dataset of problem instances using a well-known project network generator. Furthermore, we develop a tabu search that uses information from the proposed classification matrix to guide the search process towards high-quality solutions. We verify the overall performance of the metaheuristic and different improvement strategies using the developed dataset. Moreover, we show the impact of different problem parameters on the solution quality and we analyse the impact of distinct resource characteristics of alternatives on the selection process.

Keywords: Project scheduling; Resource-constrained scheduling; Alternative subgraphs; Tabu search (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718307513
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:273:y:2019:i:3:p:841-860

DOI: 10.1016/j.ejor.2018.09.005

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 ().