Mémoire de Maîtrise
DOI
https://doi.org/10.11606/D.45.2013.tde-07082013-145142
Document
Auteur
Nom complet
José EurÃpedes Ferreira de Jesus Filho
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2013
Directeur
Jury
Birgin, Ernesto Julian Goldberg (Président)
Costa, Alysson Machado
Ferreira, Carlos Eduardo
Titre en portugais
Método beam search aplicado ao problema de escalonamento de tarefas flexÃvel
Mots-clés en portugais
Beam Search
escalonamento
Job Shop
método heurÃstico
Resumé en portugais
O Job Shop Scheduling Problem é um problema NP-DifÃcil que chama a atenção de muitos pesquisadores devido seu desafio matemático e sua aplicabilidade em contextos reais. Geralmente, principalmente em cenários próximos aos de fábricas e indústrias, obter um escalonamento ótimo por meio de métodos computacionais exatos implica em um alto desprendimento de tempo. Em contrapartida, devido à s exigências de um mercado cada vez mais competitivo, as decisões de onde, como, quando e com o que produzir devem ser tomadas rapidamente. O presente trabalho propõe o desenvolvimento de um método heurÃstico Beam Search para solucionar o Job Shop Scheduling Problem e o Flexible Job Shop Scheduling Problem. Para isso, inicialmente um algoritmo do tipo list scheduling é definido e então o método Beam Search é construÃdo baseado neste algoritmo. Os métodos propostos foram avaliados em diferentes nÃveis de complexidade utilizando instâncias da literatura que retratam diferentes cenários de planejamento. Em linhas gerais, as soluções encontradas se mostraram bastante competitivas quando comparadas a outras soluções da literatura.
Titre en anglais
Beam search method applied to the flexible job shop scheduling problem
Mots-clés en anglais
Beam Search
heuristic method
Job Shop
schedule.
Resumé en anglais
The Job Shop Scheduling Problem is a NP-Hard problem which draws the attention of researchers due to both its mathematical challenge and its applicability in real contexts. Usually, mainly in industry and factory environments, an optimal schedule got by the use of exact computational methods implies in a long spending time. On the other hand, due to a more and more competitive marketplace, the decisions on where, how, when and with which to produce must be taken quickly. The present work proposes the development of an heuristic Beam Search method to solve both the Job Shop Scheduling Problem and the Flexible Job Shop Scheduling Problem. To that end, at rst a list scheduling algorithm is dened and then the Beam Search method is built based on the list scheduling algorithm. The proposed methods were evaluated over dierent complexity levels using instances from the literature that report dierent planning environments. In general terms, the solutions implemented have been proved very competitive when compared against other solutions in the literature.
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.
Dissertacao.pdf (973.59 Kbytes)
Date de Publication
2013-08-14
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées
cliquant ici.