TASK SCHEDULING ALGORITHM FOR HETEROGENEOUS MULTI PROCESSING COMPUTING SYSTEMS

摘要

The main purpose of task scheduling is to assign tasks onto available processors with the aim of producing minimum schedule length and without violating the precedence constraints. In heterogeneous multi-processing systems, task assignments and scheduling have a great impact on the system operation. In a heuristic based task scheduling algorithm, different process will result different task execution time (makespan) on a heterogeneous computing system. Thus, a good scheduling algorithm should be capable to efficiently assign precedence to each subtask depending on the resources required to reduce makespan. In this report, we propose a genetic algorithm (PGA) to resolve a task assignment and scheduling for homogeneous and heterogeneous multi-processing problem. The basic idea of this process is to exploit the advantages of heuristic-based algorithms to decrease space search and the time needed to get the best solution. The achieved results show that the suggested approach significantly outperforms the other approaches in terms of task execution time.