Otimização bi-objetivo para o problema de sequenciamento de tarefas em uma maquina com tempos de preparação dependentes da sequencia
Rodrigo Moreira Carvalho
DISSERTAÇÃO
Português
(Broch.)
T/UNICAMP C253o
Campinas, SP : [s.n.], 2002.
121p. : il.
Orientador : Vinicius Amaral Armentano
Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação
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...
Ver mais
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
Ver menos
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...
Ver mais
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
Ver menos
Otimização bi-objetivo para o problema de sequenciamento de tarefas em uma maquina com tempos de preparação dependentes da sequencia
Rodrigo Moreira Carvalho
Otimização bi-objetivo para o problema de sequenciamento de tarefas em uma maquina com tempos de preparação dependentes da sequencia
Rodrigo Moreira Carvalho
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra