6.3 最佳调度问题.docx

《6.3 最佳调度问题.docx》由会员分享，可在线阅读，更多相关《6.3 最佳调度问题.docx（9页珍藏版）》请在优知文库上搜索。

1、最正确调度问题算法设计思想：（1）分支限界法求解假设有n个任务和k个机器,首先将何时转化为空脚k：树高为n,好一层对应一个任务：株个节点代表一个调段状态，记录了徒个机器完成任务的时间；每个节点有k个核子，代表下一个任务可以由k个机器来完成.这样.问Sfi所求的最正确两度方案就是找全部机器完成时间蜃大值的最小值叶子节点.分支眼界法的本质是对解空间树的BFS（广度优先）搜寻，即将下,个任务由那个机器完成的两度状态入认，而后再依次将出队的每一个状态的子状态入队.为了实现剪枝.我的须要定义一个处理时间上界up.其含义为：当前剌下的任务全部由完成时间琳早的机潺处理之后，全部机器完成任务的呆晚时间,这样，

2、在搜寻过程中不断缩小up,并推断当前状态的最晚完成时间,一旦大于up.说明该支路没彳f开展前景.进展剪枝.另外,为J使UP正确地指示上界.须要首先对任务根据完成时间降序排序，并且预处理得到剩下的后m项任务的完成时间，防止在搜寻过程中重视计算.采纳优先队列容器在进展BFS搜寻时，须要用队列来存储解空间椅的各个节点，即当前的调度状态，该以法采纳函数库供应的特别容器：优先队列容Prlorit1.qUeUe（包含在陈queue中），并且自己定义了优先队列容器所需的对比拟优先权booloperatorOconst为冏位状态中最大机器完成时间，使队列年次出队的元素为最大完成时间G小的调度方案，实现了优先队

3、列式的分支限界法。搜寻过程中动态申谙释放数组在BFS搜寻过程中，解空间树的好个状态节点所记录的各机器完成时间都采纳动态数组记录.这就要求我Q不能仅靠构造函数中那一次动态数组申请,而是须要对每个新的状态申请一个动态数组.同样,我们也不能只玳类对象的析构函数来择放一个动态数如，而须要在算法每次剪枝时择放悬空的动态数组。我们用全局变tNUMBER（初始为0）对动态数组的申请（+）和-放（一）进展了赛视,结果显示（NUMBER=O）全都申请的动态数组都得到了释放.（相应代码已酬去）算法的点是处理时间上界UP的定义，优先队列容器的运用，以及对动态数组的动态巾请和样放。除/上述三点之外,程序对律性低广增加

4、.对非法输入和文件槽误进展/检测.程序设计代码：/*头文件最正确调度问/Bh*/WifndefKNAPJ4ITdefineKNAP.Hinclude#includeincludeusingnamespacestd;classstate(public:state(intk);state();intx;i11ttlme;booloperator(conststate&y)const;state&operator=(conststate&y);private:intn;；classTask(public:Task(car*inzchar*out);Task。；voidSolve();protecte

5、d：voidSort();voidSchedule();voidPreProcess(intaast);intMinMaChIneant*time)；intFresh(int*old);intMax(int*time);voidPrint();private:包含优先队列容器记录调度状态构造函数,k是机器数析构函数任务序号记录各机涔力前时间定义优先队列所需的关系定义状态赋值运算符”任务数任务类构造函数析构函数输出结果到文件将工作时阀从大到小排序分校眼界法采纳优先认列求科预处理，后几个工作的时间和当前状态下处理最小时间机器更新状态中的时间返回最大时间输出结果（工务数和机落数完成任务的时间记录各机

6、器工作时间最小工作时间输出结果文件intn,k;intt;intatime;intmin;Ofstreamfout;Wendif/*函数实现文件正确调度问题cpp*/include崛正确调度问题,hstate:state(intk)time=newint(nl;for(inti1;i(conststate&y)const(intthis-ma=0;intv_max=0;for(inti1;i三n;i)(if(this-maxtimei)this_max=time(i;if(y-maxy_max)returntrue;elsereturnfalse;state&state:operator=(c

7、onststate&y)(=y.x;=y.;time=y.time;构造函数.k是机器数衣示从选。个任务开场须要记录n个机涔的当前时间初始状态各机器处理时间为0定义优先队列所需的关系找到该状态机器最大处理时间机器最大处理时间大于Y定义状态赋值运算符*return*this;Task:TaSk(Char*in,char*out)：fout(out)(ifstreamfin(in);iff!fin)CerrVV文件inv无法翻开!endl;exit(l);finnk;t=newintn+l);for(i11ti1;itl);fin.dose);time=newintfk+1);for(inti1;

8、ik;M+)timei=0;min=INT_MAX;if(Ifout)(cer文件out无法翻开I初始化任务数n和机据数k初始化各任务所衢处理时间初始化各机器处理时间最小时间开场初始化为朵夫值endl；ext(l);Task:TaSko(if(fout)fout.close();ift)delete。t;if(time)de!ete11time;voidTask：Solve()(SOn0;ScheduIeO;Print();)voidTask:Sort()(i11ttemp；for(inti=1;in;i+)(for(intj=i+1;j=n;)+)将工作时间从大到小排序分技限界法米纳优先队列

9、求解/输出函数temp=ti;Wl=tUbt(j)=temp;voidTaskiScheduIeOint,last;last=newintk;PreProcess(Iast);intup=lastO;存储剌下工作时间的畋组“素为之后剜余工作时闿和预处理处网时间上界，初始为总时间statetemp(k;例助状态，构造k个机器存储状态的优先队列容寿,根据当前状态机器最大完成时同升序排列priority-queuestatervectorrgreaterQueue;Queue.push(temp);intnum;intmin_machine;wile(l)(temp=Queue.top();if(t

10、emp.三三n)break;Queue.pop();num=temp.x；for(intil;i1&temp.timei=temp.timei-l)if(ik)须要择放数组time内存delete()temp.time;continue；同等剪枝if(Max(tem.time)up)(If。=k)须要拜放数组time内存deletedtemp.time；continue;眼界典技temp.tlmei+=tnum+l;min_machine=MinMaChinMtemP.time);temp.time(min-machine+=last(numl);if(Max(temp.time)max)mi

11、n=max;delete11temp.time;)voidTask：PreProCeSS(intast)(for(iti=O;i;i)(asti=O;for(intj=i+1;j=n;j+)ast(i三tOJ;)intTask:MinMaChine(inttime)加上下一个任务的时间更新限界记录任务序号状态进队最终一个不用友原/m脸证下一个方案找到最优方案预处理last数组intmin=INT-MAX;intmin-machine;for(inti=1;i=k;i+)if(time(i)min)(min=time(i);min_machine三i;returnmin_machine;int*

12、Task:Fresh(int*old)(int*temp;temp三newint(k*l);for(inti=1;i=k;i*)tempi=oMl;returntemp;intTask:Max(int*time)(intmax=0;for(intiB1;ik;i*)(if(matime(i)max=timei;)returnmax;VOidTask-PrintO(输出最小时间fourmnendl;*主函数文件test.cpp*/Winclude”最正确调度问四.hintmain()(输入文件输出文件文件初始化任务时间求解最正确调度方案charin三input.txt;char*out=output.txt;Tasktask(ln,out);task.Solve();return0;