Novas Relaxações Lineares para o Problema de Scheduling de Processos em Multiprocessadores com Restrição de Atraso
Autores
|
4350 |
Pedro Paulo Rodrigues Teixeira Filho
|
44,1947
|
|
4351 |
44,1947
|
Informações:
Publicações do PESC
Descrevemos e avaliamos uma nova formulação matemática para o problema de escalonamento de tarefas em um sistema de multiprocessadores homogêneos com atrasos de comunicação. As formulações existentes envolvem um grande número de variáveis binárias com três índices. A formulação aqui discutida usa variáveis binárias com no máximo dois índices. Um conjunto de inequações válidas para a formulação é apresentada. Resultados numéricos de instâncias de tamanho pequeno e médio são apresentados.
We describe and evaluate a new mixed-integer mathematical programming formulation for the multiprocessor Schecluling Problem. Existing formulations involve a large number of binary variables with three indices. The formulation discussed here only uses binary variables with at most two indices. A set of valid inequalities is described. Numerical results of small and medium-scale problems are presented.