Algoritmos multiobjetivos para o problema de sequenciamento de tarefas em uma máquina com tempo de preparação dependente da sequência e da família.
No Thumbnail Available
Date
2013
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
Abstract
Este trabalho trata do Problema de Sequenciamento de Tarefas em Uma Máquina com Tempo de Preparação Dependente da Sequência e da Família. Nesse problema, um conjunto de tarefas devem ser processadas por uma máquina, sendo que antes da execução de cada tarefa é necessário um tempo para preparar a máquina, o qual é de nido de acordo com a sequência e a família da tarefa. Desta forma, o tempo de preparação da máquina é requerido, apenas, para executar duas tarefas consecutivas que pertencem a famílias diferentes. Consideram-se os objetivos de minimizar o makespan e o atraso total ponderado. Para resolvê-lo, foram analisados sete algoritmos de otimização multiobjetivo. O primeiro é o Multi-objective Variable Neighborhood Search (MOVNS), que é um método de otimização multiobjetivo baseado na metaheur ística Variable Neighborhood Search (VNS). O segundo e o terceiro são duas variantes do MOVNS encontradas na literatura, denominadas MOVNS_Ottoni e MOVNS_Arroyo, que consistem em adicionar um procedimento de intensi cação no MOVNS. O quarto é o Pareto Iterated Local Search (PILS), que é um algoritmo multiobjetivo de busca local com características semelhantes à metaheurística Iterated Local Search (ILS). O quinto é uma variante do PILS proposta neste trabalho, denominada PILS1, em que um novo procedimento de perturbação é desenvolvido. O sexto e o sétimo são o Nondominated Sorting Genetic Algorithm II (NSGA-II) e o Strength Pareto Evolutionary Algorithm 2 (SPEA2), os quais são métodos de otimização baseados no processo de evolução natural para problemas multiobjetivos. Entre os sete algoritmos, cinco são de busca local: MOVNS, MOVNS_Ottoni, MOVNS_Arroyo, PILS e PILS1, e outros dois são de busca populacional: NSGA-II e SPEA2. Esses algoritmos foram comparados em relação às métricas de cardinalidade, distância média, distância máxima, diferença de hipervolume e epsilon. Os resultados computacionais realizados em instâncias-teste geradas aleatoriamente mostraram que o algoritmo PILS1 é estatisticamente superior a todos os outros algoritmos em relação às métricas cardinalidade, distância média, diferença de hipervolume e métrica epsilon, em termos de resultados médios. O PILS1 conseguiu também o melhor resultado médio para a métrica distância máxima; entretanto, a partir da análise estatística não foi possível a rmar que a diferença observada entre ele o NSGA-II era signi cativa.
Description
Keywords
Problema de sequencialmento em única máquina, Otimização multiobjetivo, Ciência da computação, Máquina - sequenciamento de tarefas
Citation
REGO, M. F. Algoritmos multiobjetivos para o problema de sequenciamento de tarefas em uma máquina com tempo de preparação dependente da sequência e da família. 2013. 64 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Ouro Preto, Ouro Preto, 2013.