Escalonador de jobs

Estrutura de Dados II - Trabalho 3 - Escalonador de Jobs
M´rcio Oliveira da Rocha, Israel Henrique Silva de Lima a 2 de dezembro de 2010
Resumo No presente trabalho, ´ descrita a implementa¸˜o de um escalonador e ca de jobs, utilizando dois algoritimos para realizar o escalonamento. O Branch and Bound e Beam Search. Com o programa resultante, foram realizados testes e analizados os resultados, com o objetivo de comparar a forma como s˜o apresentados e o desempenho obtido em cada algoritmo. a

1

Introdu¸˜o ca

Segundo Feldmann & Biskup (2003), a crescente competividade no mercado global tem obrigado as empresas a oferecer uma grande variedade de servi¸os e c produtos a clientes cada vez mais exigentes no cumprimento dos prazos de entrega. Nesse sentido, a programa¸˜o da produ¸˜o tem sido alvo de esfor¸s das ca ca o empresas e dos pesquisadores no intuito de desenvolver modelos que minimizem atrasos. Existem alguns algoritmos que tem como objetivo resolver estes tipos de problemas, neste trabalho apresentaremos a implementa¸˜o de dois deles, o branch ca and bound e o beam search.

2

Implementa¸˜o ca

O programa foi desenvolvido de forma modularizada, com o objetivo de tornar mais simples e independente a implementa¸˜o de cada tarefa que o mesmo ca deve realizar. Os m´dulos desenvolvidos foram organizados de acordo com as o estruturas de dados utilizadas, sendo um m´dulo para cada estrutura. o Os m´dulos implementados, s˜o os seguintes: o a • jobs • registro • heap • beam search • branch bound

1

2.1

jobs

Este m´dulo ´ utilizado para guardar as informa¸˜es de um job. Ele cont´m o e co e uma estrutura de dados que armazena os dados de um job e possui as fun¸˜es co necess´rias para a manipula¸ao desses dados. a c˜

2.2

registro

Este m´dulo, ´ a implementa¸˜o de um registro onde ´ armazenado um conjunto o e ca e de jobs e as informa¸˜es relacionadas a ele. As informa¸˜es armazenadas s˜o co co a n´mero total de jobs do conjunto, n´mero