Publicação
Aplicação de algoritmos de partição e geração de colunas ao agendamento de máquinas paralelas
| 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. |
|---|---|
| Autores principais: | Duarte, António |
| Assunto: | Branch-and-price Sequenciamento Geração de colunas |
| Ano: | 2005 |
| País: | Portugal |
| Tipo de documento: | tese de doutoramento |
| Tipo de acesso: | acesso aberto |
| Instituição associada: | Universidade Politécnica de Bragança |
| Idioma: | português |
| Origem: | Biblioteca Digital da UPB |
| 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. |
|---|
Atividades financiadas
Não foram encontrados projetos financiados.