Novos limitantes inferiores para o método branch-and-bound na solução de problemas flowshop permutacional

Página do item simplificado
dc.contributorUniversidade de São Paulo
dc.contributor.authorTomazella, Caio Paziani
dc.date.accessioned2020-06-22T14:57:13Z
dc.date.available2020-06-22T14:57:13Z
dc.date.issued2019-06-26
dc.description.abstractEm um contexto industrial, a programação da produção tem como objetivo alocar recursos para operações de forma a aumentar a eficiência operacional do processo de fabricação. Esta programação pode ser modelada na forma de problemas de sequenciamento de tarefas, que são resolvidos visando minimizar um determinado critério de desempenho. A aplicação de métodos exatos nestes problemas possibilita encontrar a solução ótima, tanto para aplicação direta como para a validação de métodos heurísticos e metaheurísticas. Entretanto, a literatura mostra que os métodos exatos, tanto a resolução do problema pela modelagem em programação linear-inteira mista como o branch-and-bound, têm sua aplicação restrita à problemas de menores tamanhos. O objetivo deste trabalho é propor novas formulações de limitantes inferiores para a aplicação do branch-and-bound em problemas de flowshop permutacional visando aumentar sua eficiência e aplicabilidade. Os limitantes propostos são avaliados em problemas de flowshop permutacional com tempos de setup dependente da sequência, tendo como critérios de desempenho o tempo de fluxo total e o atraso total. A avaliação da aplicabilidade de cada limitante é feita através do número de nós explorados e o tempo computacional gasto pelo branch-and-bound para resolver problemas de diversos tamanhos.
dc.description.abstractIn an industrial context, production sequencing aims at allocating resources for job processing while increasing manufacturing efficiency. This task can be modelled in the form of scheduling problems, which are solved by minimizing a pre-determined performance criterion. The use of exact methods allows the optimal solution to be found, which can be applied directly in the manufacturing shop or used to validate heuristic and metaheuristic methods. However, the literature shows that MILP and branch-and-bound, both exact methods, are restrained to small-sized scheduling problems. The aim of this project is to propose new lower bound formulations to be used in the branch-and-bound method for permutational flowshop probems, in order to extend its efficiency and applicability. The proposed bounds are tested in permutational flowshop problems with sequence dependent setup times, and using as performance criteria the total flow time and the total tardiness. The evaluation of each lower bounds applicability is done considering the number of explored nodes and the required computational time for the branch-and-bound to solve problem instances of different sizes.
dc.formatapplication/pdf
dc.identifier.doi10.11606/D.18.2019.tde-13062019-102723
dc.identifier.urihttp://www.teses.usp.br/teses/disponiveis/18/18156/tde-13062019-102723/
dc.identifier.urihttp://repositorio.eesc.usp.br/handle/RIEESC/6668
dc.languagept
dc.rights.holderTomazella, Caio Paziani
dc.subjectbranch-and-bound
dc.subjectflowshop permutacional
dc.subjectscheduling
dc.subjectsetup dependente da sequência
dc.subjectatraso total
dc.subjecttempo de fluxo total
dc.subjecttotal flow time
dc.subjectsequence dependent setup times
dc.subjectscheduling
dc.subjectpermutation flowshop
dc.subjectbranch-and-bound
dc.subjecttotal tardiness
dc.titleNovos limitantes inferiores para o método branch-and-bound na solução de problemas flowshop permutacional
dc.title.alternativeNew lower bounds for the branch-and-bound method for solving permutation flowshop problems
dc.typeDissertação de Mestrado
Arquivos
Coleções
Teses e Dissertações (BDTD USP)