Task assignment for minimizing application completion time using honeybee mating optimization

Abstract

Effective task assignment is essential for achieving high performance in heterogeneous distributed computing systems. This paper proposes a new technique for minimizing the parallel application time cost of task assignment based on the honeybee mating optimization (HBMO) algorithm. The HBMO approach combines the power of simulated annealing, genetic algorithms, and an effective local search heuristic to find the best possible solution to the problem within an acceptable amount of computation time. The performance of the proposed HBMO algorithm is shown by comparing it with three existing task assignment techniques on a large number of randomly generated problem instances. Experimental results indicate that the proposed HBMO algorithm outperforms the competing algorithms.

Keywords

heterogeneous distributed computing / task assignment / task interaction graph / honeybee mating optimization / meta-heuristics

References

[1] Yang B, Hu H J, Guo S C. Cost-oriented task allocation and hardware redundancy policies in heterogeneous distributed computing systems considering software reliability. Computers & Industrial Engineering, 2009, 56(4): 1687-1696

[2] Wu M, Shu W, Gu J. Effcient local search for DAG scheduling. IEEE Transaction on Parallel and Distribute Systems, 2001, 12(6): 617-627

[3] Yin P Y, Yu S S, Wang P P, Wang Y T. A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems. Computer Standard & Interface, 2006, 28(4): 441-450

[4] Shen C, Tsai W. A graph matching approach to optimal task assignment in distributed computing systems using minimax criterion. IEEE Transaction on Computers, 1985, 34(3): 197-203

[5] Kafil M, Ahmad I. Optimal task assignment in heterogeneous distributed computing systems. IEEE Concurrency, 1998, 6(3): 42-51

[6] Tom A P, Murthy C S R. Optimal task allocation in distributed systems by graph matching and state space search. Journal of Systems and Software, 1999, 46(1): 59-75

[7] Ma Y C, Chen T F, Chung C P. Branch-and-bound task allocation with task clustering-based pruning. Journal of Parallel and Distributed Computing, 2004, 64(11): 1223-1240

[8] Ahmad I, Dhodhi MK. Task assignment using problem-space genetic algorithm. Concurrency: Practice and Experience, 1995, 7(5): 411-428

[9] Hadj-Alouane A B, Bean J C, Murty K G. A hybrid genetic/optimization algorithm for a task allocation problem. Journal of Scheduling, 1999, 2(4): 189-201

[10] Page A J, Keane T M, Naughton T J. Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system. Journal of Parallel and Distributed Computing, 2010, 70(7): 758-766

[11] Hamam Y, Hindi K S. Assignment of program modules to machines: a simulated annealing approach. European Journal of Operational Research, 2000, 122(2): 509-513

[12] Attiya G, Hamam Y. Optimal allocation of tasks onto networked heterogeneous computers using minimax criterion. In: Proceedings of the International Network Optimization Conference, 2003, 25-30

[13] Attiya G, Hamam Y. Task allocation for maximizing reliability of distributed systems: a simulated annealing approach. Journal of Parallel and Distributed Computing, 2006, 66(10): 1259-1266

[14] Salman A, Ahmad I, Al-Madani S. Particle swarm optimization for task assignment problem. Micromachines and Microsystems, 2002, 26(8): 363-371

[15] Alexandrescu A, Agavriloaei I, Craus M. A genetic algorithm for mapping tasks in heterogeneous computing systems. In: Proceedings of 15th International Conference on System Theory, Control, and Computing, 2011, 1-6

[16] Daoud M I, Kharma N. A hybrid heuristic-genetic algorithm for task scheduling in heterogeneous machine networks. Journal of Parallel and Distributed Computing, 2011, 71(11): 1518-1531

[17] Dasgupta D. Advances in artificial immune systems. IEEE Computational Intelligence Magazine, 2006, 1(4): 40-49

[18] Timmis J, Hone A, Stibor T, Clark E. Theoretical advances in artifi - cialim munesystems, Theoretical Computer Science, 2008, 403(1): 11-32

[19] Greensmith J, Whitbrook A, Aickelin U. Artificial immune systems. Handbook of Metaheuristics, 2010, 146: 421-448.

[20] Dorigo M, Birattari M, Stützle T. Ant colony optimization. IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39

[21] Picard D, Revel A, Cord M. An application of swarm intelligence to distributed image retrieval. Information Sciences, 2012, 192(1): 71-81

[22] Abbass H A. A single queen single worker honey-bees approach to 3-SAT. In: Proceedings of the Genetic and Evolutionary Computation Conference, 2001, 807-814.

[23] Abbass H A. A monogynous MBO approach to satisfiability. In: Proceedings of the International Conference on Computational Intelli- gence for Modeling, Control and Automation, 2001, 207-214

[24] Abbass H A. Marriage in honey bees optimization (MBO): a haplometrosis polygynous swarming approach. In: Proceedings of the Congress on Evolutionary Computation, 2001, 207-214

[25] Teo J, Abbass H A. A true annealing approach to the marriage in honey-bees optimization algorithm. International Journal of Computational Intelligence and Applications, 2003, 3(2): 199-211

[26] Koudil M, Benatchba K. Using artificial bees to solve partitioning and scheduling problems in codesign. Applied Mathematics and Computation, 2007, 186(2): 1710-1722

[27] Sabar N R, Ayob M, Kendall G, Qu R. A honey-bee mating optimization algorithm for educational timetabling problems. European Journal of Operational Research, 2012, 216(3): 533-543

[28] Fathian M, Amiri B, Maroosi A. Application of honey bee mating optimization algorithm on clustering. Applied Mathematics and Computation, 2007, 190(2): 1502-1513

[29] Afshar A, Haddad O B, Mariño M A, Adams B J. Honey-bee mating optimization (HBMO) algorithm for optimal reservoir operation. Journal of the Franklin Institute, 2007, 344(5): 452-462

[30] Haddad O B, Afshar A, Mariño M A. Honey-bees mating optimization (HBMO) algorithm: a new Heuristic approach for water resources optimization. Water Resources Management, 2006, 20(5): 661-680

[31] Marinaki M, Marinakis Y, Dounias G. Honey bees mating optimization algorithm for the Euclidean traveling salesman problem. Information Sciences, 2011, 181(20): 4684-4698

[32] Chockalingam T, Arunkumar S. Genetic algorithm based heuristics for the mapping problem. Computer and Operations Research, 1995, 22(1): 55-64.

[33] Kiran M, Hashim A H A. Execution time prediction of imperative paradigm tasks for grid scheduling optimization. International Journal of Computer Science and Network Security, 2009, 9(2): 155-163

[34] Al-Qawasmeh A M, Maciejewski A A. Characterizing task-machine affinity in heterogeneous computing environments. In: Proceedings of 2011 IEEE International Symposium on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011, 34-44

[35] Hansen P, Mladenovic N. Variable neighborhood search: principles and applications. European Journal of Operational Research, 2001, 130(3): 449-467

[36] Ali S, Siegel H J. Representing task and machine heterogeneities for heterogeneous computing systems. Tamkang Journal of Science and Engineering, 2000, 3(3): 195-207

[37] Braun T D, Siegel H J. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing system. Journal of Parallel and Distributed Computing, 2001, 61(6): 810-837

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg