Biblioteca Digital do Instituto Politécnico de Bragança   Instituto Politécnico de Bragança

Biblioteca Digital do IPB >
Escola Superior de Tecnologia e Gestão >
Gestão Industrial >
DGI - Teses de Doutoramento >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10198/1479

Título: Aplicação de algoritmos de partição e geração de colunas ao agendamento de máquinas paralelas
Autor: Duarte, António J.S.T.
Palavras-chave: Branch-and-price
Sequenciamento
Geração de colunas
Issue Date: 2005
Editora: Universidade do Minho
Citação: Duarte, António J.S.T. (2005) - Aplicação de algoritmos de partição e geração de colunas ao agendamento de máquinas paralelas- Braga: Universidade do Minho. Tese de Doutoramento em Engenharia de Produção e Sistemas Área de Investigação Operacional
Resumo: No presente trabalho é proposto um algoritmo para resolver de forma exacta um problema de programação de máquinas paralelas idênticas, com tarefas maleáveis sujeitas a datas de disponibilidade e datas de conclusão arbitrárias. O objectivo é minimizar uma função do trabalho atrasado e dos custos de preparação. Considera-se que uma tarefa é maleável se o conjunto de máquinas onde é agendada puder ser escolhido e, eventualmente, modificado livremente ao longo do tempo. Evidentemente, a cada preempção realizada está associado um custo que é tido em conta na função objectivo. Para este problema é proposta uma formulação de programação inteira sobre a qual será aplicada a decomposição de Dantzig-Wolfe, com vista a resolver o problema através da geração de colunas. No modelo decomposto, cada coluna representa a agenda de uma das máquinas e a função do subproblema é gerar agendas atractivas para incluir na solução de agendamento. Para efectuar a partição foi desenvolvido um modelo de fluxo de custo mínimo equivalente e a partição é feita sobre as variáveis correspondentes a fluxos nos arcos desta formulação. Existe uma relação matemática entre as variáveis do modelo de fluxo de custo mínimo e as variáveis do modelo original. Também foram desenvolvidas heurísticas de melhoria local de soluções válidas e uma heurística de arredondamento de quaisquer soluções fraccionárias. Para além disso, foram estudados dois casos particulares do problema: o problema com tarefas ordenáveis e o problema com janelas de agendamento comuns. Finalmente, foi levado a cabo um largo conjunto de testes computacionais para verificar a eficiência dos vários algoritmos propostos e para determinar a sensibilidade do modelo a parâmetros de dimensão da instância: o número de máquinas, o número de tarefas e o tamanho do horizonte de agendamento.
URI: http://hdl.handle.net/10198/1479
Appears in Collections:DGI - Teses de Doutoramento

Files in This Item:

File Description SizeFormat
Tese A Duarte (Final).pdf684,19 kBAdobe PDFView/Open

Please give feedback about this item
Statistics
FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpaceOrkut
Formato BibTex mendeley Endnote Logotipo do DeGóis 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 


© Instituto Politécnico de Bragança - Biblioteca Digital - Feedback - Statistics
Promotores do RCAAP   Financiadores do RCAAP

Fundação para a Ciência e a Tecnologia Universidade do Minho   Governo Português Ministério da Educação e Ciência PO Sociedade do Conhecimento (POSC) Portal oficial da União Europeia