（计算机软件与理论专业论文）基于混合遗传算法的异构网格任务调度.pdf

删御关于论文使删勺说明 y 17 9 1 3 0 4 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 链旭日期：到q ，上：应 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名： 盟丝 导师签 i_f， f 山东大学硕士学位论文 目录 摘要i a b s t r a c t 第一章绪论1 1 1 研究背景及意义l 1 2 国内外研究现状2 1 3 本文主要工作3 1 4 本文的组织结构4 第二章网格与任务调度5 2 1 网格的概念及特点5 2 2 网格体系结构5 2 3 网格任务调度问题概述6 2 3 1 网格任务模型“7 2 3 2 网格任务调度的目标”9 2 4 本章小结9 第三章遗传算法理论l o 3 1 遗传算法介绍1 0 3 2 遗传算法的实现技术1 2 3 2 1 编码1 2 3 2 2 适应度函数1 3 3 2 3 遗传算子1 3 3 2 4 运行参数1 4 3 3 单亲遗传算法1 5 3 4 遗传算法的特点1 6 3 5 本章小结1 6 第四章两种基于d a g 的网格任务调度算法1 7 4 1 基于d a g 的网格任务调度模型1 7 4 1 1 任务模型l7 山东大学硕士学位论文 4 1 2 目标系统模型1 8 4 2 基于传统遗传算法b g a 的网格任务调度2 0 4 2 1 编码2 0 4 2 2 种群初始化2 0 4 2 3 适应度函数2 0 4 2 4 概率交叉算子2 1 4 2 5 选择和变异算子2 2 4 3 基于d l s 算法的网格任务调度_ 2 4 4 4 本章小结“2 6 第五章基于混合遗传算法的网格任务调度2 7 5 1 基于预处理的种群初始化改进2 7 5 1 1 预处理种群初始化的基本思想和算法描述2 7 5 1 2 预处理种群初始化的示例及分析3 0 5 2 改进后的混合交叉算子3 2 5 2 1 混合交叉算子的基本思想3 3 5 2 2 混合交叉算子的算法描述3 4 5 2 3 混合交叉算子示例及分析3 5 5 3 改进后的动态变异算子3 6 5 3 1 动态变异算子的基本思想3 6 5 3 2 动态变异算子的算法描述3 7 5 3 3 动态变异算子示例及分析3 9 5 4 p d l s 启发式算子4 1 5 4 1 p d l s 启发式算子的基本思想4 l 5 4 2 p d l s 启发式算子的算法描述4 2 5 4 3 p d l s 启发式算子示例及分析4 3 5 5 基于混合遗传算法的d a g 网格调度4 4 5 6 本章小结4 6 第六章实验分析”4 7 6 1 实验环境一4 7 巴 ， 山东大学硕士学位论文 6 1 1d a g 随机产生器4 7 6 1 2 目标系统随机产生器4 7 6 1 3 模拟实验环境4 8 6 2 算法改进部分实验分析5 0 6 2 1 种群初始化改进实验及分析5 0 6 2 2 交叉算子改进实验及分析5 2 6 2 3 变异算子改进实验及分析5 3 6 2 4p d l s 算子实验及分析5 4 6 3 算法综合性能实验分析”5 6 6 4 本章小结6 l 第七章总结和展望“6 2 7 1 总结”6 2 7 2 展望”6 3 参考文献6 4 致谢”6 8 攻读硕士期间发表的学术论文目录6 9 攻读硕士学位期间参与的项目7 0 山东大学硕士学位论文 t a b l eo f c o n t e n t s a b s t r a c t ( i nc h i n e s e ) i a b s t r a c t ( i ne n g l i s h ) m c h a p t e r li n t r o d u c t i o n 1 1 1 r e s e a r c hb a c k g r o u n da n ds i g n i f i c a n c e 1 1 2r e s e a r c hs t a t u sa th o m ea n da b r o a d ”2 1 3m a i nw o r ko fp a p e r 3 1 4s t r u c t u r eo f p a p e r 4 c h a p t e r 2g r i da n dt a s ks c h e d u l i n g 5 2 1c o n c e p ta n dc h a r a c t e r so fg r i d - 5 2 2s t r u c t u r e so f g r i d 一5 2 3g r i dt a s ks c h e d u l i n gi n t r o d u c t i o n 6 2 3 1g r i dt a s km o d e l 7 2 3 2g o a l so fg - r i dt a s ks c h e d u l i n g - 9 2 4s u m m a r y 9 c h a p t e r3t h e o r yo f g e n e t i ca l g o r i t h m 1 0 3 1i n t r o d u c t i o no fg e n e t i ca l g o r i t h m 。1 0 3 2i m p l e m e n to f g e n e t i ca l g o r i t h m 1 2 3 2 1c o d i n g 1 2 3 2 2f i t n e s sf u n c t i o n ”1 3 3 2 3g e n e t i co p e r a t o r s 1 3 3 2 4p a r a m e t e r s 1 4 3 3s i n g l ep a r e n tg e n e t i ca l g o r i t h m 15 3 4c h a r a c t e r so f g e n e t i ca l g o r i t h m 1 6 3 5s u m m a r y 1 6 c h a p t e r4t w oa l g o r i t h m so f g r i dt a s ks c h e d u l i n gb a s e do nd a g - 1 7 4 1g r i dt a s ks c h e d u l i n gm o d e lb a s e do nd a g 1 7 41 1t a s km o d e 卜一1 7 t ， 山东大学硕士学位论文 4 1 2t a r g e ts y s t e mm o d e l 18 4 2g r i dt a s ks c h e d u l i n gb a s e do ng e n e t i ca l g o r i t h m 2 0 4 2 1c o d i n g 2 0 4 2 2p o p u l a t i o ni n i t i a l i z a t i o n 2 0 4 2 3f i t n e s sf u n c t i o n 2 0 4 2 4c r o s s o v e ro p e r a t o r 2 1 4 2 5s e l e c t i o na n dm u t a t i o no p e r a t o r 2 2 4 3g r i dt a s ks c h e d u l i n gb a s e do nd l sa l g o r i t h m 2 4 4 4s u m m a r y 2 6 c h a p t e r5g r i dt a s ks c h e d u l i n gb a s e do nh y b r i dg e n e t i ca l g o r i t h m 2 7 5 1i m p r o v e m e n to f p r e p r o c e s s - b a s e dp o p u l a t i o ni n i t i a l i z a t i o n 2 7 5 1 1a l g o r i t h mo fp r e p r o c e s s - b a s e dp o p u l a t i o ni n i t i a l i z a t i o n 2 7 5 1 2c a s es t u d yo f p r e p r o c e s s - b a s e dp o p u l a t i o ni n i t i a l i z a t i o n 3 0 5 2i m p r o v e m e n to fh y b r i dc r o s s o v e ro p e r a t o r s 3 2 5 2 1b a s i ci d e ao fh y b r i dc r o s s o v e ro p e r a t o r 3 3 5 2 2a l g o r i t h md e s c r i p t i o no f h y b r i dc r o s s o v e ro p e r a t o r 3 4 5 2 3c a s es t u d ya n da n a l y s i so f h y b r i dc r o s s o v e ro p e r a t o r 3 5 5 3i m p r o v e m e n to f d y n a m i cm u t a t i o no p e r a t o r 3 6 5 3 1b a s i ci d e ao fd y n a m i cm u t a t i o no p e r a t o r 3 6 5 3 2a l g o r i t h md e s c r i p t i o no fd y n a m i cm u t a t i o no p e r a t o r 3 7 5 3 3c a s es t u d ya n da n a l y s i so f d y n a m i cm u t a t i o no p e r a t o r 3 9 5 4p d l sh e u r i s t i co p e r a t o r 4 l 5 4 1b a s i ci d e ao f p d l sh e u r i s t i co p e r a t o r “4 1 5 4 2a l g o r i t h md e s c r i p t i o no fp d l sh e u r i s t i co p e r a t o r 4 2 5 4 3c a s es t u d ya n da n a l y s i so f p d l sh e u r i s t i co p e r a t o r 4 3 5 5d a gg r i ds c h e d u l i n gb a s e do nh y b r i dg e n e t i ca l g o r i t h m 4 4 5 6s u m m a r y 4 6 c h a p t e r6e x p e r i m e n t sa n da n a l y s i s 4 7 6 1e x p e r i m e n t se n v i r o n m e n t 4 7 611d a gr a n d o mg e n e r a t o r 4 7 v 山东大学硕士学位论文 6 1 2t a r g e ts y s t e mr a n d o mg e n e r a t o r 4 7 6 1 3s i m u l a t i o no f e x p e r i m e n t se n v i r o n m e n t 4 8 6 2e x p e r i m e n t sa n a l y s i so ni m p r o v e m e n t so fa l g o r i t h m 。5 0 6 2 1 e x p e r i m e n t so fp r e p r o c e s s - b a s e dp o p u l a t i o ni n i t i a l i z a t i o n 5 0 6 2 2e x p e r i m e n t so fc r o s s o v e ro p e r a t o r 5 2 6 2 3e x p e r i m e n t so fm u t a t i o no p e r a t o r 5 3 6 2 4e x p e r i m e n t so fp d l so p e r a t o r - 5 4 6 3e x p e r i m e n t sa n a l y s i so fa l g o r i t h m p e r f o r m a n c e 5 6 6 4s u m m a r y 6 1 c h a p t e r7c o n c l u s i o na n d f u t u r ew o r k 6 2 7 1c o n c l u s i o n 6 2 7 2f u t u r ew o r k 6 3 r e f e r e n c e s 6 4 a c k n o w l e d g e m e n t s 6 8 p u b l i s h e da c a d e r n j cp a p e r s 6 9 p r o j e c t sp a r t i c i p a t e di n 7 0 v i 一 r 山东大学硕士学位论文 摘要 任务调度是网格研究领域的一个焦点问题，研究基于网格资源实际特征的任 务调度对于高性能网格的实际应用具有重要的意义，任务调度已被证明是n p 难 解问题，考虑网格资源实际特征的任务调度就使得问题变得更加复杂。国内外学 者提出了很多启发式算法并取得了良好的效果。但是，不少调度算法往往忽视了 任务间的数据关联与优先约束关系。而考虑任务优先关系的基于d a g 表示的任 务调度算法却往往忽略了网格节点的异构性和任务之间的通信关系，不能反映网 格环境和任务的实际特征。 本文是在异构网格环境下，运用遗传算法在解决组合优化方面的优越性，对 带通信的d a g 任务图调度进行研究。详细分析了传统遗传算法b g a 和基于表 调度技术的启发式调度算法d l s 的调度策略和算法特点，提出了一种新的改进 算法混合遗传算法，主要改进有： ( 1 ) 提出了基于预处理的种群初始化方法。针对传统遗传算法初始种群较 差，进化时间较长的不足，基于预处理的种群初始化方法充分考虑了任务的重要 程度和网格异构的特点，使得独立的任务尽量并行化，进而得到比较优秀的初始 种群，在进化代数相同的情况下，能够获得更好的解，减少进化时间。 ( 2 ) 提出了混合交叉算子。针对传统遗传算法的交叉算子在两父个体相同或 相似时，交叉效率降低的特点，改进的混合交叉算子考虑了两父个体的特征，当 两个体相同或相似时，就分别执行单亲遗传方式，可以产生新个体，提高交叉操 作的效率。 ( 3 ) 提出了动态变异算子。针对传统遗传算法的变异算子在进化后期容易产 生盲目性，难以快速全局收敛的特点，动态变异算子根据进化阶段来限制变异的 范围，后期进化时采用相邻基因变异，减少随意性，快速收敛到全局最优解。 ( 4 ) 提出了融合d l s 算法的p d l s 启发式算子。针对d l s 算法在异构网格 调度中能够取得较好解的特点，本文在传统遗传算子之后融合了部分改进的d l s 操作_ p d l s 算子，以一定的概率来修正选择的个体，对个体进一步优化。 本文对改进后的混合遗传算法进行了相应的实验模拟和结果分析，实验结果 表明，基于混合遗传算法的网格任务调度能够有效缩短网格任务调度时间，可实 山东大学硕士学位论文 通信的异构网格环境中。 ：网格；任务调度；异构：遗传算法：d l s 算法 一 山东大学硕士学位论文 a b s t r a c t t a s ks c h e d u l i n gi saf o c u si nt h er e s e a r c ha r e ao fg r i dc o m p u t i n g a n dt a s k s c h e d u l i n gb a s e do nt h ea c t u a l c h a r a c t e r i s t i c so fg r i dr e s o u r c e sh a si m p o r t a n t s i g n i f i c a n c ef o rt h ep r a c t i c a la p p l i c a t i o no fh i 曲一p e r f o r m a n c eg r i d t a s ks c h e d u l i n g w h i c hh a sb e e np r o v e dt ob ea l ln p h a r dp r o b l e mb e c o m e sm o r ec o m p l i c a t e dw h e n c o n s i d e rt h ea c t u a lc h a r a c t e r i s t i c so fg r i dr e s o u r c e s c u r r e n t l y , s c h o l a r sa th o m ea n d a b r o a dh a v ep r o p o s e dm a n yh e u r i s t i ca l g o r i t h m sa n do b t a i n e dg o o de f f e c t h o w e v e l m a n ys c h e d u l i n ga l g o r i t h m so f t e ni g n o r et h ed a t ac o n n e c t i o na n dp r e c e d e n tr e s t r i c t i o n a m o n gt a s k s w h i l es o m es c h e d u l i n ga l g o r i t h m sb a s e do nd a g t a s ks c h e d u l i n gh a v e c o n s i d e r e dt h ep r e c e d e n tr e s t r i c t i o n ，t h e yo f t e ni g n o r et h eh e t e r o g e n e i t ya m o n gt h e g r i dn o d e sa n dt h ec o m m u n i c a t i o nr e l a t i o n s h i pa m o n gt a s k s ，t h u sc a l ln o tr e f l e c tt h e r e a lc h a r a c t e r i s t i co f 鲥de n v i r o n m e n ta n dt a s k s t h i sp a p e rm a k e sar e s e a r c ho fd a gt a s kg r a p hs c h e d u l i n gw i mc o m m u n i c a t i o n i nt h eh e t e r o g e n e o u sg r i de n v i r o n m e n t , b yv i r t u eo ft h es u p e r i o r i t yo fg e n e t i c a l g o r i t h m si ns o l v i n gc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s w eg i v ed e t a i l e da n a l y s i s o ft h es c h e d u l i n gs t r a t e g i e sa n dc h a r a c t e r i s t i c so ft r a d i t i o n a lg e n e t i ca l g o r i t h mb g a a n dl i s ts c h e d u l i n gt e c h n o l o g yb a s e dh e u r i s t i cs c h e d u l i n ga l g o r i t h md l s ，a n d p r o p o s ea ni m p r o v e dm e t h o d h y b r i dg e n e t i ca l g o r i t h m t h em a i ni n n o v a t i o n sa r e ： i ap r e p r o c e s s - b a s e dp o p u l a t i o ni n i t i a l i z a t i o ni sp r o p o s e d a i m i n ga tp o o ri n i t i a l p o p u l a t i o na n dl a c ko fl o n ge v o l u t i o n a r yt i m eo ft r a d i t i o n a lg e n e t i ca l g o r i t h m ，o u r i n i t i a l i z a t i o nm e t h o db a s e do np r e t r e a t m e n to ft h ep o p u l a t i o nf u l l yc o n s i d e rt h e i m p o r t a n td e g r e eo ft a s k sa n dc h a r a c t e r i s t i c so fh e t e r o g e n e o u sg r i d ，m a k ei n d e p e n d e n t t a s k st op a r a l l e l i z ea sm u c ha sp o s s i b l e ，a n dt h e ng e tb e t t e ri n i t i a lp o p u l a t i o n i nt h e s i t u a t i o no ft h es a m ee v o l u t i o ng e n e r a t i o n ，o u rm e t h o dc a l lg e tab e t t e rs o l u t i o na n d r e d u c et h ee v o l u t i o nt i m e 2 h y b r i d c r o s s o v e ro p e r a t o ri s p r o p o s e d t o a d d r e s st h e p r e m a t u r i t y c o n v e r g e n c ep r o b l e ma n dl o we f f i c i e n c yo ft r a d i t i o n a lg e n e t i ca l g o r i t h mw h e nt w o p a r e n ti n d i v i d u a l sa r et h es a m ei nc r o s s o v e ro p e r a t o lo u rh y b r i dc r o s s o v e ro p e r a t o r i i i 山东大学硕士学位论文 t a k e st h ec h a r a c t e ro ft w o p a r e n ti n d i v i d u a l si n t oa c c o u n ta n ds i n g l ep a r e n to p e r a t i o n w i l lb ed o n ew h e nt h et w oi n d i v i d u a l sa r et h es a m eo rs i m i l a r , w h i c hc a l lg e n e r a t e n e wi n d i v i d u a l sa n d i m p r o v et h ee f f i c i e n c yo f c r o s s o v e ro p e r a t o r 3 d y n a m i cm u t a t i o no p e r a t o ri sp r o p o s e d m u t a t i o no p e r a t o ro ft r a d i t i o n a l g e n e t i ca l g o r i t h m sp r o n et ob l i n d n e s si nl a t e rs t a g eo fe v o l u t i o na n di sd i f f i c u l tt oa r a p i dg l o b a lc o n v e r g e n c e t oa d d r e s sa b o v es h o r t c o m i n g s ，o u rd y n a m i cm u t a t i o n o p e r a t o rl i m i tt h es c o p eo fm u t a t i o na c c o r d i n gt oe v o l u t i o n a r ys t a g e ，d oa d j a c e n tg e n e m u t a t i o ni nt h el a t e rs t a g eo fe v o l u t i o n ，r e d u c ea r b i t r a r i n e s s ，a n dg a i nar a p i d c o n v e r g e n c et ot h eg l o b a lo p t i m a ls o l u t i o n 4 ap d l sh e u r i s t i co p e r a t o rw h i c hc a l lc o m p r o m i s ed l sa l g o r i t h mi sp r o p o s e d c o n s i d e r i n gd l sa l g o r i t h mc a r l a c h i e v eb e t t e rs o l u t i o n si nh e t e r o g e n e o u sg r i d s c h e d u l i n g ，t h i sp a p e rc o m p r o m i s es o m ei m p r o v e m e n to ft h ed l so p e r a t i o n - p d l s o p e r a t o ra f t e rt h et r a d i t i o n a lg e n e t i co p e r a t o r s ，c o r r e c tt h es e l e c t e di n d i v i d u a lw i t ha c e r t a i np r o b a b i l i t y , a n df u r t h e ro p t i m i z et h ei n d i v i d u a l s t h i sp a p e rc o n d u c t sc o r r e s p o n d i n ge x p e r i m e n ts i m u l a t i o n sa n dr e s u l t sa n a l y s i s o nt h ei m p r o v e dh y b r i dg e n e t i ca l g o r i t h m t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tg r i d t a s ks c h e d u l i n gb a s e do nh y b r i dg e n e t i c a l g o r i t h mc 锄e f f e c t i v e l ys h o r t e nt h e s c h e d u l i n gt i m eo fg r i dt a s k s k e y w o r d s ：g r i d ；t a s ks c h e d u l i n g ；h e t e r o g e n e o u s ；g e n e t i ca l g o r i t h m ；d l s a l g o r i t h m i v 一 山东大学硕士学位论文 1 1 研究背景及意义 第一章绪论 随着互联网技术的迅猛发展和人们对高性能计算的需求，单台计算机已经不 能胜任一些大规模应用问题的解决。人们希望能够把地理上分布广泛的计算机通 过互联网组织起来，形成一台虚拟的超级计算机，实现资源共享和高性能计算。 于是，这种专门针对复杂计算的新型计算模式网格计算【l 】，就在这种应用需 求下应运而生。 网格即地理上分散异构的各种资源通过高速网络互联形成的一种新型计算 平台。网格中的资源不仅仅包括计算资源，还包括存储资源、数据资源、信息资 源、知识资源、专家资源、设备资源等。网格计算的出现，使得人们可以利用分 布在各地的闲散计算资源处理较为复杂的计算密集型的并行分布式应用程序。因 此，自从f o s t e r 等人引入网格计算的概念之后【2 l ，网格计算就广泛地应用于科学 计算、工程控制、生物信息化等领域。网格计算已经成为互联网研究的一个热点， 也是并行和分布式处理的一个发展方向。 在网格计算中，任务管理、任务调度和资源管理是网格的三个基本功能。用 户通过任务管理系统向网格提交任务。而任务调度系统则按照任务类型、所需资 源和可用资源等情况调度任务到适当的资源上运行并提供运行策略。资源管理系 统监视系统中资源和任务的运行状态等。然而，如何将应用程序的任务调度到可 用的资源上，是实现网格应用高性能的关键因素之一。网格计算环境中的任务调 度策略直接影响网格应用的性能。因此，任务调度系统是网格计算中重要的组成 部分，成为目前网格计算研究领域的一个焦点。任务调度系统要根据任务信息采 用适当的策略把不同的任务分配到相应的资源节点上去运行。但是由于网格中不 同的资源所有者拥有不同的访问策略、计算能力、通信能力和各种限制条件等1 3 】， 这就要求网格调度既要实现高效的任务调度，充分利用网格资源，又不能和网格 中的资源条件冲突。由于任务调度问题是n p 难解问题【3 】，再加上网格自身的自 治性、异构性、动态性和分布性等特点使得任务调度更加复杂【4 l 。在如此复杂的 条件下，如何进行最优的调度对传统的调度算法提出了新的挑战，成为目前研究 山东大学硕士学位论文 的热点，需要在理论和实践中不断完善。 随着互联网技术的发展，网格任务调度的应用领域越来越广泛，不仅应用于 科学计算、电力调度、工业控制等生产研究领域，而且还延伸到人们的生活领域。 网格任务调度在生活领域的应用主要有远程沉浸和信息集成等。远程沉浸是一种 特殊的网络化虚拟现实环境，人们可以在虚拟环境中随意漫游和沟通。而信息集 成则为用户提供“信息随手可得式”的服务。在信息化迅速蔓延的今天，网格任务 调度将扩展到人们生产生活的方方面面，对高效网格任务调度的深入研究就越来 越有重要的意义。 1 2 国内外研究现状 一般来说，网格任务调度问题在绝大多数情况下是n p 难解问题【4 】。国内外 ， 学者进行了深入的研究，提出了很多启发式算法，这些算法分为表调度算法、基 于复制的调度算法、基于任务聚类的调度算法、基于随机搜索技术的调度算法等。， ( 1 ) 表调度算法主要是通过对任务节点分配优先级别来构造一个调度列表， 然后重复从调度列表中顺序取出第一个节点，将节点分配到使它的开始执行时间 最早的处理器上，直到任务图中所有节点被调度完毕。表调度算法主要有 h l e f t 5 1 、d l s 6 1 、m c p l 7 1 和文献【8 】等。表调度算法比较实用，与其他调度算法 相比，其时间复杂度相对较低，调度结果较好。但是，任务节点优先级的确定是 一个关键问题，而在网格运行过程中，任务优先级又是动态改变的，所以能否确 定最优的顺序，影响着调度结果的好坏。 ( 2 ) 基于任务复制的调度算法 基于任务复制调度的基本思想是：在处理器上冗余地映射任务图中的任务， 以达到减少处理器之间通信开销的目的。目前，典型算法有d s i - i r q 、b t d h f 8 l 、 c p f d 9 1 等。这种考虑通信开销的任务调度更加符合现实中的网格环境。 ( 3 ) 基于任务聚类的调度算法 基于任务聚类调度的基本思想是：将给定任务图中的所有任务映射到数量不 受限制的集群上，如果两个任务分配到同一个聚类上，则表示它们在同一个处理 器上执行，这样就忽略了任务之间的通信代价。执行聚类的步骤之后，该类算法 还要对完成映射的聚类具体进行调度，即对聚类中的任务在每个处理器上进行时 2 山东大学硕士学位论文 间先后排序。典型算法如f c b s h t l 0 】，d s c 1 1 1 等。 ( 4 ) 基于随机搜索技术的调度算法 基于随机搜索技术的调度算法的基本思想是：通过有导向的随机选择来搜索 问题的解空间，而不是单纯的随机搜索。一般来说，随机搜索算法比其他启发式 算法的调度结果要好。而在此类算法中，大多数是针对独立任务的调度，不能反 映异构环境下任务的实际特征 1 2 - 1 3 】。也有一些考虑任务之间优先约束关系的调度 s - 1 3 ，但是却假设网格环境是同构的，不能反映异构环境下资源的实际特征。然 而既考虑任务约束关系又考虑异构环境调度的算法【1 0 ，1 4 】，大多