DocumentCode :
2586841
Title :
An Efficient Task Scheduling Technique in Heterogeneous Systems Using Self-Adaptive Selection-Based Genetic Algorithm
Author :
Deepa, R. ; Srinivasan, T. ; Miriam, D.D.H.
Author_Institution :
Dept. of Comput. Sci. & Eng., Sri Venkateswara Coll. of Eng., Sriperumbudur
fYear :
2006
fDate :
13-17 Sept. 2006
Firstpage :
343
Lastpage :
348
Abstract :
Optimal scheduling of parallel tasks with some precedence relationship, onto a parallel machine is known to be NP-complete. The complexity of the problem increases when task scheduling is to be done in a heterogeneous environment, where the processors in the network may not be identical and take different amounts of time to execute the same task. We propose a new genetics-based approach to scheduling parallel tasks on heterogeneous processors. Our approach requires minimal problem specific information and no problem specific operators or repair mechanisms. Key features of our system include a flexible, adaptive problem representation and an incremental fitness function. The selection scheme used in our scheduling algorithm is designed to maintain the genetic diversity within the population by advantageous self adaptive steering of selection pressure. This self-adaptive mechanism referred to as progeny selection in which the fitness of an offspring is compared to the fitness of its own parents. The sufficient amount of `successful´ offspring becomes the member of next generation. Comparison with traditional scheduling methods indicates that the new GA is competitive in terms of solution quality if it has sufficient resources to perform its search
Keywords :
computational complexity; genetic algorithms; parallel machines; processor scheduling; NP-complete problem; heterogeneous processors; heterogeneous systems; parallel machine; self-adaptive selection-based genetic algorithm; task scheduling technique; Algorithm design and analysis; Computer science; Educational institutions; Genetic algorithms; Genetic engineering; Heuristic algorithms; Optimal scheduling; Parallel machines; Processor scheduling; Scheduling algorithm; Genetic algorithm; heterogeneous systems; parallel systems; self-adaptive selection; task scheduling.;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Computing in Electrical Engineering, 2006. PAR ELEC 2006. International Symposium on
Conference_Location :
Bialystok
Print_ISBN :
0-7695-2554-7
Type :
conf
DOI :
10.1109/PARELEC.2006.14
Filename :
1698685
Link To Document :
بازگشت