PPGCC - Programa de Pós-graduação em Ciência da Computação

URI permanente desta comunidadehttp://www.hml.repositorio.ufop.br/handle/123456789/596

Navegar

Agora exibindo 1 - 4 de 4

Uma abordagem evolucionária para o problema escalonamento de tarefas em máquinas idênticas paralelas com limitações de ferramentas.
(2018) Soares, Leonardo Cabral da Rocha; Carvalho, Marco Antonio Moreira de; Carvalho, Marco Antonio Moreira de; Toffolo, Túlio Ângelo Machado; Arroyo, José Elias Claudio
O Problema de Escalonamento de Tarefas em Máquinas Flexíveis Paralelas Idênticas com Restrições de Ferramentas, consiste em alocar tarefas a um conjunto de máquinas flexíveis paralelas, com o objetivo de minimizar o tempo máximo de processamento das tarefas pelas máquinas. Especificamente, as tarefas possuem tempo de processamento igual em qualquer máquina, porém, possuem tempo de preparo prévio que depende de todas as tarefas anteriores sequenciadas na mesma máquina, devido a configurações de ferramentas nas máquinas flexíveis. Neste trabalho, este problema NP-Difícil é abordado utilizando-se a metaheurística paralela Algoritmo Genético de Chaves Aleatórias Viciadas hibridizada com procedimentos de busca local organizados em uma Descida em Vizinhança Variável. São apresentados resultados inéditos para um conjunto de 2880 instâncias da literatura, incluindo resultados ótimos para 12,31% entre as menores instâncias. O método proposto é comparado ao atual estado da arte e obtém 91,81% das melhores soluções. Novas melhores soluções são apresentadas para 52,75% do total de instâncias. Adicionalmente, o método proposto apresenta tempo de execução 92,69% menor, dominando assim o atual estado da arte.
Estratégias de otimização contínua Caixa-Cinza para problemas de larga escala.
(2021) Costa, Rodolfo Ayala Lopes; Freitas, Alan Robert Resende de; Freitas, Alan Robert Resende de; Carvalho, Marco Antonio Moreira de; Toffolo, Túlio Ângelo Machado; Arroyo, José Elias Claudio; Guimarães, Frederico Gadelha
A otimização caixa-cinza tem emergido como uma alternativa promissora aos tradicionais métodos de otimização caixa-preta, uma vez que esses métodos tradicionais deterioram seu desempenho ao lidar com problemas de larga escala. Embora trabalhos relacionados à otimização caixa-cinza tenham sido introduzidos na literatura nos últimos anos, há uma carência de estudos sobre essa abordagem no contexto de otimização contínua. Os problemas de otimização contínua representam uma importante subclasse de problemas práticos de otimização. Em particular, estudos sobre otimização contínua de problemas de larga escala vem recebendo especial atenção na última década. Nesse contexto, este trabalho se propõe a estudar e desenvolver diferentes abordagens caixa-cinza para lidar com essa subclasse de problemas. Para isso, definições matemáticas de separabilidade de problemas de otimização que são a base teórica para implementação das abordagens caixa-cinza são apresentadas e discutidas. Baseados nessas definições, diferentes algoritmos caixa-cinza foram propostos neste estudo. Um estudo experimental utilizando um conjunto de problemas de otimização contínua de larga escala foi proposto para investigar o desempenho das abordagens introduzidas. Os resultados demonstram um desempenho promissor das abordagens caixa-cinza em comparação com as versões caixa-preta. Em resumo, esses resultados demonstram a capacidade das estratégias caixa-cinza de melhorar as soluções encontradas e economizar tempo de processamento, explorando a estrutura do problema e avaliações parciais.
A mathematical formulation and heuristic algorithms for minimizing the makespan and energy cost under time-of-use electricity price in an unrelated parallel machine scheduling problem.
(2022) Rego, Marcelo Ferreira; Souza, Marcone Jamilson Freitas; Cota, Luciano Perdigão; Souza, Marcone Jamilson Freitas; Cota, Luciano Perdigão; Penna, Puca Huachi Vaz; Coelho, Igor Machado; Arroyo, José Elias Claudio; Batista, Lucas de Souza
Em muitos países, o preço da energia varia de acordo com a política time-of-use. Como regra geral, é vantajoso financeiramente para as indústrias planejarem sua produção considerando essa política. Esta tese apresenta um novo problema de sequenciamento de máquinas paralelas não-relacionadas bi-objetivo com tempos de preparação dependentes da sequência, no qual os objetivos são minimizar o makespan e o custo total de energia considerando máquinas com diferentes modos de operação e que o preço da eletricidade segue a política time-of-use. Introduzimos uma formulação de programação linear inteira mista e aplicamos o método da soma ponderada para obter uma fronteira Pareto. Também desenvolvemos métodos de otimização multiobjetivo, baseados no Multi-objective Variable Neighborhood Search com procedimento de intensificação (chamado MOVNS2) e o Non-dominated Sorting Genetic Algorithm II (NSGA-II), para tratar instâncias grandes, com pelo menos 50 tarefas, uma vez que a formulação não pode resolvê-las em um tempo computacional aceitável para a tomada de decisão. Comparamos o desempenho dos algoritmos NSGA-II e MOVNS2 com dois algoritmos de otimização multiobjetivo da literatura, o MOVNS1 e o NSGA-I, em relação às métricas de hipervolume e hierarchical cluster counting (HCC). Os resultados mostraram que os métodos propostos são capazes de encontrar uma boa aproximação para a fronteira Pareto comparado com os resultados do método de soma ponderada em instâncias pequenas, de até 10 tarefas. Quando consideramos apenas as instâncias grandes, o MOVNS2 é superior ao MOVNS1, o NSGA-I e o NSGA-II em relação à métrica de hipervolume. Além disso, o NSGA-II supera os métodos de otimização multiobjetivo NSGA-I, MOVNS1 e MOVNS2 em relaçãoo à métrica HCC. Ambos os resultados apresentam um nível de confiança de 95%. Assim, o MOVNS2 proposto é capaz de encontrar soluções não-dominadas com boa convergência e o NSGA-II com boa diversidade.
Mathematical models and heuristic algorithms for routing problems with multiple interacting components.
(2021) Chagas, Jonatas Batista Costa das; Souza, Marcone Jamilson Freitas; Santos, André Gustavo dos; Souza, Marcone Jamilson Freitas; Santos, André Gustavo dos; Barboza, Eduardo Uchoa; Arroyo, José Elias Claudio; Vidal, Thibaut Victor Gaston; Toffolo, Túlio Ângelo Machado
Muitos problemas de otimização com aplicações reais têm vários componentes de interação. Cada um deles pode ser um problema pertencente à classe N P-difícil, e eles podem estar em conflito um com o outro, ou seja, a solução ótima para um componente não representa necessariamente uma solução ótima para os outros componentes. Isso pode ser um desafio devido à influência que cada componente tem na qualidade geral da solução. Neste trabalho, foram abordados quatro problemas de roteamento complexos com vários componentes de interação: o Double Vehicle Routing Problem with Multiple Stacks (DVRPMS), o Double Traveling Salesman Problem with Partial Last-InFirst-Out Loading Constraints (DTSPPL), o Traveling Thief Problem (TTP) e Thief Orienteering Problem (ThOP). Enquanto os DVRPMS e TTP já são bem conhecidos na literatura, os DTSPPL e ThOP foram recentemente propostos a fim de introduzir e estudar variantes mais realistas dos DVRPMS e TTP, respectivamente. O DTSPPL foi proposto a partir deste trabalho, enquanto o ThOP foi proposto de forma independente. Neste trabalho são propostos modelos matemáticos e/ou algoritmos heurísticos para a solução desses problemas. Dentre os resultados alcançados, é possível destacar que o modelo matemático proposto para o DVRPMS foi capaz de encontrar inconsistências nos resultados dos algoritmos exatos previamente propostos na literatura. Além disso, conquistamos o primeiro e o segundo lugares em duas recentes competições de otimização combinatória que tinha como objetivo a solução de uma versão bi-objetiva do TTP. Em geral, os resultados alcançados por nossos métodos de soluções mostraram-se melhores do que os apresentados anteriormente na literatura considerando cada problema investigado neste trabalho.