Publication
Aplicação de algoritmos de partição e geração de colunas ao agendamento de máquinas paralelas
| dc.contributor.author | Duarte, António | |
| dc.date.accessioned | 2010-01-26T17:22:27Z | |
| dc.date.available | 2010-01-26T17:22:27Z | |
| dc.date.issued | 2005 | |
| dc.description.abstract | 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. | pt |
| dc.description.sponsorship | Prodep, Fundo Social Europeu | pt |
| dc.identifier.citation | 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 | pt |
| dc.identifier.tid | 101149310 | |
| dc.identifier.uri | http://hdl.handle.net/10198/1479 | |
| dc.language.iso | por | pt |
| dc.publisher | Universidade do Minho | pt |
| dc.subject | Branch-and-price | pt |
| dc.subject | Sequenciamento | pt |
| dc.subject | Geração de colunas | pt |
| dc.title | Aplicação de algoritmos de partição e geração de colunas ao agendamento de máquinas paralelas | pt |
| dc.type | doctoral thesis | |
| dspace.entity.type | Publication | |
| person.familyName | Duarte | |
| person.givenName | António | |
| person.identifier.ciencia-id | 9C13-787B-295F | |
| person.identifier.orcid | 0000-0003-3759-3850 | |
| person.identifier.rid | H-4473-2011 | |
| person.identifier.scopus-author-id | 36967901400 | |
| rcaap.rights | openAccess | pt |
| rcaap.type | doctoralThesis | pt |
| relation.isAuthorOfPublication | 40f0f385-492d-4c6c-8949-2480688b1666 | |
| relation.isAuthorOfPublication.latestForDiscovery | 40f0f385-492d-4c6c-8949-2480688b1666 |