Computer Science ›› 2015, Vol. 42 ›› Issue (1): 86-89.doi: 10.11896/j.issn.1002-137X.2015.01.020

Previous Articles     Next Articles

Multiprocessor Task Scheduling Method Based on Cuckoo Search Algorithm

YANG Hui-hua, ZHANG Xiao-feng, XIE Pu-mo and WEI Xiang-yuan   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Multiprocessor system plays a key role in high performance computing.In order to improve the parallelism of the system,we proposed a new multiprocessor task scheduling algorithm,which is based on Cuckoo search(CS) algorithm.The algorithm takes the latest completion time of all tasks as the goal,and encodes based on task priority method to make continuous CS algorithm suitable for discrete task scheduling problem probably.The experimental results show that CS algorithm not only can obtain shortest task completion time,but also has the fastest solving speed.Its computation time is 60% lower than the widely used genetic algorithm and particle swarm optimization algorithm.

Key words: Multiprocessor,Task scheduling,Cuckoo search algorithm

[1] Kwok Y K,Ahmad I.Static scheduling algorithms for allocating directed task graphs to multiprocessors[J].ACM Computing Surveys (CSUR),1999,31(4):406-471
[2] Daoud M I,Kharma N.A high performance algorithm for static task scheduling in heterogeneous distributed computing systems[J].Journal of Parallel and Distributed Computing,2008,68(4):399-409
[3] 陈华平,黄刘生.启发式任务调度中的处理器选择策略[J].软件学报,1999,10(11):1194-1198
[4] 石威,郑纬民.相关任务图的均衡动态关键路径调度算法[J].计算机学报,2001,24(9):991-997
[5] Corrêa R C,Ferreira A,Rebreyend P.Scheduling multiprocessor tasks with genetic algorithms[J].IEEE Transactions on Parallel and Distributed Systems,1999,10(8):825-837
[6] Gupta S,Agarwal G,Kumar V.An Efficient and Robust Genetic Algorithm for Multiprocessor Task Scheduling[J].International Journal of Computer Theory and Engineering,2013,5(2);377-382
[7] 叶春晓,陆杰.基于改进遗传算法的网格任务调度研究[J].计算机科学,2010,7(7):233-235
[8] Omara F A,Arafa M M.Genetic algorithms for task scheduling problem[J].Journal of Parallel and Distributed Computing,2010,70(1):13-22
[9] Hwang R,Gen M,Katayama H.A comparison of multiprocessortask scheduling algorithms with communication costs[J].Computers & Operations Research,2008,35(3):976-993
[10] 王成昌,陈闳中,方钰,等.基于混合粒子群算法的网格任务调度[J].计算机科学,2012,9(2):18-21
[11] Al Badawi A,Shatnawi A.Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization[J].Computers & Operations Research,2013,40(10):2322-2328
[12] Yin P Y,Yu S S,Wang P P,et al.A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems[J].Computer Standards & Interfaces,2006,28(4):441-450
[13] Sivanandam S N,Visalakshi P,Bhuvaneswari A.Multiprocessor Scheduling Using Hybrid Particle Swarm Optimization with Dynamically Varying Inertia[J].IJCSA,2007,4(3):95-106
[14] 高尚,杨静宇.多处理机调度问题的粒子群优化算法[J].计算机工程与应用,2005,41(27):72-73
[15] Yang X S,Deb S.Engineering optimisation by cuckoo search[J].International Journal of Mathematical Modeling and Numerical Optimisation,2010,1(4):330-343
[16] Gandomi A H,Yang X S,Alavi A H.Cuckoo search algorithm:a metaheuristic approach to solve structural optimization problems[J].Engineering with computers,2013,29(1):17-35
[17] Ouaarab A,Ahiod B,Yang X S.Discrete cuckoo search algorithm for the travelling salesman problem[J].Neural Computing and Applications,2014,24(7/8):1659-1669
[18] 邱卫东,陈燕,李洁萍,等.一种实时异构嵌入式系统的任务调度算法[J].软件学报,2004,15(4):504-511
[19] Yang X S,Deb S.Cuckoo search via Lévy flights[C]∥World Congress on Nature & Biologically Inspired Computing,2009(NaBIC 2009).IEEE,2009:210-214
[20] Standard Task Graph Set.http://www.kasahara.elec.waseda.ac.jp/schedule/index.html

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .