算法导论-实验三--一个任务调度问题

1、实验三一个任务调度问题1. 问题描述：在单处理器上具有期限和惩罚的单位时间任务调度问题2. 算法原理：考虑一个给定的调度.我们说一个任务在调度迟了，如果它在规定的时间之后完成；否则，这个任务在该调度中是早的.一个任意的调度总可以安排成早任务优先的形式，其中早的任务总是在迟的任务之前为了搞清这一点，请注意如果某个早任务a(i)跟在某个迟任务a(j)之后,就可以交换a(i)和a(j)的位置,并不影响a(i)是早的a(j)是迟的状态.类似的，任意一个调度可以安排成一个规范形式，其中早的任务先于迟的任务，且按期限单调递增顺序对早任务进行调度为了做到这一点，将调度安排成早任务优先形式然而，只要在该调度中

2、有两个分别完成于时间k和k+1的早任务a(i)和a(j)使得d(j)<d(i)，就交换a(i)和a(j)的位置.因为在交换前任务j是早的，k+1<=d(j).所以k+1<d(j)，则a(i)在交换之后任然是早的.任务a(j)被已到了调度中的更前位置，故它在交换后任然是早的.如此，寻找最优调度问题就成为找一个由最优调度中早的任务构成的集合A的问题.一旦A被确定后，就可按期限的单调递增顺序列出A中的所有元素，从而给出实际的调度，然后按任意顺序列出迟的任务(S-A)，就可以产生出最优调度的一个规范次序.称一个任务的集合A是独立的，如果存在关于A中任务的一个调度，使得没有一个任务是迟

3、的.显然，某一调度中早任务的集合就构成一个独立的任务集3. 实验数据：输入：没有输入，有一个结构体task，系统会随机生成task的期限和惩罚输出：分别输出随机生成task的集合后的早任务集合，迟任务惩罚以及将每个替换为口汽亠71'-；后的早任务集合，迟任务惩罚.4. 实验截图WF=0w=474=81=17后迟任务惩罚対:92:优调度方棄的早任务为：d-2dl=31-8最优謫度方案的早任务如*=2w=6=47v=33w-474V'miccssfcturned.8<0x0>executiont;inE-1.312sressctnykeytocontinuew=0EA3

4、5O云盘诵Wdy算法导论谀斷5A1龙2阴W_F訣屋蓟代码以及可执疔“1=3v/=415.结果分析：可以看出将每个亠替换为沁Id宀-后的早任务集合基本上包括了没有替换是的早任务集合，并且替换后的迟任务惩罚大于没有替换时的迟任务惩罚6.源代码：普通排序/*贪心算法实现单处理器任务调度。*基本思想是：首先按照惩罚把各个任务降序排序。*然后遍历任务，逐一确定是否可以放入独立子集A*/#include<iostream>#inelude<>#inelude<>usingnamespacestd;#definen8structtaskintid;d=i;tai.d=1+

5、rand()%20;tai.w=rand()%50;voidprint(taskta)cout<<"id="<<<<"td="<<<<"tw="<<<<endl;voidcopy(task&t,tasks)voidsortW(taskta)<taj+1.w)>taj+1.d)copy(s,taj);copy(taj,taj+1);copy(taj+1,s);intgreedy(taska,taskta);k=1;for(i=0;i&

6、lt;=n;i+)if(i>=a0.d)Nti=1;elseNti=0;for(i=1;i<n;i+)for(j=tai.d;j<=n;j+)if(Ntj+1>j);j<=n;j+);for(i=0;i<n;i+)sum2+=tai.w;returnsum2-sum1;intmain()tasktaskern;for(i=0;i<n;i+)maxweg=taskeri.w;k=greedy(A,tasker);sortD(A,k);=maxweg-taskeri.w;k=greedy(A,tasker);sortD(A,k);cout<<"改变后最优调度方案的早任务为："<<endl;for(i=0;i&