|
|
|
Task assignment for minimizing application completion time using honeybee mating optimization |
Qinma KANG1,2( ), Hong HE1 |
| 1. School of Information Engineering, Shandong University,Weihai 264209, China; 2. State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China |
|
|
|
|
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
|
|
Corresponding Author(s):
KANG Qinma,Email:qmkang@sdu.edu.cn
|
|
Issue Date: 01 June 2013
|
|
| 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
doi: 10.1016/j.cie.2008.11.001
|
| 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
doi: 10.1109/71.932715
|
| 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
doi: 10.1016/j.csi.2005.03.005
|
| 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
doi: 10.1109/TC.1985.1676563
|
| 5 |
Kafil M, Ahmad I. Optimal task assignment in heterogeneous distributed computing systems. IEEE Concurrency , 1998, 6(3): 42-51
doi: 10.1109/4434.708255
|
| 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
doi: 10.1016/S0164-1212(98)10088-2
|
| 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
doi: 10.1016/j.jpdc.2004.08.002
|
| 8 |
Ahmad I, Dhodhi MK. Task assignment using problem-space genetic algorithm. Concurrency: Practice and Experience , 1995, 7(5): 411-428
doi: 10.1002/cpe.4330070506
|
| 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
doi: 10.1002/(SICI)1099-1425(199907/08)2:4<189::AID-JOS25>3.0.CO;2-I
|
| 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
doi: 10.1016/j.jpdc.2010.03.011
|
| 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
doi: 10.1016/S0377-2217(99)00251-9
|
| 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
doi: 10.1016/j.jpdc.2006.06.006
|
| 14 |
Salman A, Ahmad I, Al-Madani S. Particle swarm optimization for task assignment problem. Micromachines and Microsystems , 2002, 26(8): 363-371
doi: 10.1016/S0141-9331(02)00053-4
|
| 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
doi: 10.1016/j.jpdc.2011.05.005
|
| 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, T heoretical C omputer Science , 2008, 403(1): 11-32
doi: 10.1016/j.tcs.2008.02.011
|
| 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
doi: 10.1016/j.ins.2010.03.003
|
| 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
doi: 10.1142/S146902680300094X
|
| 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
doi: 10.1016/j.amc.2006.08.166
|
| 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
doi: 10.1016/j.ejor.2011.08.006
|
| 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
doi: 10.1016/j.amc.2007.02.029
|
| 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
doi: 10.1016/j.jfranklin.2006.06.001
|
| 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
doi: 10.1007/s11269-005-9001-3
|
| 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
doi: 10.1016/j.ins.2010.06.032
|
| 32 |
Chockalingam T, Arunkumar S. Genetic algorithm based heuristics for the mapping problem. Computer and Operations Research , 1995, 22(1): 55-64 .
doi: 10.1016/0305-0548(94)P2435-7
|
| 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
doi: 10.1109/IPDPS.2011.125
|
| 35 |
Hansen P, Mladenovic N. Variable neighborhood search: principles and applications. European Journal of Operational Research , 2001, 130(3): 449-467
doi: 10.1016/S0377-2217(00)00100-4
|
| 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
doi: 10.1006/jpdc.2000.1714
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
