Asian Science Citation Index is committed to provide an authoritative, trusted and significant information by the coverage of the most important and influential journals to meet the needs of the global scientific community.  
ASCI Database
308-Lasani Town,
Sargodha Road,
Faisalabad, Pakistan
Fax: +92-41-8815544
Contact Via Web
Suggest a Journal
International Journal of Soft Computing
Year: 2010  |  Volume: 5  |  Issue: 2  |  Page No.: 42 - 51

Modified Genetic Algorithm for Task Scheduling in Homogeneous Parallel System Using Heuristics

Kamaljit Kaur, Amit Chhabra and Gurvinder Singh    

Abstract: Multiprocessor task scheduling is an important and computationally difficult problem. Multiprocessors have emerged as a powerful computing means for running real-time applications especially due to limitation of uni-processor system for not having sufficient enough capability to execute all the tasks. Multiprocessor computing environment requires an efficient algorithm to determine when and on which processor a given task should execute. A task can be partitioned into a group of subtasks and represented as a DAG (Directed Acyclic Graph) that problem can be stated as finding a schedule for a DAG to be executed in a parallel multiprocessor system. The problem of mapping meta-tasks to a machine is shown to be NP-complete. The NP-complete problem can be solved only using heuristic approach. The execution time requirements of the applications tasks are assumed to be stochastic. In multiprocessor scheduling problem, a given program is to be scheduled in a given multiprocessor system such that the program’s execution time should be minimized. The last job must be completed as early as possible. Genetic Algorithm (GA) is one of the widely used techniques for constrained optimization. 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 study 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 Modified Genetic Algorithm (MGA) based on MET (Minimum execution time)/Min-Min heuristics and b-level or t-level precedence resolution is finally 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 modified genetic algorithm produces much better results in terms of quality of solutions.

Fulltext    |   Related Articles   |   Back
  Related Articles

Copyright   |   Desclaimer   |    Privacy Policy   |   Browsers   |   Accessibility