Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/261853
Type: DISSERTAÇÃO
Degree Level: Mestrado
Title: Otimização bi-objetivo para o problema de sequenciamento de tarefas em uma maquina com tempos de preparação dependentes da sequencia
Author: Carvalho, Rodrigo Moreira
Advisor: Armentano, Vinícius Amaral, 1950-
Abstract: Resumo: A área de otimização combinatória multiobjetivo tem despertado crescente interesse pela sua importância prática e pela necessidade de desenvolver métodos eficientes que forneçam uma boa aproximação das soluções ótimas de Pareto. Neste trabalho é abordado o problema de seqüenciamento de tarefas em uma máquina com tempos de processamento dependentes da seqüência, datas de entrega e duas medidas de desempenho: soma do atrasos das tarefas e tempo total para processar todas as tarefas, também chamado de makespan. A minimização do makespan é equivalente à minimização do comprimento da rota no problema do caixeiro viajante assimétrico. Diversas heurísticas construtivas para cada critério propostas na literatura foram adaptadas para gerar um conjunto inicial de soluções não dominadas. Este conjunto é utilizado como partida em um método de busca em vizinhança com múltiplos recomeços. Vários tipos de vizinhanças foram testados, bem como diferentes estratégias de implementação de uma busca local multiobjetivo. Uma versão do método é testada em problemas pequenos, onde as soluções ótimas de Pareto são obtidas por enumeração completa. Para problemas grandes testa-se o desempenho relativo de diversas versões do método, e compara-se a qualidade das soluções que minimizam cada objetivo individualmente com a qualidade das soluções geradas por algoritmos mono-objetivos propostos recentemente na literatura

Abstract: The area of multio~ve combinatorial optimization has attracted the attention of researchers due to its practical importance and the need to develop efficient methods that yield a good approximation of the Pareto optimal solutions. This work addresses the sequencing of jobs in a single machine with sequence dependent setup times, due dates and two performance measures: the sum of job tardiness and the total time to process all jobs, also known as makespan. The minimization of the makespan is equivalent to the minimization of the tour length for the asymmetric traveling salesman problem. Several constructive heuristics proposed for each criterion in the literature were adapted to generate an initial set of nondominated solutions. This set is used to start a neighborhood search method with multiple restarts. Various neighborhood types were tested, as well as different strategies of implementing a multiobjective local search. A version of the method is tested for small problems, where the optimal Pareto solutions are obtained by complete enumeration. For larger problems, the relative performance of versions of the method is evaluated, and the quality of the solutions that minimize each objective is compared with the solutions generated by single-objective algorithms recently proposed in the literature
Subject: Otimização combinatória
Produção em massa
Processo decisório por critério múltiplo
Programação heurística
Problema do caixeiro viajante
Language: Português
Editor: [s.n.]
Date Issue: 2002
Appears in Collections:FEEC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Carvalho_RodrigoMoreira_M.pdf6.55 MBAdobe PDFView/Open


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