Efficient Metaheuristics For The Dynamic Space Allocation Problem

Título: Efficient Metaheuristics For The Dynamic Space Allocation Problem

Autores: Silva, Geiza Cristina da; Bahiense, Laura; Ochi, Luiz Satoru; Boaventura-Netto, Paulo Oswaldo

Resumo: This work is devoted to the Dynamic Space Allocation Problem (DSAP), where project duration is divided into a number of consecutive periods, each of them associated with a number of activities. The resources required by the activities have to be available in the corresponding workspaces and those sitting idle during a period have to be stored. This problem contains the Quadratic Assignment Problem (QAP) as a particular case, which places it in the NP-hard class. In this context, the difficulty of identifying optimal solutions, even for instances of medium size, justifies the use of heuristic techniques. This work presents new construction and local search methods and heuristic algorithms based on the VNS and ILS metaheuristics to obtain near optimal solutions for the DSAP. Comp arisons are presented for values obtained by VNS, ILS, and results from the literature. Computational results show the proposed methods to be competitive in relation to instances in the literature and to existing techniques.

Palavras-chave: Dynamic Space Allocation Problem; Quadratic Assignment Problem; Metaheuristics; Computational Intelligence

Páginas: 8

Código DOI: 10.21528/CBIC2011-29.5

Artigo em pdf: st_29.5.pdf

Arquivo BibTex: st_29.5.bib