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
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
  Estamos no RCAAP Governo Português separator Ministério da Educação e Ciência   Fundação para a Ciência e a Tecnologia

Financiado por:

POS_C UE