基于多机调度问题的动态规划算法

基于多机调度问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的动态规划算法 基于多机调度问题的动态规划算法 第l6卷第3期 2006年3月 计算机技术与发展 COMPU'I'ERTECHNOI.OGYANDDEVELOPMENT Vo1.16No3 Mar.2006 基于多机调度问题的动态规划算法 张凤梅,洪运国2 (1.辽宁师范大学计算机与信息技术学院,辽宁大连116029; 2.大连职业技术学院信息技术系,辽宁大连116035) 摘要:动态规划设计策略对许多具有最优解的实际应用问题的解决是灵活和有效的.文中首先针对在多机系统的操作 并给出了该类问题的动态规划算法,最后对系统的一类多机调度问题进行了 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 , 所给算法的复杂度进行了分析和讨论. 实验结果验证了所提出方法的有效性. 关键词:动态规划;最优解;多机调度问题;复杂度 中图分类号:TP301.6文献标识码:A文章编号:1005,3751(2006)03—0061—02 DynamicProgrammingAlgorithmforaKindof SchedulingProblemofMulticomputer ZHANGFeng.mei,HONGYun.guo2 (1.CollegeofComputerandInformationTechnology,LiaoningNormalUniversity,Dalian1 16029,China; 2.DepartmentofInformationandTechnology,DalianVocationalTechndogyCoHege,Dalia n116035,China) Abstract:Thedymmicpr.g】mmil1galgorithmisaflexibleandhigh—efficientmethodtomanyproblemswhichhavethebestmethod. Inthispaper.akindofschedulingproblemofmulticomputerisbroughtupfirstly.Andthenano velalgorithmforthisproblembasedOildy? mmicprogrammingispr(1p0sed.Finally,theecraplexityofthep】p0sedalgorithmisanalyzed.Simulationresultsshowitiseffective. Keywords:dynamicprogramming;thebestmethod;schedulingproblemofmulticomputer; complexity 0引言 动态规划设计策略最早由Belknan…1等人提出.Bel1 man认为利用最优性原理以及所获得的递推关系去求解 最优决策序列可以使问题的计算量急剧下降.动态规划 思想是将待求解问题分解成若干个子问题,先求解子问 题,然后从这些子问题的解得到原问题的解.动态规划算 法通常用于求解具有某种最优性质的问题.几年来,人们 在这一领域进行了积极的研究,给出了很多具有重叠子问 题特性的动态规划算法. 文中首先对在多机系统的操作系统中一类NP问 题u2J,即多机调度难解问题进行了分析和讨论,对该问题 的最优子结构性质进行了 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 ,在此基础上给出了该问题 的递归结构,同时实现了其动态规划算法,最后对所提出 的算法的复杂度进行了分析和讨论. 1问题的提出 在多机系统中设有两台处理机A和B来处理"个作 收稿日期:2oo5O6一O7 基金项目:国家自然科学基金资助项目(60372071);辽宁省自然科学 基金资助项目(2oo32125) 作者简介:张风梅(197O一).女,辽宁本溪人,硕士,讲师.研究领域为 操作系统,Linux,算法分析与设计. 业,设第f个作业交给机器A处理时需要时间a,若由机器 B来处理,则需要时间b.由于各作业的特点和机器的性能 关系,很可能对于某些i有a?b,而对于某些J,J?i有 aj<,既不能将一个作业分开由两台机器处理,也没有 一 台机器能同时处理2个作业. 问题[3J:设计一个算法,使得这两台机器A和B处理 完这个作业的时间最短(从任何一台机器开工到最后一 台机器停工的总时间). 2问题的动态规划算法 2.1问题的最优子结构性质 设全部作业的集合为N={1,2,…,},作业P?N 是机器A上第一个调度作业;作业q?N是在机器B上第 一 个调度作业,S={N—P,q{是N的作业子集,设7l"是 所给N个作业的最优调度,它所需的调度时间为丁(N, t),N个作业调度问题的最优值T(N,0)在一般情况下, 机器A开始加工N中某个作业P时,所需时间为t1;机器 B开始加工N中另一个作业q时,所需时间为2,对于其它 任意作业m?S,要等待t—min{t1,f2}之后,才可在机 器A或B上被调度. 设耳是所给N个作业的最优调度,它所需加工时间为 rain{tl,t2}+T',其中丁'是调度完P和q之后,作业集S ? 62?汁算机技术与发展第l6卷 所需的调度时间,S=={N(P,q)},则1,=T(S,query(b,schedul[m]);//4t!b中查找作业号 8ched~1I【n1]的b min{tl,t2}).[j]将其time置为1,表示相应的作业已在A上调度完成 证明:由T的定义可知, T'?T(S,min{tl,t2})(1) 若T'>T(S,min{tl,t2}),设'是作业集S在机器 A或B上的等待时间为min{tl,t2}情况下最优凋度,则 7c(P,口)+T(S,min{tl,t2})<不(P,口)+T',这与7c是N 的最优调度相矛盾,故 T'?T(Smin{t1,t2})(2) 由式(1)和式(2)可得T'=T(S,rain{tl,t2}),从而证明 了该作业调度具有最优子结构性质. 2.2问题的递归结构 由作业调度问题的最优子结构性质l4j可知,T(N,0) =min{min{a,b},T(N一{i},min{Tl,T2})}1?i? ?z 其中Tl和T2分别为前1个作业在机器A和B上分别 被调度所花时间.即: T(S,t)=min{min{a,b}+T(S一{i}),?mx{t— rain{Tl,}}},i?S 其中ITI&X{t—min{Tl,}}为调度完作业i之后,剩下作 业在机器上还需的时间. 按照上述递归式,可设计出流水作业在多机系统中的 作业调度问题的动态规划算法,但通过对递归式深入分 析,算法可进一步简化. 2.3算法的实现 设流水作业的个数为N,用含有两个成员的结构数组 n[N]和6[N]来存储N个作业在机器A和B上加工所需 的时间和作业号,结构数组定义:structAB{inttime;int JobNum;}a[N],6[N];用n_t变量存放最后所需的最 短时间,即最优值,用一个intschedul[N]来存储最后的最 优解即所需时间最短的作业调度次序. (1)数组的初始化和一些变量的定义. 设N为6,假设6个作业分别在机器A和B上执行所 需的时间分别为(al,a2,a3,a4,a5,a6)=(2,5,7,10,5, 2);(bl,b2,b3,b4,b5,b6)=(3,8,4,11,3,4);a[N]= {{2,1},{5,2},{7,3},{10,4},{5,5},{2,6}};b[N]= {{3,1},{8,2},{4,3},{11,4},{3,5},{4,6}};int1,z2, u,口,min—t,schedul[N]//nfin—t和schedul[N]分别是所 求最优值和最优解;t1,t2是在A和B上调度分别所需时 间;",是调度指针. (2)最优值和最优解的算法描述. ?对数组a和b分别按调度时问进行由小到大排序. ?求最优值和最优解,具体的算法如下: voidBestvalue—method(struetABa【],structABb[]) lintn;N,m=0,nfin—t,tl,t2, u,v,schedul[N]; if(a[u].time<b[v].time) {schedul[m]=a[u].JobNum;n一一;tl+=a[u].time; in++;u++;} else {schedut[m]=b[v].]obNum;n一一;t2+=b[v].time;query (a,schedul[m]);/佐a中查找作业号=schedul[m]的a[i]将其 time置为1,表示相应的作业已在A上凋度完成 m++;v++;} /经过一个判断进行第一次调度这样t1或也有了一个非零 的初值 while(n>O) lif(tl>t2) 1while(b[v].time==一1)v+; schedul[m]=b[v].JobNum~t2+=b[v].time;rl一; query(a,schedul[m]); m++:V++ } else {while(a[u].time==一1)u+; ~hedul[m]=a[u].JobNum,tl+=a[u].time~n一一; query(b,schedul[m]); m++;v十+;}} min—t=ma)【{tl,r2};} //re_in—t为A,B调度时间tl和t2最长的,min—t即为所求的最 优值,Schedul[N]即为N个作业在两台机器上在最优解 2.4算法的结果和复杂性分析 应用上述算法,对N为6,假设6个作业分别在机器A 和B上执行所需的时间分别为(口1,口2,口3,口4,5,a6)= (2,5,7,10,5,2);(61,62,63,64,65,b6)=(3,8,4,11,3, 4),进行调度结果min—t即所需的最短时间为18, schedul[N]即最优解为{1,5,6,3,2,4}. 算法BestValue—method的主要计算量取决于程序对 和每次循环体内查询query(a,schedul[m])或query(b, schedul[m])计算量,循环体内计算量为o(1),而两次循 环总次数为0(住)(住为流水作业的个数),算法所占用的 空间为0()[5l. 3结束语 综合以上分析,整个多机调度问题的动态规划算法的 时间复杂度为0(),所占空间复杂度为0(),这要比 用其它算法(比如用分冶法求解,其时间复杂度为指数 级),效率较高.同时本算法可以稍加改动,推广到具有7,r/ >2个机器的个流水作业的调度的问题上,同样有效.本 算法主要应用在多机系统中,当操作系统有多个作业需要 处理时,可以用此算法来预测调度次序,从而当有一个机 器出现空闲时,按此算法预测出的调度次序进行调度,可 以使这m个机器能在最短的时间内凋度完这7-/个作业,提 高计算机系统资源的利用率,加快用户的响应,从而使用 户获得最合理的响应时间,满足不同用户的 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 . (下转第65页)