Please use this identifier to cite or link to this item: http://ri.ufs.br/jspui/handle/riufs/10678
Document Type: Dissertação
Title: Otimização com muitos objetivos por múltiplos enxames aplicada ao escalonamento dinâmico de projetos de software
Authors: Amaral, Rodrigo Octávio Melo do
Issue Date: 31-Aug-2018
Advisor: Carvalho, André Britto de
Co-advisor: Almeida e Silva, Leila Maciel de
Resumo : Os processos da Engenharia de Software geralmente envolvem problemas com requisitos e restrições conflitantes. Para a solução desses problemas, recentemente surgiu o conceito de Search Based Software Engineering (SBSE). A SBSE consiste basicamente no uso de algoritmos de busca e otimização para encontrar soluções de forma automática e equilibrar o compromisso entre os objetivos dos problemas comuns a suas várias ramificações. Uma das áreas da SBSE ocupa-se do gerenciamento de projetos de software, sendo que um de seus principais desafios é o problema de escalonamento de projetos de software (SPSP, do inglês Software Project Scheduling Problem). Soluções para este problema buscam montar um cronograma de projeto de modo que a alocação dos empregados às tarefas disponíveis minimize tanto a duração total do projeto quanto seu custo final, caracterizando o SPSP como um problema de otimização multiobjetivo. No entanto, o ambiente de projetos de software está sujeito a muitas incertezas, o que faz com que o espaço de soluções possíveis se transforme ao longo do tempo. Essa natureza dinâmica traz a necessidade de que os cronogramas sejam também estáveis e robustos frente a mudanças, introduzindo novos objetivos a serem conciliados. Assim, nessa nova abordagem o SPSP é modelado como um problema de otimização dinâmica com muitos objetivos (quando há mais de três funções objetivo). Este trabalho tem como objetivo investigar a aplicação de algoritmos de otimização multiobjetivo ao problema de escalonamento dinâmico de projetos de software (DSPSP). Para isso, foi utilizada a meta-heurística de otimização por múltiplos enxames de partículas, abordagem ainda pouco explorada para aplicação ao DSPSP. O algoritmo proposto explora características do problema, buscando conciliar tanto o aspecto de otimização dinâmica, por meio do uso de múltiplas populações, quanto o de ser um problema com muitos objetivos, por meio dos métodos de arquivamento. Além da utilização de múltiplos enxames, o trabalho explora também o uso de mais dois algoritmos multiobjetivo já aplicados a outros problemas na área de SBSE, porém ainda não aplicados ao problema de SPSP dinâmico. Em conjunto com a otimização por múltiplos enxames, são exploradas ainda algumas estratégias heurísticas dinâmicas para a inicialização das populações, de forma a aproveitar características das melhores soluções já encontradas. Essas estratégias também são aplicadas aos demais algoritmos avaliados, a fim de verificar como elas influenciam o desempenho. A validação do algoritmo é feita por meio de um conjunto de experimentos que comparam o algoritmo proposto com dois algoritmos consagrados da literatura (NSGA-II e SMPSO).
Abstract: Software engineering processes often involve problems with mutually conflicting requirements and constraints. To address these issues, the concept of Search-Based Software Engineering (SBSE) has emerged. SBSE consists on using search and optimization algorithms to balance the compromise between the objectives of the problems common to its various domains. One of these sub-areas deals with software project management, one of its main challenges being the Software Project Scheduling Problem (SPSP). Solutions to this problem aim to assemble a project schedule so that employee allocation to available tasks minimizes both the total project duration and its final cost. However, a software project environment is subject to many uncertainties, which makes the solution landscape change over time. This dynamic nature demands schedules to be stable and robust to changes, introducing new objectives to be reconciled into the problem. Because this dynamic formulation of SPSP is still under-explored, it is believed that it is possible to explore new meta-heuristics, incorporate features of the problem, and use many-objective optimization techniques to solve it. The objective of this work is to investigate how multiobjective algorithms can be applied to solve the Dynamic Software Project Scheduling problem (DSPSP). This work uses the meta-heuristic of optimization by multiple swarms of particles, an approach not yet explored when applied to DSPSP. The proposed algorithm also explores the problem characteristics, seeking to reconcile both the dynamic optimization aspect, by using multiple populations, as the fact it is many-objective problem, by using archiving methods. In addition to using multiple swarns, this work also explores the use of two multi-objective algorithms already applied to other problems in SBSE area, but not yet applied to DSPSP. In addition to multi-swarm optimization, some dynamic heuristic strategies for population initialization are explored to take advantage of the features of the best solutions already found. These strategies are also applied to the other evaluated algorithms in order to verify how they influence performance. The algorithm validation is done through a set of experiments which compared the proposed algorithm with two popular algorithms in literature (NSGA-II and SMPSO).
Keywords: Escalonamento de projetos
Search-based software engineering
Otimização com muitos objetivos
Múltiplos enxames
Project scheduling
Many objective optimization
Multiple swarm
Subject CNPQ: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language: por
Institution: Universidade Federal de Sergipe
Program Affiliation: Pós-Graduação em Ciência da Computação
Citation: AMARAL, Rodrigo Octávio Melo do. Otimização com muitos objetivos por múltiplos enxames aplicada ao escalonamento dinâmico de projetos de software. 2018. 79 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Sergipe, São Cristóvão, SE, 2018.
URI: http://ri.ufs.br/jspui/handle/riufs/10678
Appears in Collections:Mestrado em Ciência da Computação

Files in This Item:
File Description SizeFormat 
RODRIGO_OCTAVIO_MELO_AMARAL.pdf2,9 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.