[pt] O problema de escalonamento de tarefas divisíveis consiste
em determinar
como uma carga a ser processada deve ser dividida entre
processadores
e em que ordem cada fração de carga será enviada a cada
processador.
Considera-se o escalonamento em redes estrela com
computadores e enlaces
heterogêneos. Nesta dissertação são propostas formulações
originais deste
problema como modelos de programação linear inteira mista,
assim como
um novo algoritmo de complexidade O(n) para a solução ótima
de um
caso especial. Além disso, também são propostas duas novas
heurísticas
para o problema, que permitem a elaboração de bons
escalonamentos para
instâncias de grande porte em um reduzido tempo de
processamento. / [en] The problem of divisible job scheduling consists of
determining how to
divide the data to be processed among processors and in
which order each
fraction should be sent to them. In this dissertation, we
consider the divisible
load scheduling problem in star networks with heterogeneous
computers
and links. Original mixed integer linear programming
formulations of this
problem are proposed, as well as a new algorithm with
complexity O(n)
to find the optimal solution for a special case. We also
propose two fast
heuristics that achieve good results for instances
representing large scale
computing systems.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:5242 |
| Date | 03 August 2004 |
| Creators | ELBIO RENATO TORRES ABIB |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0122 seconds