A new solution approach to solve the resource-constrained project scheduling problem with logical constraints
Name:
Publisher version
View Source
Access full-text PDFOpen Access
View Source
Check access options
Check access options
Publication type
Vlerick strategic journal articlePublication Year
2016Journal
European Journal of Operational ResearchPublication Volume
249Publication Issue
2Publication Begin page
577Publication End page
591
Metadata
Show full item recordAbstract
This paper presents a new solution approach to solve the resource-constrained project scheduling problem in the presence of three types of logical constraints. Apart from the traditional AND constraints with minimal time-lags, these precedences are extended to OR constraints and bidirectional (BI) relations. These logical constraints extend the set of relations between pairs of activities and make the RCPSP definition somewhat different from the traditional RCPSP research topics in literature. It is known that the RCPSP with AND constraints, and hence its extension to OR and BI constraints, is NP-hard. The new algorithm consists of a set of network transformation rules that removes the OR and BI logical constraints to transform them into AND constraints and hereby extends the set of activities to maintain the original logic. A satisfiability (SAT) solver is used to guarantee the original precedence logic and is embedded in a metaheuristic search to resource feasible schedules that respect both the limited renewable resource availability as well as the precedence logic. Computational results on two well-known datasets from literature show that the algorithm can compete with the multi-mode algorithms from literature when no logical constraints are taken into account. When the logical constraints are taken into account, the algorithm can report major reductions in the project makespan for most of the instances within a reasonable time.Knowledge Domain/Industry
Operations & Supply Chain Managementae974a485f413a2113503eed53cd6c53
10.1016/j.ejor.2015.08.044