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

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+1d(j) , 则a(i)在交换之后任然是早的. 任务a(j) 被已到了调度中的更前位置,故它在交换后任然是早的.如此, 寻找最优调度问题就成为找一个由最优调度中早的任务构成的集合A的问题. 一旦A被确定后, 就可按期限的单调递增顺序列出A中的所有元素,从而给出实际的调度, 然后按任意顺序列出迟的任务(S-A), 就可以产生出最优调度的一个规范次序.称一个

3、任务的集合A是独立的, 如果存在关于A中任务的一个调度, 使得没有一个任务是迟的. 显然, 某一调度中早任务的集合就构成一个独立的任务集.3. 实验数据:l 输入:没有输入, 有一个结构体task,系统会随机生成task的期限和惩罚l 输出:分别输出随机生成task的集合后的早任务集合,迟任务惩罚以及将每个替换为 后的早任务集合,迟任务惩罚.4. 实验截图:5. 结果分析:可以看出将每个替换为 后的早任务集合基本上包括了没有替换是的早任务集合, 并且替换后的迟任务惩罚大于没有替换时的迟任务惩罚. 6. 源代码:l 普通排序/*贪心算法实现单处理器任务调度。*基本思想是：首先按照惩罚把各个任务降

4、序排序。*然后遍历任务，逐一确定是否可以放入独立子集A*/#include #include #include using namespace std;#define n 8struct taskint id;/任务标记int d;/期限int w;/惩罚;void init(task ta)/初始化任务列表，随机确定任务的截止时间和惩罚srand(unsigned)time(NULL); /随机数发生器的初始化函数for (int i = 0; i n; i+)tai.id = i;tai.d = 1 + rand() % 20;tai.w = rand() % 50;void print(

5、task ta)cout id= ta.id td= ta.d tw= ta.w 0; i-)for (int j = 0; j i; j+)if (taj.w 0; i-)for (int j = 0; jtaj + 1.d)copy(s, taj);copy(taj, taj + 1);copy(taj + 1, s);int greedy(task a, task ta)/实现贪心算法int max = 0, k = 0, i, j;int count = 0;int Ntn + 1;/Nti记录a中截止时间在i之前的任务数sortW(ta);/按照权重排序copy(a0, ta0);m

6、ax = ta0.d;k = 1;for (i = 0; i = a0.d)Nti = 1;elseNti = 0;for (i = 1; in; i+)for (j = tai.d; j j)/这种情况下，说明tai不能放入a中。break;if (j = n + 1)/tai可以放入独立子集中copy(ak, tai);k+;for (j = tai.d; j = n; j+)/把tai放入a后，要更新Nt数组。Ntj+;return k;int getW(task a, task ta, int k)/计算延时任务的惩罚int i = 0;int sum1 = 0, sum2 = 0;f

7、or (i = 0; i k; i+)sum1 += ai.w;for (i = 0; i n; i+)sum2 += tai.w;return sum2 - sum1;int main()task taskern;/初始任务集合task An;/早任务集合int i = 0, maxweg = 0, k = 0;init(tasker);maxweg = tasker0.w;for (i = 0; i n; i+)/找到最大惩罚值if (maxweg taskeri.w)maxweg = taskeri.w;k = greedy(A, tasker);sortD(A, k);/将调度方案按照截止时间进行排序，便于查看算法是否正确执行cout 最优调度方案的早任务为： endl;for (i = 0; i k; i+)print(Ai);cout 迟任务惩罚为： getW(A, tasker, k) endl;/改变惩罚值重新确定最优调度。for (i = 0; i n; i+)taskeri.w = maxweg - taskeri.w;k = greedy(A, tasker);sort