• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Master's Dissertation
DOI
10.11606/D.18.2011.tde-25042011-114532
Document
Author
Full name
Felipe Marcus Carneiro
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2010
Supervisor
Committee
Nagano, Marcelo Seido (President)
Moccellin, João Vitor
Oliveira, Marcio Mattos Borges de
Title in Portuguese
Avaliação de métodos heurísticos para a solução do problema de programação flowshop com tempos de setup assimétricos e dependentes da sequência
Keywords in Portuguese
Flowshop permutacional
Métodos heurísticos
Métodos meta-heurísticos
Programação da produção
Setup dependente
Abstract in Portuguese
Este trabalho é dedicado ao problema de programação em Flowshop Permutacional com tempos de preparação (setup) assimétricos e separados dos tempos de processamento e dependentes da seqüência de execução das tarefas e tem o objetivo de minimização da duração total da programação (Makespan). Através da investigação das propriedades estruturais do problema, são desenvolvidos os parâmetros XR e QR de uma programação, que indicam ociosidade das máquinas (para valores positivos) e bloqueio das tarefas (para valores negativos). Os novos parâmetros são utilizados para propor uma melhoria no cálculo eficiente de Makespan proposto por Taillard (1990). Esta melhoria é então utilizada no desenvolvimento de uma nova heurística construtiva baseada no método NEHT-RB de Ríos-Mercado e Bard (1998b) denominada CNIT, que é comparada durante a experimentação computacional com os métodos SETUP e TOTAL, de Simons (1992) com pequenas melhorias; com a proposta da utilização da propriedade UBX de Moccellin e Nagano (2007); e com o método NEHT-RB. Os métodos são então submetidos a uma busca local descendente como proposta em Ruiz e Stützle (2008) e seus desempenhos como soluções iniciais para este procedimento de busca local são avaliados. Em seguida, um método melhorativo derivado do novo método construtivo e baseado na meta-heurística IG de Ruiz e Stützle (2008) é proposto e denominado CNIT-IG. O método é comparado com a heurística IG original submetida às diferentes soluções iniciais estudadas durante a avaliação da nova heurística construtiva. As comparações são realizadas utilizando-se o banco de dados de Taillard (1990) para o flowshop permutacional adaptado para o problema de flowshop com tempos de setup assimétricos e dependentes da seqüência. Os resultados da experimentação computacional são analisados em termos da porcentagem média de sucesso, do desvio relativo médio e em relação ao tempo médio computacional e mostram a superioridade dos resultados da nova heurística construtiva CNIT e seu alto custo computacional, de complexidade mn³. Os resultados mostram ainda a superioridade da meta-heurística CNIT-IG sobre o método IG.
Title in English
Heuristic methods evaluation for solution of flowshop scheduling problems with asymmetric sequence dependent setup times
Keywords in English
Heuristics
Metaheuristcs
Permutational flowshop
Production schedule
Sequence dependent setup times
Abstract in English
This work addresses the Permutation Flowshop scheduling problem with separated sequence-dependent setup times with the objective of minimizing Makespan. Through the investigation of the problem structural properties, two scheduling parameters XR e QR are developed, they indicate the machine idleness (for positive values) and task blocking (for negative values). These new parameters are used to propose an improvement in the efficient makespan calculation as stated by Taillard (1990). This improvement is then used for development of a new constructive heuristic based on Ríos-Mercado and Bard (1998b) method NEHT-RB nominated CNIT, and it is compared during computational experimentation with the methods SETUP and TOTAL of Simons (1992), with slight improvements; with the proposal of property UBX from Moccellin and Nagano (2007) and with NEHT-RB method. The methods are then submitted to descent local search as proposed in Ruiz and Stützle (2008) and its performance as initial solutions for this local search procedure is evaluated. Next, an improvement method derivate from the new constructive method and based on metaheuristic IG from Ruiz and Stützle (2008) is proposed and nominated CNIT-IG. This method is compared with original IG submitted to different initial solutions studied during constructive heuristic evaluation. Comparisons are done using Taillards instances (1990) for standard flowshop and adapted to the flowshop with sequencedependent setup times problem. The results of computation experimentation are analyzed in terms of average percentage of success, average relative percentage deviation and average computational time and show superiority of new constructive heuristic CNIT-IG and its high computational cost, with complexity mn³. The results also show superiority of metaheuristic CNIT-IG over IG method.
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2011-04-27
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
Centro de Informática de São Carlos
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2020. All rights reserved.