Utilize este identificador para referenciar este registo:
https://hdl.handle.net/1822/4567
Título: | Aplicação de algoritmos de partição e geração de colunas ao agendamento de máquinas paralelas |
Outro(s) título(s): | Application of branch-and-price to parallel machine scheduling |
Autor(es): | Duarte, António Jorge da Silva Trindade |
Orientador(es): | Carvalho, J. M. Valério de |
Data: | 16-Jan-2006 |
Resumo(s): | 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. This work presents an algorithm for solving exactly a scheduling problem with identical parallel machines and malleable tasks, subject to arbitrary release dates and due dates. The objective is to minimize a function of the late work and of the setup costs. A malleable task is such that the set of processors allotted to its processing can be freely chosen and, possibly, modified over time. Obviously, for each preemption there is a corresponding setup cost to be considered in the objective function. To approach this problem, we propose an integer programming formulation and we apply the Dantzig-Wolfe decomposition to it in order to solve the problem by column generation. On the decomposed model, each column represents the schedule of a single machine and the goal of the subproblem algorithm is to provide new valid and attractive schedules that can be included in the global schedule. For the branching phase, we developed an equivalent network flow model and the branching is made on the variables corresponding to flows on arcs of this formulation. There is a mathematical relation between the variables of this network flow model and the variables of the original model. We also developed heuristics for local improvement of valid solutions and a heuristic for rounding any non integral solution. Besides, we studied two special cases of the problem: the problem with an orderable task set and the problem with common time windows. Finally, we carried out an extensive set of computational tests to verify the algorithm’s efficiency and to determine the model’s sensitivity to instance size parameters: the number of machines, the number of tasks and the size of the planning horizon. |
Tipo: | Tese de doutoramento |
Descrição: | Tese de doutoramento em Engenharia de Produção e Sistemas área de Investigação Operacional. |
URI: | https://hdl.handle.net/1822/4567 |
Acesso: | Acesso aberto |
Aparece nas coleções: |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Tese A Duarte (Final).pdf | 684,19 kB | Adobe PDF | Ver/Abrir |