Problemas de Sequenciamento em Máquinas Paralelas

Autores

1677
Luciane Ferreira Alcoforado
710,3
1678
Claudio Thomas Bornstein
(Orientador)
710,3

Informações:

Publicações do PESC

Título
Problemas de Sequenciamento em Máquinas Paralelas
Linha de pesquisa
Otimização
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
30/11/1998
Resumo
PESC: Resumo de Dissertação de Mestrado Resumo da Tese apresentada à COPPE/UFRJ como parte dos requisitos necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)

Problemas de Sequenciamento em Máquinas Paralelas

Luciane Ferreira Alcoforado

Novembro/1998
Orientador: Cláudio T. Bornstein  

 
Programa: Engenharia de Sistemas e Computação

      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.

Abstract
PESC: Master Degree Abstracts Abstract of Thesis presented at COPPE/UFRJ as a partial fulfillment of the requirements for the degree of Master of Science (M.Sc.)

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.

Arquivo
Topo