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

Carlos E. Ferreira, Wellington D. Previero

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.


Palavras-chave


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

Texto completo:

PDF


DOI: https://doi.org/10.5540/03.2015.003.01.0431

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato