Algoritmos Branch e Bound para o problema de sequenciamento em uma única m´máquina

Autores

  • Carlos E. Ferreira
  • Wellington D. Previero

DOI:

https://doi.org/10.5540/03.2015.003.01.0431

Palavras-chave:

Sequenciamento em uma única máquina, escalonamento de tarefa

Resumo

Neste trabalho apresentamos o problema de minimização do makespan para o sequenciamento de tarefas em uma única máquina. Para este problema, cada tarefa está associada a um tempo de execução, um instante de disponibilidade de entrada no sistema e o tempo em que a tarefa fica no sistema após o seu processamento. Para a resolução do problema foram utiliza- dos dois algoritmos baseados no método Branch e Bound e os resultados foram comparados. O primeiro algoritmo utiliza as estratégias de Carlier [2] e o segundo as de Grabowski, Nowicki e Zdrzalka [5]. O limitante inferior para o Branch e Bound ´e obtido através do Algoritmo Pre-emptivo de Jackson.

Downloads

Não há dados estatísticos.

Downloads

Publicado

2015-08-25

Edição

Seção

Otimização