Paper Info
Title
Comparison of genetic representation schemes for scheduling soft real-time parallel applications
Abstract
This paper presents a hybrid technique that combines List Scheduling (LS) with Genetic Algorithms (GA) for constructing non-preemptive schedules for soft real-time parallel applications represented as directed acyclic graphs (DAGs). The execution time requirements of the applications' tasks are assumed to be stochastic and are represented as probability distribution functions. The performance in terms of schedule lengths for three different genetic representation schemes are evaluated and compared for a number of different DAGs.The approaches presented here produce shorter schedules than HLFET, a popular LS approach for all of the sample problems. Of the three genetic representation schemes investigated, PosCT, the technique that allows the GA to learn which tasks to delay in order to allow other tasks to complete produced the shortest schedules for a majority of the sample DAGs.
Year
DOI
Venue
2006
10.1145/1143997.1144093
GECCO
Keywords
Field
DocType
genetic algorithms,sample problem,acyclic graph,list scheduling,genetic representation scheme,hybrid technique,popular ls approach,sample dags,soft real-time parallel application,different dags,different genetic representation scheme,preemptive scheduling,genetic algorithm,genetics,performance,algorithms,directed acyclic graph,probability distribution function
Fixed-priority pre-emptive scheduling,Mathematical optimization,Fair-share scheduling,Computer science,Theoretical computer science,Schedule,Probability distribution,Rate-monotonic scheduling,Genetic representation,Dynamic priority scheduling,Genetic algorithm
Conference
ISBN
Citations 
PageRank 
1-59593-186-4
0
0.34
References 
Authors
13
2
Name
Order
Citations
PageRank
Yoginder S. Dandass114711.74
Amit C. Bugde200.34