• 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
 
 
Thèse de Doctorat
DOI
10.11606/T.18.2017.tde-16032017-104814
Document
Auteur
Nom complet
Mauricio Iwama Takano
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Carlos, 2016
Directeur
Jury
Nagano, Marcelo Seido (Président)
Azzolini Junior, Walther
Carneiro, Marcelo Bertolete
Oliveira, Marcio Mattos Borges de
Sagawa, Juliana Keiko
Titre en portugais
Uma contribuição para o problema de programação de operações flow shop com buffer zero e tempos de setup dependente da sequência e da máquina
Mots-clés en portugais
Branch-and-Bound
Buffer zero
Flow shop
Setup dependente
Bloqueio
Métodos heurísticos
Programação da produção
Programação inteira mista
Resumé en portugais
O problema do sequenciamento da produção diz respeito à alocação das tarefas nas máquinas em um ambiente de fabricação, o qual vem sendo amplamente estudado. O sequenciamento pode variar em tamanho e complexidade dependendo do tipo de ambiente onde ele é aplicado, do número e tipos de restrições tecnológicas e da função objetivo do problema. A utilização de métodos de decisão para a solução de problemas de sequenciamento na indústria depende de modelos que sejam capazes de oferecer soluções para os problemas reais, que geralmente envolvem diversas restrições, os quais devem ser considerados simultaneamente. No presente trabalho o problema de sequenciamento da produção em ambientes flow shop permutacionais, com bloqueio com buffer zero, e com tempos de setup dependente da sequência e da máquina, com o objetivo de minimização do makespan é estudado, sendo este considerado um problema NP-Completo. O problema é pouco explorado na literatura. No presente trabalho é apresentado um procedimento de cálculo para o makespan e três métodos de solução para o problema: quatro limitantes inferiores para o procedimento Branch-and-Bound; quatro modelos MILP, sendo dois deles adaptados; e 28 modelos heurísticos construtivos adaptados para o problema. Os métodos desenvolvidos baseiam-se em propriedades matemáticas do problema que são apresentadas neste trabalho como limitante inferior e limitante superior. Dentre todos os modelos MILP, o modelo adaptado RBZBS1 obteve os melhores resultados para os problemas menores e o modelo desenvolvido TNZBS1 obteve os melhores desvios relativos médios do makespan para os problemas maiores, que não foram resolvidos dentro do limite de tempo computacional estipulado. O limitante inferior para o Branch-and-Bound LBTN2 foi melhor que os demais tanto no tempo computacional e no número de nós explorados como também no número de problemas não resolvidos e no desvio relativo médio do makespan. Foi realizado uma comparação entre o melhor modelo MILP e o melhor limitante inferior para o Branch-and-Bound, sendo que o último obteve melhores resultados para os problemas testados. Entre os métodos heurísticos adaptados, o PF foi o que obteve, de uma forma geral, os melhores resultados em todas as fases.
Titre en anglais
A contribution to the flow shop problem with zero buffer and sequence and machine dependent setup times
Mots-clés en anglais
Blocking
Branch-and-Bound
Dependent setup
Flow shop
Heuristic methods
Mixed integer program
Production scheduling
Zero buffer
Resumé en anglais
Production scheduling is defined as a problem of allocating jobs in machines in a production environment and it has been largely studied. The scheduling can vary in difficulty and complexity depending on the environment, the variety and types of technological restraints and the objective function of the problem. The use of decision making methods to solve scheduling problems in the industry needs models that are capable to solve real problems, that usually involve a big variety of restraints that have to be simultaneously studied. At the present work the scheduling problem in a permutational flow shop environment, considering blocking with zero buffer, and sequence and machine dependent setup times, with the objective of minimizing makespan is studied, which is considered a NP-Complete problem and little explored in literature. The work presents a calculation procedure for the makespan and three solution methods for the problem: four lower bounds for the Branch-and-Bound procedure; four MILP models, two of which are adapted; and 28 constructive heuristic methods adapted to the problem. The methods developed are based on mathematical properties of the problem that are presented in this work as a lower bound and an upper bound. Among all the MILP models, the adapted model RBZBS1 was the one to obtain the best results for the smaller problems, and the developed model TNZBS1 obtained the smallest mean relative deviation of the makespan for the bigger problems that were not solved within the specified computational time limit. The lower bound for the Branch-and-Bound LBTN2 obtained smaller computational times and number of explored nodes as well as the number of unsolved problems and the mean relative deviation for the makespan than all other lower bounds. Also, a comparison among the best MILP model and the best lower bound for the Branch-and-Bound was performed, being that the last obtained better results for the tested problems. Among the adapted heuristic methods, the PF heuristic was the one that obtained, in general, the better results in all phases.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2017-03-24
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2021. Tous droits réservés.