Problemas de Sequenciamento em Máquinas Paralelas
Autores
1677 |
Luciane Ferreira Alcoforado
|
710,3
|
1678 |
710,3
|
Informações:
Publicações do PESC
Problemas de Sequenciamento em Máquinas Paralelas
Luciane Ferreira Alcoforado
Novembro/1998
Orientador: | Cláudio T. Bornstein | |
|
Neste trabalho é analisado o problema de sequenciar n tarefas em m máquinas paralelas onde cada tarefa tem datas de chegada iguais, tempos de processamento iguais e datas de entrega diferentes. Admite-se interrupção no processamento das tarefas. Nosso objetivo é minimizar o número de tarefas atrasadas. O problema é modelado por um grafo onde um fluxo máximo pode ser obtido. Investiga-se a relação entre a solução do problema de fluxo máximo com a solução para o problema de minimização do número de tarefas atrasadas. Mostramos que existe pelo menos uma solução que satisfaz ambos os problemas. Para o problema de sequenciamento um algoritmo O(n2) é apresentado mostrando- se eficiente na obtenção de um fluxo máximo e na minimização do tempo ocioso de máquina.
Sequencing Problems on Parallel Machines
Claudio T. Bornstein
December/1998
Advisor: | Claudio T. Bornstein | |
Department: Systems Engineering and Computer Science |
We examine the scheduling problem with n jobs on m parallel machines. Each job has the same arrival time, the same processing time and different due dates. Preemption is permitted. The objective is the minimization of the number of tardy jobs. The problem may be modeled as a maximum flow problem. We try to find the relation between maximum flow solutions and the minimization of the number of tardy jobs. We show that there is at least a solution which solves both problems. An O(n2) algorithm is presented for the scheduling problem wich succeds in maximizing the flow and minimizing the idle time.