Repository logo
 
Publication

An approach using SAT solvers for the RCPSP with logical constraints

2016-03Journal article Restricted access
Simple item page
dc.contributor.authorVanhoucke, Mario
dc.contributor.authorCoelho, José
dc.date.accessioned2016-05-16T09:56:58Z
dc.date.available2016-05-16T09:56:58Z
dc.date.issued2016-03
dc.descriptionLast working versionpt_PT
dc.description.abstractThis 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.pt_PT
dc.identifier.doi10.1016/j.ejor.2015.08.044pt_PT
dc.identifier.issn0377-2217
dc.identifier.urihttp://hdl.handle.net/10400.2/5279
dc.language.isoengpt_PT
dc.peerreviewedyespt_PT
dc.publisherElsevierpt_PT
dc.relation.publisherversionhttp://www.sciencedirect.com/science/article/pii/S0377221715008000pt_PT
dc.subjectProject schedulingpt_PT
dc.subjectRCPSPpt_PT
dc.subjectAND/OR/BI constraintspt_PT
dc.subjectSATpt_PT
dc.titleAn approach using SAT solvers for the RCPSP with logical constraintspt_PT
dc.typejournal article
dspace.entity.typePublication
oaire.citation.endPage591pt_PT
oaire.citation.startPage577pt_PT
oaire.citation.titleEuropean Journal of Operational Researchpt_PT
oaire.citation.volume249 (2)pt_PT
person.familyNameVanhoucke
person.familyNameCoelho
person.givenNameMario
person.givenNameJosé
person.identifierR-000-8V7
person.identifier.ciencia-id7D18-9842-159F
person.identifier.orcid0000-0001-6702-3563
person.identifier.orcid0000-0002-5855-284X
person.identifier.ridD-8647-2015
person.identifier.scopus-author-id6507772652
rcaap.rightsrestrictedAccesspt_PT
rcaap.typearticlept_PT
relation.isAuthorOfPublication129fc49c-d742-406a-b680-f5544f8da0e2
relation.isAuthorOfPublication2926ed15-fe04-4ee4-a40d-ad0a83e33af8
relation.isAuthorOfPublication.latestForDiscovery2926ed15-fe04-4ee4-a40d-ad0a83e33af8

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
MMRCPSP_SAT_Logical_working_version.pdf
Size:
686.83 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.97 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Ciências e Tecnologia | Artigos em revistas internacionais / Papers in international journals