Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front Comput Sci    2013, Vol. 7 Issue (3) : 404-415    https://doi.org/10.1007/s11704-013-2130-6
RESEARCH ARTICLE
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
 Download: PDF(565 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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
 Cite this article:   
Qinma KANG,Hong HE. Task assignment for minimizing application completion time using honeybee mating optimization[J]. Front Comput Sci, 2013, 7(3): 404-415.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-013-2130-6
https://academic.hep.com.cn/fcs/EN/Y2013/V7/I3/404
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
[1] Gang WU, Zhiyong CHEN, Jia LIU, Donghong HAN, Baiyou QIAO. Task assignment for social-oriented crowdsourcing[J]. Front. Comput. Sci., 2021, 15(2): 152316-.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed