• 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
 
 
Tese de Doutorado
DOI
10.11606/T.3.2014.tde-26122014-152423
Documento
Autor
Nome completo
Guilherme Barroso Mainieri
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2014
Orientador
Banca examinadora
Ronconi, Debora Pretti (Presidente)
Mesquita, Marco Aurélio de
Nagano, Marcelo Seido
Poldi, Kelly Cristina
Santoro, Miguel Cezar
Título em português
Meta-heurística BRKGA aplicada a um problema de programação de tarefas no ambiente flowshop híbrido.
Palavras-chave em português
Atraso total
BRKGA
Flowshop flexível
Flowshop híbrido
Resumo em português
O presente trabalho aborda o ambiente de produção conhecido como flowshop híbrido. Devido a crescente complexidade dos sistemas de produção, este ambiente é frequentemente encontrado em situações reais de manufatura. No caso estudado existem estágios em série e em cada estágio existe um número de máquinas idênticas em paralelo. Os tempos de processamento em cada estágio são dependentes da tarefa, já a rota através do sistema é a mesma para todas as tarefas. O objetivo é minimizar o atraso total, ou seja, a soma do atraso de todas as tarefas. Um modelo de programação linear inteira mista é apresentado para este problema e, dada a sua complexidade, ele é abordado através de uma meta-heurística relativamente nova e que, conforme revisão da literatura, nunca foi aplicada a este problema. Conhecida por BRKGA (Biased Random-Key Genetic Algorithm), este método codifica as soluções de maneira a obter um melhor desempenho em comparação com algoritmos genéticos tradicionais. Com o objetivo de avaliar a melhor estratégia, são propostas diversas versões de BRKGA para o problema considerado. Estas versões buscam explorar características das melhores heurísticas construtivas da literatura, dentre estas: ordens direta e inversa de programação das tarefas dentro do ambiente produtivo, identificação do estágio gargalo e diferenciação da programação do gargalo dos demais estágios. Experimentos computacionais foram realizados com 432 problemas teste de grande porte. Os métodos apresentados são comparados entre si e os resultados mostraram que uma versão do BRKGA se destaca frente às demais, visto que ela atingiu o melhor resultado em 61% dos problemas. Destaca-se que o método de melhor desempenho da literatura obteve a melhor solução em apenas 15% dos problemas. Devido às dimensões dos problemas teste da literatura, não foi possível encontrar suas soluções ótimas. Deste modo, este trabalho propõe um novo limitante inferior para o mínimo atraso total. Além disso, 576 novos problemas teste de menores dimensões são propostos e seus resultados ótimos são utilizados para aprofundar as comparações. Os resultados deste experimento indicaram que o BRKGA proposto apresentou um bom desempenho visto que, na média, seus resultados estão apenas a 2,4% dos resultados ótimos.
Título em inglês
BRKGA meta-heuristic for a scheduling problem in hybrid flowshops.
Palavras-chave em inglês
BRKGA
Flexible flowshop
Hybrid flowshop
Total tardiness
Resumo em inglês
This work addresses a scheduling problem in hybrid flowshops. Due to the increasing complexity of production systems, this production environment is often encountered in real manufacturing situations. In hybrid flowshops, there are stages in series and, in each stage, a number of similar parallel machines. Processing times in each stage are dependent on the job, and the route through the system is the same for all jobs. The objective is to minimize the total tardiness, that is, the sum of all jobs tardiness. A mixed integer linear programming model is presented for the problem considered. Given its complexity, this problem is approached by a relatively new meta-heuristic, known as BRKGA (Biased Random-Key Genetic Algorithm). A literature review showed that BRKGA had never been applied to this problem. The BRKGA codes solutions in order to obtain a better performance compared with traditional genetic algorithms. Several versions of BRKGA were developed in order to evaluate the best strategy to solve the problem considered. These versions aim to exploit features of the best constructive heuristic from the literature, among them: scheduling jobs in direct and inverse order within the production environment, identification of the bottleneck stage and distinction of the bottleneck stage schedule from the others. Computational experiments were conducted with 432 large instances. The methods were compared and the results showed that one of these versions stood out against the others. This version achieved better results in 61% of instances, while the best heuristic from the literature achieved 15%. Due to the size of these instances, optimal solutions were not found. Therefore, this work develops a new lower bound for the minimum total tardiness. Additionally, in order to find optimal results, a set of 576 new instances is proposed. This experiment indicated that the BRKGA proposed performed well since, on average, their results are only 2.4% away from the optimal results.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
FichaCatalografica.pdf (16.24 Kbytes)
Tese_Mainieri.pdf (2.97 Mbytes)
Data de Publicação
2015-01-13
 
AVISO: O material descrito abaixo refere-se a trabalhos decorrentes desta tese ou dissertação. O conteúdo desses trabalhos é de inteira responsabilidade do autor da tese ou dissertação.
  • MAINIERI, G., and RONCONI, D. P. New heuristics for total tardiness minimization in a flexible flowshop [doi:10.1007/s11590-012-0448-x]. Optimization Letters [online], 2013, vol. 7, p. 665-684.
  • MAINIERI, G., e RONCONI, D. P. Regras de despacho para a minimização do atraso total no ambiente flowshop flexível [doi:10.1590/S0104-530X2010000400004]. Gestão & Produção (UFSCAR. Impresso) [online], 2010, vol. 17, p. 683-692.
  • MAINIERI, G., e RONCONI, D. P. UMA HEURÍSTICA PARA A MINIMIZAÇÃO DO ATRASO TOTAL NO AMBIENTE FLOWSHOP FLEXÍVEL. In XL Simposio Brasileiro de Pesquisa Operacional, João Pessoa, 2008. XL Simposio Brasileiro de Pesquisa Operacional. : SOBRAPO, 2008.
  • RONCONI, D. P., and MAINIERI, G. A Dispatching rule-based approach for total tardiness minimization in a flexible flowshop. In International Symposium on Mathematical Programming, Chicago, 2009. International Symposium on Mathematical Programming. : Mathematical Programming Society, 2009. Abstract.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2018. Todos os direitos reservados.