最优流水作业调度问题

《最优流水作业调度问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最优流水作业调度问题摘要本文给出了双机流水作业调度的Johnson算法，并结合POJ上的一道题目详述了该算法的具体编程实现和应用。关键词：双机流水作业调度Johnson算法正文流水作业是并行处理技术领域的一项关键技术，它是以专业化为基础,将不同处理对象的同一施工工序交给专业处理部件执行,各处理部件在统一计划安排下,依次在各个作业面上完成指定的操作。流水作业调度问题是一个非常重要的问题，其直接关系到计算机处理器的工作效率。然而由于牵扯到数据相关、资源相关、控制相关等许多问题，最优流水作业调度问题处理起来非常复杂。已经证明，当机器数(或称工序数)大于等于3时

2、，流水作业调度问题是一个NP-hard问题（e.g分布式任务调度）。粗糙地说，即该问题至少在目前基本上没有可能找到多项式时间的算法。只有当机器数为2时，该问题可有多项式时间的算法（机器数为1时该问题是平凡的）。我们先给出流水作业调度的定义：设有n个作业，每一个作业i均被分解为m项任务:Ti1,Ti2,…,Tim(1≤i≤n，故共有n×m个任务)，要把这些任务安排到m台机器上进行加工。如果任务的安排满足下列3个条件，则称该安排为流水作业调度：1.每个作业i的第j项任务Tij(1≤i≤n,1≤j≤m)只能安排在机器Pj上进行加工；2.作业i的第j项任务Tij

3、(1≤i≤n,2≤j≤m)的开始加工时间均安排在第j-1项任务Ti,j-1加工完毕之后，任何一个作业的任务必须依次完成，前一项任务完成之后才能开始着手下一项任务；3.任何一台机器在任何一个时刻最多只能承担一项任务。最优流水作业调度是指：设任务Tij在机器Pj上进行加工需要的时间为tij。如果所有的tij(1≤i≤n,1≤j≤m)均已给出，要找出一种安排任务的方法，使得完成这n个作业的加工时间为最少。这个安排称之为最优流水作业调度。前面已经说过，当m≥3时该问题是NP问题，这里我们只给出m=2时时间复杂度在多项式以内的Johnson算法。求解流水作业调度问

4、题的Johnson算法具体描述如下：1)设a[i]和bi(0≤i

5、(0≤j

6、。任务之间先做后做任意。求最早的完工时间。双机调度问题Johnson算法简析:1)把作业按工序加工时间分成两个子集，第一个集合中在S1上做的时间比在S2上少，其它的作业放到第二个集合。先完成第一个集合里面的作业，再完成第二个集合里的作业。2)对于第一个集合，其中的作业顺序是按在S1上的时间的不减排列；对于第二个集合，其中的作业顺序是按在S2上的时间的不增排列。Johnson算法的时间取决于对作业集合的排序,因此,在最怀情况下算法的时间复杂度为O(nlogn),所需的空间复杂度为O(n)。c语言代码如下：#include#include<

7、memory.h>#includeusingnamespacestd;constintMAXN=10005;structTNode{ints1,s2;}ws[MAXN];inttopf,tops;intn;booloperator<(TNodex,TNodey){if(x.s1=y.s2)returntrue;if(x.s1=x.s2&&y.s1>=y.s2)returnx.s2>y.s2;returnfalse;}intmax

8、(intx,inty){returnx>y?x:y;}voidWork(){so