浅议基于动态遗传算法的网格任务调度算法研究

《浅议基于动态遗传算法的网格任务调度算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、天津大学硕士学位论文基于动态遗传算法的网格任务调度算法研究姓名：薛桂香申请学位级别：硕士专业：计算机软件与理论指导教师：赵政20051201摘要将异构任务调度到异构资源上的问题，即任务分配问题，一般是NP问题。存在许多任务调度问题的具体实例的启发式算法，但多数情况下效率都不高。Holland提出的遗传算法应用进化策略实现了对调度空间的更快搜索，能够更快更好的找到优质的解。该算法在许多领域都得到了应用。许多研究者探索了遗传算法在同构和异构多处理机上对任务调度的应用，并取得了许多成绩。但是，他们都爹睛

2、况作了各种假设，降低了解决方案的通用性，如调度必须事先离线做出并且不能改变，所有的通信时间事先知道，所有的处理机具有相同的处理能力，处理机专门用来处理来自调度器分配来的任务等。这些假设限制了这些调度策略在分布式系统中的通用性。网格具有动态性和异构性，所以这些策略不适合网格中的应用。、本文提出了一种遗传算法的改进算法一动态遗传算法DGA(DynamicGeneticAlgorithm)，根据网格系统各服务节点的计算能力、负载及网络状态进行动态调度，从而向用户提供最优性能，不仅使总的完成时间最短，还尽

3、量考虑到使主机的空闲时间最短，同时要满足每个任务的deadline的要求。动态遗传算法主要是在基本遗传算法的基础上，针对网格任务调度的动态特性，提出了新的编码机制和适应度函数，能够很好的适应空闲主机数量和等待调度任务数量的动态变化。根据新的编码机制，重新设计了选择算子、交叉算子和变异算子。在OPNET环境中构建了一个局部网格的仿真模型，对所提出的动态遗传算法进行了仿真实现，并与常见的其他网格任务调度算法(如Min-min、Max-min、FCFS等)进行了对比，试验结果表明，动态遗传算法具有很好的

4、优化能力，提供了较好的服务质量。关键词：网格计算，遗传算法，0PNET，任务调度ABSTRACTneproblemofschedulingheterogeneoustasksontoheterogeneousresources．otherwiseknownasthetaskallocationproblem,isallNP—hardproblemforthegeneralcase．Manyheuristicalgorithmsexistforspecificinstancesofthetasksc

5、hedulingproblem．butareinefficientforamoregeneralcase．TheuseofHolland’sgeneticalgorithmsinscheduling，allowsgoodsolutionstobefoundquicklyandfortheschedulertobeappliedtomoregeneralproblem．ManyresearchershaveinvestigatedtheuseofGAstoscheduletasksinhomogen

6、eousandheterogeneousmulti—processorsystems、jvitllnotableSucCeSS．Unfortunately，assumptionsareoftenmadewhichreducethegeneralityofthesesolutions，suchthatschedulingcallbecalculatedoff-lineinadvanceandcannotchange，allcommunicatiOIIStimesareknowninadvance，a

7、llprocessorshaveequalcapabilitiesandarededicatedtoprocessingtasksfromthescheduler．Theseassumptionslimitthegeneralityoftheseschedulingstrategiesinreal-worlddistributedsystems．11lemaincharactersofgridaredynamicandheterogeneous．SOthesestrategiesarenotapp

8、ropriateforgridcomputing．Desirablegoalsforgridtaskschedulingalgorithmswouldshortenaveragedelays，maximizesystemutilizationandfulfilluserconstraints．InthispaperaschedulingstrategyispresentedwhichUSeSaDynamicGA(DGA)toscheduleheterogeneoustasksont