Heuristics Based Genetic Algorithm for Scheduling Static Tasks in Homogeneous Parallel System

International Journal of Computer Science and Security

Gurvinder Singh¹  Kamaljit Kaur¹  Amit Chhabra¹ 

[1] $$

关键词: DAG;    multiprocessor scheduling;    genetic algorithm;    heuristics;   

DOI  :  

来源: Computer Science and Security

【 摘 要 】

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.

【 授权许可】

Unknown