Escalonador de jobs

Disponível somente no TrabalhosFeitos
  • Páginas : 8 (1798 palavras )
  • Download(s) : 0
  • Publicado : 21 de julho de 2012
Ler documento completo
Amostra do texto
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¸˜otem 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 objetivode 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 asinforma¸˜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´merode jobs j´ escalonados, tempo de u u a processamento dos jobs j´ escalonados, multa m´ a ımina poss´ e multa m´xima. ıvel a Al´m da defini¸˜o do registro, o m´dulo fornece as fu¸˜es necess´rias a mae ca o co a nipula¸˜o dos dados nele armazenados. As fun¸˜es de maior importancia ser˜o ca co a discutidas nas se¸˜es seguintes. co 2.2.1 reg geraDescendente

reg geraDescendente Recebe o endere¸o deum registro e gera um descenc dente, escalonando o primeiro job ainda n˜o escalonado. Retorna o endere¸o a c do descendente gerado, caso n˜o seja gerado um descendente, retorna NULL. a Esta fun¸˜o ´ chamada dentro de um loop para que todos os descententes sejam ca e gerados. Prot´tipo o TRegistro* reg geraDescendente(TRegistro* reg); reg: ´ um ponteiro para um registro. e

2.2.2

regtransformaEmFolha

reg transformaEmFolha Recebe o endere¸o de um registro e o transforma c em folha, ou seja, marca seus jobs como completamente escalonados. Retorna o endere¸o do registro transformado em folha. c Prot´tipo o TRegistro* reg transformaEmFolha(TRegistro* reg); reg: ´ um ponteiro para um registro. e

2.2.3

reg imprime

reg imprime Recebe o endere¸o de um registro e imprime o seucusto, juntac mente com a lista de jobs armazenada nele.. Prot´tipo o

2

void reg imprime(TRegistro* reg) reg: ´ um ponteiro para um registro. e

2.3

heap

Neste m´dulo, ´ implementado um heap de registros que ´ indexado pelo UB o e e (multa m´xima) do conjunto de jobs. De forma que o registro da primeira a posi¸˜o do heap ´ o que tem o menor UB. Al´m da defini¸˜o do heap o m´dulo ca e e cao fornece as fu¸˜es necess´rias a manipula¸˜o dos dados nele armazenados. co a ca

2.4

branch bound

Neste m´dulo ´ implementado o algoritimo branch bound, que se trata de um o e m´todo de enumera¸˜o no qual se obt´m uma solu¸˜o ´tima sem ter que testar e ca e ca o todas as solu¸˜es poss´ co ıveis. Os m´todo ´ composto de duas opera¸˜es b´sicas: e e co a • Branching: Divide-se o problema...
tracking img