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.

Simple item page
dc.contributor.advisorSouza, Marcone Jamilson Freitaspt_BR
dc.contributor.authorRego, Marcelo Ferreira
dc.date.accessioned2013-06-14T16:54:38Z
dc.date.available2013-06-14T16:54:38Z
dc.date.issued2013
dc.description.abstractEste 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.pt_BR
dc.description.abstractenThis work addresses the Single Machine Scheduling Problem with Sequence Dependent Family Setup Times. In this problem, there is a set of jobs to be processed by a single machine, and before the execution of each job a time to prepare the machine is required, which is de ned according to the sequence and the family of the job. Thus, the setup time is required only to perform two consecutive jobs belonging to di erent families. Two objectives were considered: the minimization of the makespan and the total weighted tardiness. In order to solve this problem, seven multi-objective algorithms were analyzed. The rst one is the Multi-objective Variable Neighborhood Search (MOVNS), which is a multi-objective optimization method based on Variable Neighborhood Search (VNS). The second and third ones are two variants of MOVNS found in the literature, here named MOVNS_Ottoni and MOVNS_Arroyo, which consists in adding an intensi cation procedure in the MOVNS. The fourth one is the Pareto Iterated Local Search (PILS), which is a multi-objective local search algorithm with similar features to the metaheuristics Iterated Local Search (ILS). The fth one is a variant of PILS proposed in this work, called PILS1, in which a new perturbation procedure is developed. The sixth and seventh ones are the Nondominated Sorting Genetic Algorithm II (NSGA-II) and the Strength Pareto Evolutionary Algorithm 2 (SPEA2), which are optimization methods based on the process of natural evolution for multi-objective problems. Among the seven algorithms, ve are based on local search: MOVNS, MOVNS_Ottoni, MOVNS_Arroyo, PILS and PILS1, and two other are populationbased: NSGA-II and SPEA2. These algorithms were compared according to cardinality, average distance, maximum distance, hypervolume di erence and epsilon metrics. The Computational results realized over test instances randomly generated show that PILS1 is statistically better than all other algorithms in relation to the cardinality, average distance, di erence of hypervolume and epsilon metrics, in terms of average results. The PILS1 produced also the best average result for the metric maximum distance; however, from the statistical analysis is not possible to a rm that the di erence between it and the NSGA-II is signi cant.
dc.identifier.citationREGO, 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.pt_BR
dc.identifier.urihttp://www.repositorio.ufop.br/handle/123456789/2915
dc.language.isopt_BRpt_BR
dc.publisherPrograma 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.pt_BR
dc.subjectProblema de sequencialmento em única máquinapt_BR
dc.subjectOtimização multiobjetivopt_BR
dc.subjectCiência da computaçãopt_BR
dc.subjectMáquina - sequenciamento de tarefaspt_BR
dc.titleAlgoritmos 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.pt_BR
dc.typeDissertacaopt_BR
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
DISSERTAÇÃO_AlgoritimosMultiobjetivosPoblemas.pdf
Size:
1.1 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.13 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
PPGCC - Mestrado (Dissertações)