ESCALONAMENTO DE TAREFAS DIVISÍVEIS EM REDES ESTRELA
| Autor: | ELBIO RENATO TORRES ABIB |
|---|---|
| Přispěvatelé: | CELSO DA CRUZ CARNEIRO RIBEIRO, NOEMI DE LA ROCQUE RODRIGUEZ, MARIA CRISTINA SILVA BOERES, ALEXANDRE PLASTINO DE CARVALHO |
| Jazyk: | portugalština |
| Rok vydání: | 2004 |
| Zdroj: | Repositório Institucional da PUC-RIO (Projeto Maxwell) Pontifícia Universidade Católica do Rio de Janeiro (PUC-RIO) instacron:PUC_RIO |
| Popis: | CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO 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. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|