调度问题研究.docx

题目：关于一般性调度问题的研究摘要：问题描述 简单调度算法作者: 冷磊首先，先描述一下什么是调度问题。在现实世界中，人们可能经常会遇到这样一个问题：同时面临很多项任务，这些任务之中有的任务必须要在某些其他任务完成之后才能完成，或者有的任务之间互不干扰，谁先谁后并无多大关系；并且现在也有一个小的团队，团队里的人都能独立完成这些任务中的各个小项目。现在问题出来了，要怎样给这些人分配任务，并且怎样分配这些任务的先后顺序，才能使我们完成之间时的效率达到最高。这对这样的问题，我们将其抽象为一个数学模型，就是我们所说的一般性的调度问题，一般性调度问题是指这样的一类问题:给定有穷的任务集和m台相同的机器，T上存在偏序关系，如果，那么必须保证任务完成之后才能去完成. 表示完成任务所需的时间，表示任务的截止时间，设开始时间为，表示对任务集的一个调度方案，其中表示任务的开始时间，设表示完成任务的最终时间，假设每一项任务都可以安排到任何一台机器上执行找出可以用于执行的，这个称为可行调度一个可行调度必须满足一下个条件：1. 每项任务都要在截止时间之前完成2. 同时工作的的不同机器台数不超过3. 任务安排必须满足任务集的偏序约束，即上文所说的某项任务必须在某些项任务完成之后才能完成用数学公式将这三个条件表达出来就是：1. ；2. ；3.举一个例子来说明这个问题：在这个图中，忽略了自反关系，因为在拓扑排序中自反关系并不会发挥作用，假设这个问题中我们有两台机器，我们由此可以给出至少两种调度方案：其中ti表示任务，数字表示完成此项任务所花费的时间，现在我们的任务是找到最优的调度组合，使在这两台机器上完成这个任务的效率最高，即时间最短：分析：将偏序关系拓展为拓扑排序，将自反关系剔除，进行分析可得下列方案：（表格中空表示机器不运转）方案一:t1t2t4t6时长8 t3t5方案二:t1t3t5t6时长7t2t4相对方案一来说，方案二效率更高，第二个方案为最优调度。当然，对于一般性调度问题，现在还没又有效地算法，不过，如果将机器个数简化为1个，调度问题就大大简化了，相当于只是求一个偏序关系的拓扑排序.针对这种状况,我们将这个有向图写成矩阵形式(说明:只要两个节点能找到一条路,那么此位置的元素就为1,否则为0),根据这个假设,上面图的矩阵就可以写出如下:对于这个矩阵的求解,即利用这个矩阵求出一个拓扑排序,算法如下:下面进行算法实现，源代码如下：#includeint main() int i,j,s6=0,a66,*p6,*t; printf(请输入矩阵：n); for(i=0;i6;i+) for(j=0;j6;j+) scanf(%d,&aij); for(i=0;i6;i+) for(j=0;j6;j+) si+=aji; pi=&si; for(i=0;i6;i+) for(j=i;j*pj) t=pi; pi=pj; pj=t; printf(nn一个可能的拓扑排序为: n); for(i=0;i6;i+) printf(%d ,pi-s+1); printf(nn