|
Vol: 55(69) No: 3 / September 2010 Nature Inspired Metaheuristics for Task Scheduling in Static and Dynamic Computing Environments Flavia Zamfirache Department of Computer Science, West University of Timisoara, Faculty of Mathematics and Informatics, Blvd. V. Parvan 4 Timisoara 300223, Romania, phone: (0)256-592155, e-mail: zflavia@info.uvt.ro Daniela Zaharie Department of Computer Science, West University of Timisoara, Faculty of Mathematics and Informatics, Blvd. V. Parvan 4 Timisoara 300223, Romania, e-mail: dzaharie@info.uvt.ro Ciprian Craciun Department of Computer Science, West University of Timisoara, Faculty of Mathematics and Informatics , Blvd. V. Parvan 4 Timisoara 300223, Romania, e-mail: ccraciun@info.uvt.ro Keywords: task scheduling, heterogeneous computing environments, evolutionary algorithms, ant colony optimization, dynamic optimization Abstract Finding optimal assignments of tasks to processing elements in heterogeneous computing environments is a challenging optimization problem which attracted a lot of researchers during the last decades. The aim of this paper is to analyze the behavior of two nature inspired approaches for task scheduling in static and in dynamic environments. An evolutionary and an ant based schedulers are proposed. For each one the selection of adequate operators is discussed and some memory based mechanisms are investigated in order to asses their ability to deal with the dynamic nature of the environment. The numerical analysis is based on a well-known benchmark for task scheduling in heterogeneous environments and the dynamic character of the environment is simulated randomly marking some resources as unavailable. Results obtained by three types of experiments are provided. The first experiment aims to assess the effectiveness of the schedulers in the case of static computing environments. The second experiment is focused on the comparison between the static and dynamic variants of the schedulers tested in the case of the simulated dynamic environment. The last experiment provides results of a robustness analysis. The numerical results illustrate that the nature inspired schedulers produce good and robust schedules especially in the case of heterogeneous computing environments characterized by inconsistency. In the case of dynamic environments the memory techniques introduced in the nature inspired schedulers proved to be beneficial as long as the ratio of processors which become unaivalable between successive scheduling events is around 10%. References [1] A. Abraham, H. Liu, C. Grosan, F. Xhafa, Nature Inspired Meta-heuristics for Grid Scheduling: Single and Multi-objective Optimization Approaches, F. Xhafa, A. Abraham (Eds.): Meta. for Sched. in Distri. Comp. Envi., SCI 146, pp. 247-272, 2008. [2] F. Xhafa, A. Abraham, Meta-heuristics for Grid Scheduling Problems, Metaheuristics for Scheduling: Distributed Computing Environments, Studies in Computational Intelligence, Springer Verlag, Germany, pp. 1-37, 2008. [3] A.M. Mehta, J. Smith, H.J. Siegel, A. Maciejewski, A. Jayaseelan, B. Ye, Dynamic Resource Allocation Heuristics for Maximizing Robustness with an Overall Makespan in an Uncertain Environment, Proceedings of PDPTA 2006, Las Vegas, Nevada, USA, June 26-29, 2006, vol. 1, 2006. [4] F. Zamfirache, D. Zaharie, C. Craciun, Evolutionary Task Scheduling in Static and Dynamic Environments, Proc. ICCC-CONTI, Timisoara, Romania, 2010, pp. 619 – 624. [5] T. D. Braun, H. J. Siegel, N. Beck, L. L. Boloni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, B. Yao, D. Hensgen, R. F. Freund, A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing, 61(6), pp. 810-837, 2001. [6] F. Xhafa, A. Abraham, Computational models and heuristic methods for Grid scheduling, Future Generation Computer Systems, 26, pp. 608-621, 2010. [7] J. Carretero, F. Xhafa, Using Genetic Algorithms for Scheduling Jobs in Large Scale Grid Applications. Journal of Technological and Economic Development - A Research Journal of Vilnius Gediminas Technical University, 12(1), pp. 11-17, 2006. [8] B. Sahoo, S. Mohapatra, and S.K. Jena, A Genetic Algorithm Based Dynamic Load Balancing Scheme for Heterogeneous Distributed Systems, Proceedings of PDPTA 2008, Las Vegas, Nevada, USA, July 14-17, 2008, CSREA Press, 2008. [9] G. V. Iordache, M. S. Boboila, F. Pop, C. Stratan, V. Cristea, A Decentralized Strategy for Genetic Scheduling in Heterogeneous Environments. OTM Conferences (2) , pp. 1234-1251, 2006. [10] R. Prodan, T. Fahringer, Dynamic scheduling of scientific workflow applications on the grid: a case study. Procs. of ACM SAC 2005, pp. 687-694, 2005. [11] S. Fidanova, M. Durchova, Ant Algorithm for Grid Scheduling Problem. In LNCS 3743, pp. 405-412, 2006. [12] G. Ritchie, J. Levine, A hybrid ant algorithm for scheduling independent jobs in heterogeneous computing environments. In Proceedings the 23rd Workshop of the UK Planning and Scheduling Special Interest Group, 2004. [13] K. Rzadca, F. Seredynski, Heterogeneous multiprocessor scheduling with differential evolution, Congress on Evolutionary Computation IEEE (2005) , pp. 2840-2847,2005. [14] P. Visalakshi, S. N. Sivanandam, Dynamic Task Scheduling with Load Balancing using Hybrid Particle Swarm Optimization, Int. J. Open Problems Compt. Math., 2(3), 2009. [15] F. Xhafa, B. Duran, A. Abraham, K. Dahal, Tuning Struggle Strategy in Genetic Algorithms for Scheduling in Computational Grids, Neural Network World, 18(3), pp. 209-225, 2008. [16] K. Kousalya, P. Balasubramanie, An enhanced ant algorithm for grid scheduling problem. In IJCSNS International Journal of Computer Science and Network Security, vol. 8, no. 4, 2008. [17] S. Lorpunmanee, M.N. Sap, A.H. Abdulah, C. Chompooinwai, An ant colony optimization for dynamic job scheduling in grid environment. In International Journal of Computer and Information Science and Engineering vol. 1, no. 4, pp. 207-214, 2007. [18] L.C. Canon, E.Jeannot, R. Sakkellariou and W.Zhang, Comparative evaluation of the robustness of DAG scheduling heuristics, Grid Computing, pp. 73-84, 2008. |