Greedy randomized adaptive evolutionary path relinking aplicado a problemas de máquinas paralelas não relacionadas com recursos renováveis

Abstract

Resumo: Esta dissertação aborda o problema de máquinas paralelas não relacionadas, com restrição de recursos renováveis (UPMR), para minimizar o makespan. Para este problema é proposto um Greedy Randomized Adaptive Evolutionary Path-Relinking (GRAEPR) e uma abordagem híbrida com um modelo de programação por restrição (CP). Os resultados apresentam soluções competitivas com as presentes na literatura, estabelecendo alguns novos Lower e Upper Bounds. Além disso, é apresentada uma extensão para este problema. É introduzido o problema de máquinas paralelas não relacionadas, com setup dependente e restrição de recursos renováveis (UPMSR). Para este problema é apresentado um modelo de programação inteira mista (MILP), um modelo de programação por restrição e uma uma adaptação da abordagem de Fleszar e Hindi (2018). Além disso, são modificadas as abordagens do Greedy Randomized Adaptive Evolutionary Path-Relinking e híbrida desenvolvidas para o UPMR. Um conjunto de instâncias é gerada para UPMSR e os resultados evidenciam o potencial existente na abordagem GRAEPR. Palavras-chaves: Máquinas paralelas não relacionadas. Restrição de recursos Renováveis. Programação linear inteira mista. Programação por restrição. Path-relinking.

Abstract: This thesis addresses the problem of unrelated parallel machines, with restriction of renewable resources (UPMR), to minimize the makespan. For this problem, a Greedy Randomized Adaptive Evolutionary Path-Relinking (GRAEPR) and a hybrid approach with a constraint programming (CP) model is proposed. The results show competitive solutions with those found in the literature, establishing some new values for Lower and Upper Bounds. In addition, an extension is presented for this problem. We introduce the problem of unrelated parallel machines, with dependent setup and restriction of renewable resources (UPMSR). For this problem, we present a mixed integer linear programming (MILP) model, a contraint programming (CP) model, and an adaptation of the approach of Fleszar and Hindi (2018). We also modify the Greedy Randomized Adaptive Evolutionary Path-Relinking and the hybrid approach developed for the UPMR. A set of instances is generated for UPMSR and the results show the potential that exists in the GRAEPR approach. Key-words: Unrelated parallel machines. Renewable resource constraint. Mixed-integer linear programming. Constraint programming. Path-relinking