最优流水作业调度问题

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

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

3、lt; i < n, 2 < j < m）的开始加工时间均安排在第j - 1项任务 Tij"加工完毕之后，任何一个作业的任务必须依次完成，前一项任务完成之后才能开 始着手下项任势；3. 任何一台机器在任何一个时刻最多只能承担一项任务。最优流水作业调度是指：设任务T”在机器耳上进行加工需要的时间为可。如果所有的5 （l<i<n,l<j<m）均 己给岀，要找出一种安排任务的方法，使得完成这n个作业的加工时间为最少。这个 安排称之为最优流水作业调度。前面己经说过，卅m > 3时该问题是NP问题，这里我们只给出m = 2时时间复杂度在多 项式以

4、内的Johnson算法。求解流水作业调度问题的Johnson算法具体描述如下：1）设减i和bi （0 < i <町分别为作业i在两台设备上的处理时间。建立由三元组（作业 号，处理时间，设备号）组成的三元组表d°其中，处理时间是指每个作业所包含的两 个任务中时间较少的处理时间。设n = 4. (a0,apa2,a3) = (3A8,10)>ftl(b0,bpb2lb3) = (6,2,9,15)的作业 0 的三元组为 (0,3,0),作业1的三元组为(1,2,1)。如图(打所示。2) 对三元组表按处理时间排序，得到排序后的三元组表d。如图(b)所示。3) 对1元组表的

5、每一项di(0 M i V n),从左右两端生成最优作业排列cj(0 < j < n), cj 是作业号。如果di设备号为1,则将作业i置于c的左端末尾，否则置于c的右端 末尾。如图(c)所示，由两端向中间存放。a)三元组表作业号处理时间设备号0301212803100b)按处理时间排序作业号处理时间设备号121002803100c)瑕优作业排列(02 3,1) d)最优调度方案pl38104P269152该算法是如此经典以至于ACM界己经有该算法的题目.卜面是北k PKU P0J第2751题 Saving Endeavour俄校的BOJ上也有，不过是从POJ上照搬过來的)：有2台

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

7、stdio. h>#include <memory. h>#includealgorithm using namespace std;const int MAXN=10005;struct TNodeint si, s2;wsMAXN;int topf, tops;int n;bool operator< (TNode x. TNode y)if (x. sl<x s2&&y sl>=y. s2) rrturn true;if (x. sl<x s2&&y sl<y s2) return x. sl<ysl; if (x. sl>=x s2&&y. sl>= y s2) ret urn x s2> y s2; return false;)int max(int x,int y)return x>y?x：y;void Work 0sort (ws. ws+n);int i, tl二0»t2二0;for (i=0;i<n;i+)11+=ws. si;t2 =max(tlt t2)+ws. s2;pr intf (/z%dnz t2);void ReadOint i;whi