双机流水作业调度问题

2024-07-03 01:28| 来源: 网络整理| 查看: 265

概述

流水作业是并行处理技术领域的一项关键技术，它是以专业化为基础,将不同处理对象的同一施工工序交给专业处理部件执行,各处理部件在统一计划安排下,依次在各个作业面上完成指定的操作。流水作业调度问题是一个非常重要的问题，其直接关系到计算机处理器的工作效率。然而由于牵扯到数据相关、资源相关、控制相关等许多问题，最优流水作业调度问题处理起来非常复杂。已经证明，当机器数(或称工序数)大于等于3时，流水作业调度问题是一个NP-hard问题（e.g分布式任务调度）。粗糙地说，即该问题至少在目前基本上没有可能找到多项式时间的算法。只有当机器数为2时，该问题可有多项式时间的算法（机器数为1时该问题是平凡的）。

我们先给出流水作业调度的定义：

设有

n个作业，每一个作业

i均被分解为

m项任务:

Ti1,Ti2,…,Tim\mathrm{T}_{\mathrm{i} 1}, \mathrm{T}_{\mathrm{i} 2}, \ldots, \mathrm{T}_{\mathrm{im}}

Ti1?,Ti2?,…,Tim?(

1≤i≤n1 \leq i \leq n

1≤i≤n，故共有

m?nm * n

m?n个任务)，要把这些任务安排到m台机器上进行加工。如果任务的安排满足下列3个条件，则称该安排为流水作业调度：

每个作业 i 的第 j 项任务Tij (1?i?n,1?j?m)(1 \leqslant \mathrm{i} \leqslant \mathrm{n}, 1 \leqslant \mathrm{j} \leqslant \mathrm{m})

(1?i?n,1?j?m) 只能安排在机器

Pj\mathrm{P}_{\mathrm{j}}

Pj? 上进行加工

作业 i 的第 j 项任务 Tij(1≤i≤n,2≤j≤m)\mathrm{T}_{\mathrm{ij}}(1 \leq \mathrm{i} \leq \mathrm{n}, 2 \leq \mathrm{j} \leq \mathrm{m})

Tij?(1≤i≤n,2≤j≤m) 的开始加工时间均安排在第

j?1\mathrm{j}-1

j?1 项任务

Tij?1\mathrm{T}_{\mathrm{ij}-1}

Tij?1? 加工完毕之后，任何一个作业的任务必须依次完成，前一项任务完成之后才能开始着手下一项任务：

任何一台机器在任何一个时刻最多只能承担一项任务。

最优流水作业调度是指：

设任务

τij\tau_{i j}

τij?在机器

PjP_{j}

Pj?上进行加工需要的时间为

tijt_{i j}

tij?。如果所有的

tij(1?i?n,1?j?m)\mathrm{t}_{\mathrm{ij}}(1 \leqslant \mathrm{i} \leqslant \mathrm{n}, 1 \leqslant \mathrm{j} \leqslant \mathrm{m})

tij?(1?i?n,1?j?m)均已给出，要找出一种安排任务的方法，使得完成这

n个作业的加工时间为最少。这个安排称之为最优流水作业调度。

前面已经说过，当

m≥3\mathrm{m} \geq 3

m≥3时该问题是NP问题，这里我们只给出

m=2m = 2

m=2时时间复杂度在多项式以内的Johnson算法。

求解流水作业调度问题的Johnson算法具体描述如下：

1、设 a[i]和 b[i]

(0≤in)(0 \leq i

(0≤i 号，处理时间，设备号）组成的三元组表 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) 所示。 \begin{array}{l} \text { 设 } \mathrm{n}=4,\left(\mathrm{a}_{0}, \mathrm{a}_{1}, \mathrm{a}_{2}, \mathrm{a}_{3}\right)=(3,4,8,10) \text { 和 }\left(\mathrm{b}_{0}, \mathrm{b}_{1}, \mathrm{b}_{2}, \mathrm{b}_{3}\right)=(6,2,9,15) \text { 的作业 } 0 \text { 的三元组为 } \\ (0,3,0), \text { 作业 } 1 \text { 的三元组为 }(1,2,1) \text { 。 } \text { 如图 }(\mathrm{a}) \text { 所示。 } \end{array}

设 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) 所示。 ?

(a)三元组表

作业号处理时间设备号 0301212803100\begin{array}{|c|c|c|} \hline \text { 作业号 } & \text { 处理时间 } & \text { 设备号 } \\ \hline 0 & 3 & 0 \\ \hline 1 & 2 & 1 \\ \hline 2 & 8 & 0 \\ \hline 3 & 10 & 0 \\ \hline \end{array}

作业号 0123? 处理时间 32810? 设备号 0100??

2、对三元组表按处理时间排序，得到排序后的三元组表 d。如图(b)所示。

(b)按处理时间排序

作业号处理时间设备号 1210302803100\begin{array}{|c|c|c|} \hline \text { 作业号 } & \text { 处理时间 } & \text { 设备号 } \\ \hline 1 & 2 & 1 \\ \hline 0 & 3 & 0 \\ \hline 2 & 8 & 0 \\ \hline 3 & 10 & 0 \\ \hline \end{array}

作业号 1023? 处理时间 23810? 设备号 1000??

3、对三元组表的每一项

d[i](0≤in),\mathrm{d}[\mathrm{i}](0 \leq \mathrm{i}

d[i](0≤ic[j](0≤jn),c[j]\mathrm{c}[\mathrm{j}](0 \leq \mathrm{j}

c[j](0≤j

（c）最优作业排列（0，2，3，1）

（d)最优调度方案

p138104p269152\begin{array}{|l|l|l|l|l|} \hline \mathrm{p} 1 & 3 & 8 & 10 & 4 \\ \hline \mathrm{p} 2 & 6 & 9 & 15 & 2 \\ \hline \end{array}

p1p2?36?89?1015?42??

例题：

下面是北大PKU POJ 第2751题Saving Endeavour

有2台机器，n件任务，必须先在S1上做，再在S2上做。任务之间先做后做任意。求最早的完工时间。

双机调度问题Johnson算法简析: （1)把作业按工序加工时间分成两个子集，第一个集合中在S1上做的时间比在S2上少，其它的作业放到第二个集合。先完成第一个集合里面的作业，再完成第二个集合里的作业。

（2)对于第一个集合，其中的作业顺序是按在S1上的时间的不减排列；对于第二个集合，其中的作业顺序是按在S2上的时间的不增排列。

Johnson算法的时间取决于对作业集合的排序,因此,在最怀情况下算法的时间复杂度为

0( nlogn )0(\text { nlogn })

0( nlogn ),所需的空间复杂度为

0( n )0(\text { n })

0( n )。

c语言代码如下：

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include using namespace std; const int MAXN=10005; struct TNode { int s1,s2; }ws[MAXN]; int topf,tops; int n; bool operatory?x:y; } void Work() { sort(ws,ws+n); int i,t1=0,t2=0; for (i=0;i

【本文地址】

双机流水作业调度问题

双机流水作业调度问题

今日新闻

推荐新闻