文章基本信息

标题：Heuristics Based Genetic Algorithm for Scheduling Static Tasks in Homogeneous Parallel System
本地全文：下载
作者：Mr. Kamaljit Kaur ; Mr. Amit Chhabra ; Mr. Gurvinder Singh 等
期刊名称：International Journal of Computer Science and Security (IJCSS)
电子版ISSN：1985-1553
出版年度：2010
卷号：4
期号：2
页码：183-198
出版社：Computer Science Journals
摘要：In the multiprocessor scheduling problem, a given program, represented by a directed acyclic graph (DAG), is to be scheduled in such a way that the program's execution time should be minimized. This problem is being very hard to solve exactly. The scheduling problem is still known to be NP-complete in general, even when the target processors are fully connected and no communication delay is considered among task. Many heuristic methods for finding a suboptimal schedule exist. Performance of genetic algorithm can be improved with the introduction of some knowledge about the scheduling problem represented by the use of heuristics. In this paper the problem of same execution time or completion time and same precedence in the homogeneous parallel system is resolved by using concept of Bottom-level (b-level) or Top-level (t-level). This combined approach named as heuristics based genetic algorithm (HGA) based on MET (Minimum execution time)Min-Min heuristics and b-level or t-level precedence resolution and is compared with a pure genetic algorithm, min-min heuristic, MET heuristic and First Come First Serve (FCFS) approach. Results of the experiments show that the heuristics based genetic algorithm produces much better results in terms of quality of solutions.
关键词：DAG; multiprocessor scheduling; genetic algorithm; heuristics