Please use this identifier to cite or link to this item:
Title: Heurísticas híbridas para escalonamento estático de tarefas em sistemas com processadores heterogêneos
Other Titles: Hybrid heuristics for static task scheduling in computing systems with heterogeneous processors
Keywords: Ciência da computação;  Algoritmo genético;  Processador de escalonamento de tarefa;  Escalonamento de tarefas;  Escalonamento estático de tarefas;  Otimização;  Processamento paralelo;  Metaheurística;  Algoritmo genético;  GRASP;  Static task scheduling;  Metaheuristics;  Genetic algorithm
Abstract: The utilization of existing resources in distributed computing systems with adequate allocation of parallel application's components is not an elementary is- sue. Such process constitutes the Task Scheduling Problem which is in general a NP-complete problem, and it has been explored in specialized literature. The com- plexity of this problem has motivated the development of heuristic methods to solve it, in which algorithms within the list scheduling class constitute commonly used me- chanisms. However, the greedy characteristic of such heuristics can, in many cases, contribute negatively on the achievmento of the best solution. This work investiga- tes the applicability of the integration of List Scheduling class heuristics with search mechanisms based on meta-heuristics. The goal is to combine meta-heuristics search power with low-complexity of List Scheduling heuristics for generating efficient sche- dules on distributed computing systems, in which resources are heterogeneous, in general. For this, two heuristics are proposed: HTSGA and HTSG, which are based on Genetic Algorithm and GRASP, respectively. The search mechanisms implemen- ted in such heuristics aims to eliminate the greedy behaviour of List Scheduling algorithm, providing new scheduling possibilities by determinating different task al- location sequences during the solution construction. Moreover, it was investigated the possibility of adapting proposed heuristics to different parallel application clas- ses. To validate this work, the solutions generated by the proposed heuristics were compared with traditional construction algorithms presented in the literature and to a meta-heuristic which was the basis of this work. The results showed that the proposed algorithms are robust both related to adaptability to characteristics of the submitted instances and to quick convergency to sub-optimal solutions.
Appears in Collections:TEDE com arquivos

Files in This Item:
File SizeFormat 
Eyder Rios-dissert.pdf1.46 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.