Aplicação de algoritmos de partição e geração de colunas ao agendamento de máquinas paralelas

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.

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.