调度问题研究

《调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、题目：关于一般性调度问题的研究摘要：问题描述简单调度算法作者：冷磊首先，先描述一下什么是调度问题。在现实世界中，人们可能经常会遇到这样一个问题：同时面临很多项任务，这些任务之中有的任务必须要在某些其他任务完成之后才能完成，或者有的任务之间互不干扰，谁先谁后并无多大关系；并且现在也有一个小的团队，团队里的人都能独立完成这些任务中的各个小项冃。现在问题出来了，要怎样给这些人分配任务，并且怎样分配这些任务的先后顺序，才能使我们完成之间时的效率达到最高。这对这样的问题，我们将其抽象为一个数学模型，就是我们所说的一般性的调度问题，一般性调度问题是指这样的一类问题：给定有穷的任务集T=｛佥I刃wN+｝和m

2、台相同的机器，T上存在偏序关系Y,如果“Yf2,那么必须保证任务九完成之后才能去完成九Vr€?,/(/)表示完成任务t所需的时间，d(f)表示任务t的截止时间，/(f),d(f)wZ+,设开始时间为0，5:T—｛0丄2.•…｝表示对任务集T的一个调度方案,其中表示任务t的开始时间，设Q=max｛/⑴+/(/)1/丘门表示完成任务的最终口寸间，假设每一项任务都可以安排到任何一台机器上执行•找出可以用于执行的■这个》称为可行调度.一个可行调度必须满足一下3个条件：1.每项任务都要在截止吋间Z前完成2.同时工作的的不同机器台数不超过m3.任务安排必须满足任务集的偏序约束，即上文所说的某项任务必须在某

3、些项任务完成之后才能完成用数学公式将这三个条件表达出来就是：1・X訂,5(f)+/(/)》(")+/(“)<5(/2)举一个例子来说明这个问题：在这个图中，忽略了自反关系，因为在拓扑排序中自反关系并不会发挥作用，假设这个问题屮我们有两台机器，我们由此可以给出至少两种调度方案：其屮ti表示任务，数字表示完成此项任务所花费的时间，现在我们的任务是找到最优的调度组合，使在这两台机器上完成这个任务的效率最高,即时间最短:分析：将偏序关系拓展为拓扑排序，将自反关系剔除，进行分析可得下列方案：（表格

4、中空表示机器不运转）方案一：tlt2t4t6时长t3t58方案二:tlt3t5t6时长t2t47相对方案一来说，方案二效率更高，第二个方案为最优调度。当然，对于一般性调度问题，现在还没又有效地算法，不过,如果将机器个数简化为1个，调度问题就大大简化了，相当于只是求一个偏序关系的拓扑排序•针对这种状况,我们将这个有向图写成矩阵形式(说明:只要两个节点能找到一条路，那么此位置的元素就为匕否则为0),根据这个假设，上面图的矩阵就可以写出如下：tlt2t3t4t5t6ti001101a001111r3000001tA000001t5000001t6000000对于这个矩阵的求解，即利用这个矩阵求出一个

5、拓扑排序，算法如下:川=61.对i:1—>6,S/=工如7=12.将$(i:lT6)由小到大排序3.排在前面的先执行，依次输出下面进行算法实现，源代码如下：#includeintmain(){intij,s[6]={0},a[6][6],*p[6],*t;printf(H请输入矩阵:H);for(i=0;i<6;i++)for(j=0;j<6;j++)for(i=0;i<6;i++)for(j=0;j<6;j++)s[i]+=a[j][i];p[i]二&s[i];}for(i=0;i<6;i++)for(j=i;j<6;j++)if(*p[i]>*p[j]){t=p[i]

6、；p[i]=p[jl；P[j]=t；}printf(n一个可能的拓扑排序为：rT);for(i=0;i<6;i++)printf(H%dHzp[i]-s+l);printf(,,H);return0;}上机运行结果为:上机运行结果与实际相符合。后记：由于我们知识水平的限制，此文屮一定存在很多瑕疵，还望教员指正。