Hybrid Genetic Algorithm for Bi-Criteria Multiprocessor Task Scheduling with Communication Delay

Present work considers the minimization of the bi-criteria function including weighted sum of makespan and total completion time for a Multiprocessor task scheduling problem.Genetic algorithm is the most appealing choice for the different NP hard problems including multiprocessor task scheduling. Performance of genetic algorithm depends on the quality of initial solution as good initial solution provides the better results. Different list scheduling heuristics based hybrid genetic algorithms (HGAs) have been proposed and developedfor the problem. Computational analysis with the help of defined performance index has been conducted on the standard task scheduling problems for evaluating the performance of the proposed HGAs. The analysis shows that the ETF-GA is quite efficient and best among the other heuristic based hybrid genetic algorithms in terms of solution quality especially for large and complex problems