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

Authors

  • Carlos E. Ferreira
  • Wellington D. Previero

DOI:

https://doi.org/10.5540/03.2015.003.01.0431

Keywords:

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

Abstract

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

Download data is not yet available.

Published

2015-08-25

Issue

Section

Otimização