| 失效链接处理 |
|
流水作业最优调度问题 PDF 下载
本站整理下载：
相关截图：
主要内容：
1. 问题描述：
个作业 要在两台机器 组成的流水线上完成加工。每个作业加工的
顺序都是先在 上加工，再在 上加工。 加工作业 所需的时间分别为
，流水作业调度要求确定这 个作业的最优加工次序，使得从第一个作
业在机器 上开始加工，到最后一个作业在机器 上加工完成所需时间最少。
【分析】
直观来看，一个最优调度应使机器 无空间时间，即 上加工的时间是所有 之和，
等待（空闲）的时间最少，不一定等于 之和。对 来说，一般有机器空闲和作业积压两
种情况。
设全部作业的集合为 。 是 的作业子集。机器 开始加工 中作
业时， 还在加工其他作业，等时间 t 之后才能利用。在此情况之下，
1) 完成 中所有的作业需要最短时间即为
2) 流水作业调度的最优值为
3)
：选一个作业 先加工，在 的加工时间。(注：此处的 不一定等于 1，而是任意选
取一个 ，使得 最小)
：剩余的作业要在等待 时间后才能在 上加工：因为一开始工作 是
随机取的， 加工完了 之后， 要开始加工 了，这里 是空闲的可以开始加工
剩下的 个作业了，但此时 开始加工 ，所以要等 时间之后才能重新利用。
4) 将 3)推广到一般情形下：
：在作业子集 中，当 加工完 后，要开始加工剩余的作业
，此时，对 来说有两种可能状态：正在加工积压的作业，需要时间 ，且 ，
i b i i b t a + − i
t a i b i b
+max{ ,0} i i b t a − N (1), (2),..., ( ) n
(1) a T ' + S N= −{ (1)} (1) T T S b ' ( , ) = T (1) T S b ( , ) (1) T T S b ' ( , )
(1) T T S b ' ( , ) ' S M2 (1) b
(1) (1) (1) a T S b a T ( , ) ' + + N
(1) (1) (1) (1) a T S b a T T T S b ( , ) ' ' ( , ) + + (1) T T S b ' ( , ) = S M2 t
ij , (1) , (2) = = i j ( , ) ( { }, max{ ,0}) ( { , }, ) T S t a T S i b b t a a T S i j t = + − + − = + + − i i i i j ij
max{ max{ , 0} , 0}
max{max{ , 0}, }
max{ , , }
ij j i i j
ij j i j i j i
ij j i j i i i j i
t b b t a a
t b b a t a a b
t b b a a t a a a b
= + + − −
= + − + − −
= + − − + + −
ij , min{ , } min{ , } i j j i b a b a ij ,
ij , ij ,
ij , '
max{ , , } ji j i j i j j i j t b b a a t a a a b = + − − + + − ij , min{ , } min{ , } i j j i b a b a
在加工完积压的作业之后才能开始加工 ，等待时间 才能利用；或者， ，
即处于空闲状态，不需要额外等待时间，直接加工 ，等待时间 才能利用。
综上，取等待时间 。
2. 最优子结构证明：(问题最优解包括子问题最优解) 设 是 的一个最优调度，加工顺序为 ，其所需的加工时间为
，记 ，则 。
证明：由 的定义可知， 是最优的，故 ，若这个子调度不是
最优解的话，即 ，设存在一个 为作业集 在 等待 情况下的最
优调度，所需时间为 ，这与 是 的一个最优调度矛盾，
故 ，故： ，最优子结构
得证。
3. Johnson 法则 设 为作业集 在 等待 情况下的最优调度，若在此调度中，排在最前面的两个作
业分别是 ，即 。
如果作业 满足 ，则称作业 满足 Johnson 不等式。
若 不满足 Johnson 不等式，则交换 位置即可满足 Johnson 不等式。
证明如下：
交换 位置之后形成的另一个调度 ，则：
当 满足 Johnson 不等式时， ，有：
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
