资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
2023年最优流水作业调度问题:流水作业调度问题 最优流水作业调度问题 摘要 本文给出了双机流水作业调度的Johnson算法,并结合POJ上的一道题目详述了该算法的详细编程实现和应用。 关键词: 双机流水作业调度 Johnson算法 正文 流水作业是并行处理技术领域的一项关键技术,它是以专业化为基础,将不同处理对象的同一施工工序交给专业处理部件执行,各处理部件在统一安排支配下,依次在各个作业面上完成指定的操作。流水作业调度问题是一个特别重要的问题,其干脆关系到计算机处理器的工作效率。然而由于牵扯到数据相关、资源相关、限制相关等很多问题,最优流水作业调度问题处理起来特别困难。已经证明,当机器数(或称工序数)大于等于3时, 流水作业调度问题是一个NP-hard问题(e.g分布式任务调度)。粗糙地说,即该问题至少在目前基本上没有可能找到多项式时间的算法。只有当机器数为2时,该问题可有多项式时间的算法(机器数为1时该问题是平凡的)。 我们先给出流水作业调度的定义: 设有 n 个作业,每一个作业 i 均被分解为 m 项任务: Ti1,Ti2, ,Tim(1in,故共有nm个任务), 要把这些任务支配到m台机器上进行加工。 假如任务的支配满意下列3个条件, 则称该支配为流水作业调度: 1. 每个作业 i 的第 j 项任务Tij (1in,1jm) 只能支配在机器Pj上进行加工; 2. 作业 i 的第 j 项任务Tij(1in,2jm)的起先加工时间均支配在第j1项任务 Ti,j1加工完毕之后,任何一个作业的任务必需依次完成,前一项任务完成之后才能起先着手下一项任务; 3. 任何一台机器在任何一个时刻最多只能担当一项任务。 最优流水作业调度是指: 设任务Tij在机器Pj上进行加工须要的时间为tij。 假如全部的tij (1in,1jm)均已给出, 要找出一种支配任务的方法, 使得完成这 n 个作业的加工时间为最少。 这个支配称之为最优流水作业调度。 前面已经说过,当m3时该问题是NP问题,这里我们只给出m=2时时间困难度在多项式以内的Johnson算法。 求解流水作业调度问题的Johnson算法详细描述如下: 1) 设ai和b i (0i 号,处理时间,设备号)组成的三元组表d。其中,处理时间是指每个作业所包含的两个任务中时间较少的处理时间。 设n=4, a0,a1,a2,a3 =(3,4,8,10)和 b0,b1,b2,b3 =(6,2,9,15)的作业0的三元组为(0,3,0),作业1的三元组为(1,2,1)。 如图(a)所示。 2) 对三元组表按处理时间排序,得到排序后的三元组表d。如图(b)所示。 3) 对三元组表的每一项di(0i 是作业号。假如di设备号为1,则将作业 i 置于 c 的左端末尾,否则置于 c 的右端末尾。如图(c)所示,由两端向中间存放。 a) 三元组表 b) 按处理时间排序 c) 最优作业排列 (0,2,3,1) d) 最优调度方案 该算法是如此经典以至于ACM界已经有该算法的题目,下面是北大PKU POJ 第2751题Saving Endeavour(我校的BOJ上也有,不过是从POJ上照搬过来的): 有2台机器,n件任务,必需先在S1上做,再在S2上做。任务之间先做后做随意。求最早的完工时间。 双机调度问题Johnson算法简析: 1) 把作业按工序加工时间分成两个子集,第一个集合中在S1上做的时间比在S2上少,其 它的作业放到其次个集合。先完成第一个集合里面的作业,再完成其次个集合里的作业。 2) 对于第一个集合,其中的作业依次是按在S1上的时间的不减排列;对于其次个集合, 其中的作业依次是按在S2上的时间的不增排列。 Johnson算法的时间取决于对作业集合的排序,因此,在最怀状况下算法的时间困难度为O(nlogn),所需的空间困难度为O(n)。 c语言代码如下: #include #include #include using namespace std; const int MAXN=10005; struct TNode int s1,s2; wsMAXN; int topf,tops; int n; bool operator if (x.s1=y.s2) return true; if (x.s1=x.s2&&y.s1>=y.s2) return x.s2>y.s2; return false; int max(int x,int y) return x>y?x:y; void Work() sort(ws,ws+n); int i,t1=0,t2=0; for (i=0;i t1+=ws.s1; t2=max(t1,t2)+ws.s2; printf(%dn,t2); void Read() int i; while (scanf(%d,&n)&&n) for (i=0;i scanf(%d%d,&ws.s1,&ws.s2); Work(); int main() Read(); return 1;
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号