Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.2/1790
Título: Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers
Autor: Coelho, José
Vanhoucke, Mario
Palavras-chave: Project scheduling
SAT
Multi-mode RCPSP
Data: Mar-2011
Editora: ELSEVIER
Citação: Coelho, José; Vanhoucke, Mario - Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers [Em linha]. "European Journal of Operational Research". ISSN 0377-2217. Vol. 213, Issue 1 (2011), p. 73-82
Resumo: This paper reports on a new solution approach for the well-known multi-mode resource-constrained project scheduling problem (MRCPSP). This problem type aims at the selection of a single activity mode from a set of available modes in order to construct a precedence and a (renewable and non-renewable) resource feasible project schedule with a minimal makespan. The problem type is known to be NP-hard and has been solved using various exact as well as (meta-)heuristic procedures. The new algorithm splits the problem type into a mode assignment and a single mode project scheduling step. The mode assignment step is solved by a satisfiability (SAT) problem solver and returns a feasible mode selection to the project scheduling step. The project scheduling step is solved using an efficient meta-heuristic procedure from literature to solve the resource-constrained project scheduling problem (RCPSP). However, unlike many traditional meta-heuristic methods in literature to solve the MRCPSP, the new approach executes these two steps in one run, relying on a single priority list. Straightforward adaptations to the pure SAT solver by using pseudo boolean non-renewable resource constraints has led to a high quality solution approach in a reasonable computational time. Computational results show that the procedure can report similar or sometimes even better solutions than found by other procedures in literature, although it often requires a higher CPU time.
Peer review: yes
URI: http://hdl.handle.net/10400.2/1790
ISSN: 0377-2217
Versão do Editor: http://dx.doi.org/10.1016/j.ejor.2011.03.019
Aparece nas colecções:Ciências e Tecnologia - Artigos em revistas internacionais / Papers in international journals

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
SATRCPSP.pdf429,18 kBAdobe PDFVer/Abrir    Acesso Restrito. Solicitar cópia ao autor!


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.