Uma nova modelagem para o problema de escalonamento de tarefas com restrições de recursos

Abstract

Este trabalho apresenta uma nova modelagem a ser utilizada no problema de escalonamento de tarefas com restrições de recursos (PETRR). Alguns modelos de PETRR adotam um sistema de recursos renováveis dentro de um horizonte de planejamento composto de um conjunto de períodos, isto é, no decorrer do problema, após a ativação de tarefas, estas passam a gerar receitas em quantidades fixas ou variáveis a cada período subseqüente. No modelo aqui proposto, a partir do momento em que se ativa uma tarefa até o último período considerado, uma quantidade de recursos denominada lucro (associada à tarefa ativada) é disponibilizada a cada período. Assim, a quantidade de recursos disponíveis, num dado período, vai depender de quais tarefas foram ativadas até então e de quando isto ocorreu. Esta modelagem reflete, de maneira mais real, grandes projetos de expansão de empresas, que podem ser feitos em etapas e que já admitem retornar algum lucro antes do término do projeto como um todo. Foram propostas algumas heurísticas para tratar este problema incluindo conceitos das meta-heurísticas GRASP e Algoritmos Evolutivos (AEs). O trabalho mostra como determinados parâmetros do problema podem ser calibrados bem como formas de combinar de modo eficiente heurísticas de construção e busca local numa estrutura GRASP e/ou AE