云计算环境下基于遗传蚁群算法的任务调度研究

C o m p u t e r E n g i n e e r i n g a n d A p p l i c a t i o n s计算机工程与应用

2 0 1 4, 5 0 ( 6 )

5 1

云计算环境下基于遗传蚁群算法的任务调度研究张雨，李芳，周 涛ZHAN G Yu,LI Fa ng, ZHOU Ta o

上海理工大学管理学院，上海 2 0 0 0 9 0Col l e g e o f Ma n a g e me n t, Un i v e r s i t y of S h a n g h a i f o r Sc i e n c e a n d Te c h n o l o g y, S ha n g h a i 2 0 0 0 9 0, Ch i n a

ZH AN G Yu, LI Fa n g,ZH O U Ta o . Ta s k s c he du l i ng a l g o r i t hm b a s e d o n g e ne t i c a n t c o l o n y a l g o r i t h m i n c l o u d c o m-

put i n g e nv i r o n me n t . Co m pu t e r Eng i n e e r i ng a nd Appl i c a t i o n s, 2 0 1 4 . 5 0 ( 6 ): 5 1 - 5 5 .

Ab s t r a c t:HO W t o s c he d u l e ma s s e s o f t a s k s e ic f i e n t l y i S a n i mpo r t a n t i s s u e t o be r e s o l v e d i n c l o ud c o mp u t i n g e n v i r o n—

me n t . An a l g o r i t h m c o mb i n i n g Ge n e t i c Al g o r i t h m( GA)a n d An t Co l o n y a l g o r i t h m( ACO)i s b r o u g h t u p or f t h e p r o g r a m—mi n g f r a me wo r k o f c l o u d c o mp u t i n g . I n t h e a l g o r i t h m, t h e GA a d o p t s t a s k— wo r k e r c o d i n g me t h o d, e v e r y c h r o mo s o me r e p - r e s e n t i n g a s p e c i ic f s c h e d u l i n g

s c h e me,a n d c h o os e s t h e a ve r a g e c o m pl e t i n g t i me o f a l l t a s ks a s i t s it f n e s s f u n c t i o n. Th e n t h e ACO a d o p t s Ge n e t i c Al g o r i t h m t o g i v e i n i t i a l i n f o r ma t i o n p he r o mo n e t o d i s t r i bu t e .Th i s c o mb i n a t i o n n o t o n l y o v e r c o me s t h e s l o w s p e e d o f ACO c a u s e d b y l a c k o f i n f o m a r t i o n p he r o mo n e o n t he p a t h e a r l y, b u t a l s o t a k e s f u l l u s e o f GA, t h a t i s f a s t— s pe e d, r a n d o ml y a n d g l o b a l s e a r c h. Th e r e i s a c o n t r a s t be t we e n GA a n d t he c o mb i n e d a l g o r i t h m t h r o u g h s i mu— l a t i o n e x pe r i me n t, a n d t h e r e s u l t s h o ws t h e p r o p os e d a l g o r i t h m i s e ic f i e n t i n t he c l o u d c o mp u t i n g e n vi r o n me n t .

Ke y wo r d s: c l o u d c o mp u t i n g; a n t c o l o n y a l g o r i t h m; Ge n e t i c Al g o r i t h m( GA): t a s k s c h e d u l i n g

摘要：对云计算中任务调度进行了研究，针对云计算的编程模型框架，提出一种融合遗传算法与蚁群算法的混合调度算法。在该求解方法中，遗传算法采用任务一资源的间接编码方式，每条染色体代表一种具体调度方案；选取任务平均完成时间作为适应度函数，再利用遗传算法生成的优化解，初始化蚁群信息素分布。既克服了蚁群算

法初期信息素缺乏，导致求解速度慢的问题，又充分利用遗传算法的快速随机全局搜索能力和蚁群算法能模拟资源负载情况的优势。通过仿真实验将该算法和遗传算法进行比较，实验结果表明，该算法是一种云计算环境下有效的任务调度算法。

关键词：云计算；蚁群算法；遗传算法；任务调度文献标志码： A 中图分类号： T P 3 0 1 . 6 d o i: 1 0 . 3 7 7 8/ j . i s s n . 1 0 0 2 . 8 3 3 1 . 1 2 0 6 . 0 0 3 9

1 引言云计算是一种新兴的商业计算模式，由网格计算脱胎而来，但更注重商业化，近年来受到各行各业的青睐。云计算在许多方面只是互联网的一个比喻词，亦即计算和数据资源日益迁移到 We b上的比喻词。云计算代表网络计算价值的一个新的临界点。它提供更高的效率、巨大的可扩展性和更快、更容易的软件开发。其中心内容为新的编程模型、新的I T基础设施以及实现

目前， I B M、 G o o g l e、 Ama z o n、 Mi c r o s o f t等巨头纷纷涉足云计算，提供了很多基于云计算的服务，比如Go o g l e Do c s、 Go o g l e Ea r t h、 Gma i l、 Go o g l e Ap p En g i n e、

Ama z o n E C2( E l a s t i c c o mp u t i n g c l o u d )和 S 3( S i mp l e

s t o r a g e s e r v i c e )、 Mi c r o s o f t的 Wi n d o ws L i v e We b及

Ho t ma i l等，未来还将有各种各样的云服务呈现。迄今为止，针对云计算的任务调度问题仍属于一个

比较前沿的课题。现有的一些理论还不是十分成熟完

新的商业模式。基金项目：上海市重点学科建设资助项目( No .￥ 3 0 5 0 4 )。

善，缺乏一个系统的科学方法。如果采用简单的分配调

作者简介：张雨 ( 1 9 8 7一),女，硕士研究生，主要研究方向为科技管理、云计算；李芳 ( 1 9 6 6一),女，博士研究生，副教授，主要研究方向为工业工程、生产运作管理；周涛 ( 1 9 8 9一),男，硕士研究生，主要研究方向为工业工程、供应链管理。E— ma i l: z h a n g y u 6 2 7 2 5

3 0 8 2@1 6 3 . c o m

收稿日期： 2 0 1 2 . 0 6 . 0 4 修回日期： 2 0 1 2 . 0 8 . 1 6 文章编号： 1 0 0 2 . 8 3 3 1 ( 2 0 l 4 ) 0 6— 0 0 5 l一 0 5C NK I网络优先出版： 2 0 1 2— 0 9— 2 5, h t t p:// w ww . c n k i . n e t/ k c ms/ d e t a i l/ 1 1 . 2 1 2 7 . T P . 2 0 1 2 0 9 2 5 . 1 0 0 1 . 0 4 7 . h t ml

本文来源：https://www.bwwdw.com/article/nsfq.html