Name
Abstract | ||
|---|---|---|
In real-time multiprocessor systems, admission control must respond to the requests of tasks quickly, otherwise some requests have to be rejected even if there are enough resources to meet the requirements of tasks running. Real-time task scheduling in multiprocessor systems has been proved to be NP-hard problems. Genetic algorithms (GAs) are known as a class of effective tools to solve NP problems, but the execution time of GAs is usually very long. In this paper, we present a novel approach of using genetic algorithms in real-time task admission control and scheduling. First our approach preserves the population of the GA and tries to use the historical information, i. e., the previous task schedules, to shorten the search time, instead of destroying and creating a population respectively after and before dealing with a new task in the standard GA procedure; second our approach dynamically updates the chromosomes in the population in terms of task arrivals and departures in order to repeatedly reuse the preserved population. Through simulations, it is demonstrated that our approach can rapidly make admission decisions and produce task schedules, meanwhile with satisfying task acceptance ratio and low preemption frequency. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/PDCAT.2009.10 | PDCAT |
Keywords | Field | DocType |
real-time multiprocessor systems,novel genetic admission control,novel approach,satisfying task acceptance ratio,task schedule,previous task schedule,new task,real-time task scheduling,genetic algorithm,task arrival,real-time task admission control,approach dynamically,satisfiability,algorithm design and analysis,computational complexity,distributed computing,scheduling,np hard problem,real time systems,genetics,control systems,probabilistic logic,genetic algorithms,data mining,multiprocessor,real time | Population,Preemption,Admission control,Scheduling (computing),Computer science,Multiprocessing,Real-time computing,Schedule,Genetic algorithm,Distributed computing,NP | Conference |
Citations | PageRank | References |
1 | 0.36 | 12 |
Authors | ||
1 | ||