Genetic Algorithm Parameters Optimization for Bi-Criteria Multiprocessor Task Scheduling Using Design of Experiments

Authors: Sunita Dhingra, Satinder Bal Gupta, Ranjit Biswas

Abstract:

Multiprocessor task scheduling is a NP-hard problem and Genetic Algorithm (GA) has been revealed as an excellent technique for finding an optimal solution. In the past, several methods have been considered for the solution of this problem based on GAs. But, all these methods consider single criteria and in the present work, minimization of the bi-criteria multiprocessor task scheduling problem has been considered which includes weighted sum of makespan & total completion time. Efficiency and effectiveness of genetic algorithm can be achieved by optimization of its different parameters such as crossover, mutation, crossover probability, selection function etc. The effects of GA parameters on minimization of bi-criteria fitness function and subsequent setting of parameters have been accomplished by central composite design (CCD) approach of response surface methodology (RSM) of Design of Experiments. The experiments have been performed with different levels of GA parameters and analysis of variance has been performed for significant parameters for minimisation of makespan and total completion time simultaneously.

Keywords: Multiprocessor task scheduling, Design of experiments, Genetic Algorithm, Makespan, Total completion time.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1093602

References:

[1] M.M. Rahman and M.F.I. Chowdhury, "Examining Branch and Bound Strategy on Multiprocessor Task Scheduling”, Proceedings of 12th International Conference on Computer and Information Technology, Dhaka, Bangladesh, 2009, pp. 162-167.
[2] Nafiseh Sedaghat, Hamid Tabatabaee–Y and M R. Akbarzadeh, "Comparison of MOGA with Greedy Algorithms in Soft Real-time Task Scheduling on Heterogeneous Processors with Communication Delay”, 3rd Joint Congress on Fuzzy and Intelligent systems , pp. 235 – 241.
[3] J. H. Holland, Adaptation in Natural and Artificial Systems. Cambridge, MA, USA: MIT Press, 1992.
[4] Andrew J. Page and Thomas J. Naughton, "Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing”, Proceedings of the 19th IEEE/ACM International parallel and distributed processing symposium, Denver USA, 2005, pp. 1530-2075.
[5] E.-S. Kim, C.-S. Sung, and I.-S. Lee, "Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints," The Journal of Computers & Operations Research, vol. 36, 2009, pp. 698 – 710.
[6] R. Hwang, M. Gen, and H. Katayam, "A comparison of multiprocessor task scheduling algorithms with communication costs," The Journal of Computers & Operations Research, vol. 35, 2008, pp. 976 – 993.
[7] E.S.H. Hou, N. Ansari and R. Hong, "A Genetic Algorithm for Multiprocessor Scheduling”, IEEE Transactions on Parallel and Distributed Systems. Vol. 5, No. 2, 1994, pp. 113 – 120.
[8] A.S. Wu, H. Yu, S. Jin, K.-C. Lin, and G. Schiavone, "An incremental genetic algorithm approach to multiprocessor scheduling”, IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 9, 2004, pp. 824–834
[9] O. Ceyda and M. Ercan, "A genetic algorithm for multilayer multiprocessor task scheduling”, In:TENCON 2004. IEEE region 10 conference, Vol. 2, 2004, pp. 68-170.
[10] R.C. Correa, A. Ferreira and P. Rebreyend, "Scheduling multiprocessor tasks with genetic algorithms”, IEEE Transactions on Parallel and Distributed Systems, Vol. 10, No. 8, 1999, pp. 825–837.
[11] M. R. Bonyadi and M. E. Moghaddam, "A bipartite genetic algorithm for multi-processor task scheduling”, International Journal of Parallel Programming, Vol. 37, No. 5, 2009, pp. 462- 487.
[12] C. K. Goh , E. J. Teoh ,K. C. Tan, "A hybrid evolutionary approach for heterogeneous multiprocessor scheduling”, Soft Computing, Vol. 13. 2009, pp. 833–846
[13] P. Chitra, P. Venkatesh and R. Rajaram,” Comparison of evolutionary computation algorithms for solving bi-objective task scheduling problem on heterogeneous distributed computing systems”, Sadhana, Vol. 36, Part 2, 2011, pp. 167–180
[14] M. R. Mohamed and M. H. A. Awadalla,” Hybrid Algorithm for Multiprocessor Task Scheduling”, IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 3, No. 2, 2011, pp. 79-89.