Authors : 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.
Kamaljit Kaur, Amit Chhabra and Gurvinder Singh, 2010. Modified Genetic Algorithm for Task Scheduling in Homogeneous Parallel System Using Heuristics. International Journal of Soft Computing, 5: 42-51.