PROGRAMAÇÃO DE TAREFAS EM MÁQUINAS PARALELAS NÃO-RELACIONADAS COM TEMPOS DE PREPARAÇÃO, RESTRIÇÕES DE RECURSO E MINIMIZAÇÃO DO ATRASO TOTAL

Favorite this paper
How to cite this paper?
Details
  • Presentation type: Trabalho completo (oral)
  • Track: 13. MH – Metaheurísticas
  • Keywords: Programação de tarefas; Máquinas paralelas não-relacionadas; Heurísticas;
  • 1 Universidade Federal de Viçosa
  • 2 Universidade Federal de Viçosa/Departamento de Informática

PROGRAMAÇÃO DE TAREFAS EM MÁQUINAS PARALELAS NÃO-RELACIONADAS COM TEMPOS DE PREPARAÇÃO, RESTRIÇÕES DE RECURSO E MINIMIZAÇÃO DO ATRASO TOTAL

Júlio César dos Santos Neves Pinheiro

Universidade Federal de Viçosa

Abstract

Neste trabalho é abordado o problema da programação de tarefas em máquinas paralelas não-relacionadas sujeitas a tempos de preparação e restrições de recurso. Tarefas são classificadas em famílias e tempos de preparação são necessários entre o processamento de duas tarefas de famílias distintas. A execução de uma tarefa demanda uma quantidade de recurso da máquina responsável, que é suprida por processos superiores. O objetivo é encontrar uma programação de tarefas cujo atraso total seja mínimo. Uma formulação matemática de programação linear inteira-mista foi desenvolvida para o problema. Por se tratar de um problema NP-difícil, métodos exatos são ineficientes. Deste modo, desenvolve-se dois métodos resolutivos baseados nas meta-heurísticas Simulated Annealing e Iterated Greedy. Experimentos computacionais mostraram que os algoritmos apresentados resolvem satisfatoriamente o problema abordado.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!