流水作业调度问题（不能直接使用动态规划法的例子） 流水作业调度的定义：
设有n个作业，每一个作业i均被分解为m项任务: Ti1, Ti2, ┅ , Tim(1≤i≤n，故共有nm个任务)， 要把这些任务安排到m台机器上进行加工。 如果任务的安排满足下列3个条件， 则称该安排为流水作业调度：
1. 每个作业i的第j项任务Tij (1≤i≤n, 1≤j≤m)
只能安排在机器Pj上进行加工；
2. 作业i的第j项任务Tij(1≤i≤n, 2≤j≤m)的开始 加工时间均安排在第j-1项任务Ti,j-1加工完毕之后； (任何一个作业的任务必须依次完成，
前一项任务完成之后才能开始着手下一项任务) 3. 任何一台机器在任何一个时刻最多只能承担 一项任务。
最优流水作业调度：
设任务Tij在机器Pj上进行加工需要的时间为tij。 如果所有的tij (1≤i≤n, 1≤j≤m)均已给出，
要找出一种安排任务的方法，
使得完成这n个作业的加工时间为最少。 这个安排称之为最优流水作业调度。 完成n个作业的加工时间： 从安排的第一个任务开始加工,
到最后一个任务加工完毕，其间所需要的时间。
优先调度：
允许优先级较低的任务在执行过程中被中断， 转而去执行优先级较高的任务。 非优先调度：
任何任务一旦开始加工，就不允许被中断， 直到该任务被完成。
流水作业调度一般均指的是非优先调度。 非优先调度可看成是特殊的优先调度：
所有任务的优先级均相同。 7 5 8 e.g. （tij）= 2 2 6 0 7 4
注意：tij为0表示作业i无须在机器Pj上进行加工、
即该道工序可以省略。
已经证明，当机器数(或称工序数)m≥3时，
流水作业调度问题是一个NP-hard问题 （e.g分布式任务调度）。 （粗糙地说，即该问题至少在目前
基本上没有可能找到多项式时间的精确最优算法。） ∴ 目前仅当m=2时，该问题可有多项式时间的算法。 为方便起见，记ti1为a（作业i在P1上加工所需时间）， i ti2为bi（作业i在P2上加工所需时间）。 当机器P1为空闲即未安排任何加工任务时，
则任何一个作业的第一个任务（第一道工序） 都可以立即在P1上执行，无须任何先决条件。 因此易知：
必有一个最优调度使得在P1上的加工是无间断的。 证明：设是一个最优调度，
且在P1上安排的加工是有间断的。
则我们可以把所有在P1上出现间断处的任务的 开始加工时间提前，使得在P1上的加工是无间断的； 而在P2上仍按原先的安排。 把这样调整之后的调度记作为’。
由于在调度’下，任何一个任务在P1上加工的结束 时间不晚于在调度下的结束时间，故调度’不会 影响在P2上进行加工的任何一个任务的开始时间。 由于调度’在P1上的结束时间不晚于调度， 在P2上的结束时间与调度相同，而又是最优调度， 所以’也是最优调度。由此我们得到：
一定有一个最优调度使得在P1上的加工是无间断的。 另外，也一定有一个最优调度使得在P2上的
加工空闲时间（从0时刻起算）为最小， 同时还满足在P1上的加工是无间断的。 （证明留作作业）
因此，如果我们的目标是只需找出一个最优调度，
我们可以考虑找：在P1上的加工是无间断的、 同时使P2的空闲时间为最小的最优调度。 （根据上述分析，这样的最优调度一定存在。）
此外可以证明，若在P2上的加工次序与在P1上的
加工次序不同，则只可能增加加工时间 （在最好情况下，增加的时间为0）。 （证明留作作业）
也就是说，在P1上的加工次序已确定的情况下， 至少有一个最优调度，其在P1上的加工次序 与在P2上的加工次序是完全相同的 （注意：这一点对m≥3不成立）。 因此，当只需找到一个最优调度时，我们
仅需要考虑在P1和P2上加工次序完全相同的调度。 以下的讨论均以此为前提。 为简化起见，我们假定所有ai0。 因为如果有ai=0的作业，
我们可以先对所有ai0的作业进行调度， 然后把所有ai=0的作业放到最前面执行即可 （可按任意次序）。 最优调度具有如下性质：
在所确定的最优调度的排列中去掉第一个执行作业后， 剩下的作业排列仍然还是一个最优调度，
即该问题具有最优子结构的性质。
而且，在计算规模为n的作业集合的最优调度时， 需多次使用该作业集合的子集合的最优调度， 即该问题亦具有高度重复性。
这就引导我们考虑用动态规划法求解。 然而，正如下面将会看到的，
虽然使用动态规划法可以得到一些有用的结果， 但如果不加以某种改进，完全照搬动态规划法 会使得算法的时间复杂度成为指数量级。 问题求解的思路如下。
设N={1，2，┅，n}是全部作业的集合， 作业集S是N的子集合即有S N。
在我们对S中的第一个作业开始进行加工时， 机器P2上加工的其它作业可能还尚未完成， 不能立即用来对S中的作业进行加工。 假设对机器P2需等待t个时间单位以后才可以 用于S中的作业加工（t也可以为0即无须等待）， 并记g(S,t)为在此情况下完成S中全部作业的 最短时间，则可用下述递归表达式来表出g(S,t)：
g(S,t)=miniS{ai + g(S-{i},bi+max{t-ai,0})} （*） 说明：当选定作业i为S中第一个加工作业之后， 在机器P2上开始对S-{i}中的作业进行加工之前， 所需要的等待时间为bi+max{t-ai,0}。 这是因为，若P2在开始加工S中的作业之前 需等待t个时间单位且t ai，
则作业i在P1上加工完毕（需时ai）之后， 还要再等t-ai个时间单位才能开始在P2上加工； 若t≤ai，则作业i在P1上加工完毕之后， 立即可以在P2上加工，等待时间为0。 故P2在开始对S-{i}中的作业进行加工之前， 所需要的等待时间为bi+max{t-ai,0}。 （bi是作业i在P2上加工所需的时间）。 当S=N即全部作业开始加工时， 由于P2上尚无任何正在加工的作业， 故此时等待时间t=0。
于是有：g(N,0)=min1≤i≤n{ai+ g(N-{i},bi)}
虽然根据（*）式我们可以编写出计算g(N,0)的程序， 但该算法的时间复杂度为指数量级，因为
算法中对N的每一个非空子集都要进行一次计算， 而N的非空子集共有2-1个。
因此，我们不能直接使用动态规划法来求解该问题， 而需要对算法作一定的改进。 设是作业子集S的某一个调度，
该调度首先安排作业i，其次安排作业j， P2需等待t个时间单位以后才可以用于S中的 作业加工。记t’= bi+max{t-ai,0}， 则由（*）式调度的g(S,t)可写为g(S,t)= ai+g(S-{i}, t’)=ai+aj+g(S-{i,j}, bj+max{t’-aj,0})。 由于x+ max{y1, y2,„,yn}= max{x+y1,x+y2,„,x+yn}、
t’= bi+max{t-ai,0}，所以 bj+max{t’-aj,0}
= bj + max{bi+max{t-ai,0}-aj, 0} = bj + bi - aj + max{max{t-ai,0},aj-bi} = bj + bi - aj + max{t-ai, 0, aj-bi} = bj+ bi - aj - ai + max{t, ai, ai+aj-bi}。 记tij= bj+ bi - aj - ai +max{t, ai, ai+aj-bi} （= bj+max{t’-aj,0}），
n
则调度的g(S,t)=ai+aj+g(S-{i,j}, tij)。 将调度中的作业i与j的加工次序交换 （其它加工次序不变）所得调度记为’，
则调度’的最早完工时间g’(S,t)=ai+aj+g(S-{i,j}, tji)。 比较g(S,t)与g’(S,t)两式，显然，若tij tji， 则有g(S,t) g’(S,t)即i在前j在后的安排用时较少； 反之，若tij tji，则j在前i在后的安排用时较少。 因此，需要找出能判断tij与tji之间大小关系的表达式。 由于tij= bj+ bi - aj - ai +max{t, ai, ai+aj-bi}，
tji= bj+ bi - aj - ai + max{t, aj, ai+aj-bj}， 故tij-tji= max{t, ai, ai+aj-bi} - max{t, aj, ai+aj-bj}， 因此我们只要比较max{t, ai, ai+aj-bi}与
max{t, aj, ai+aj-bj}的大小就可以了, 即tij tji当且仅当
max{t, ai, ai+aj-bi} max{t, aj, ai+aj-bj}。 由于max{t, ai, ai+aj-bi} max{t, aj, ai+aj-bj} 对任何t 0成立，当且仅当
max{ai, ai+aj-bi} max{aj, ai+aj-bj}成立，当且仅当 ai+aj+max{-aj, -bi}ai+aj+max{-ai, -bj}成立，当且仅当
max{-aj, -bi} max{-ai, -bj}成立，当且仅当 min{aj, bi} min{ai, bj}成立 （此式称为Johnson不等式）。 当min{ ai , aj , bi , bj}为ai或者bj时， 即Johnson不等式成立时，有tij tji， 此时把i排在前j排在后的调度用时较少； 反之，若min{ ai , aj , bi , bj}为aj或者bi时， 则j排在前i排在后的调度用时较少。 将此情况推广到一般。
当min{ a1, a2,┅, an , b1, b2,┅, bn }=ak时， 则对任何ik，都有min{ai, bk} min{ak, bi}成立， 故此时应将作业k安排在最前面， 作为最优调度的第一个执行的作业； 当min{ a1, a2,┅, an , b1, b2,┅, bn }= bk时， 则对任何ik，也都有min{ak, bi}min{ai, bk}成立， 故此时应将作业k安排在最后面， 作为最优调度的最后一个执行的作业。
n个作业中首先开工（或最后开工）的作业确定之后， 对剩下的n-1个作业采用相同方法可再确定
其中的一个作业,
作为n-1个作业中最先或最后执行的作业； 反复使用这个方法直到最后只剩一个作业为止， 最优调度就确定了。
e.g. n=4, (a1, a2, a3, a4)=(5,12,4,8),
(b1, b2, b3, b4)=(6,2,14,7)。
(a1, a2, a3, a4)与(b1, b2, b3, b4)合起来排序的结果 为(2,4,5,6,7,8,12,14)=(b2,a3,a1,b1,b4,a4,a2, b3)。 最小数是b2，故作业2应安排为最后一个作业： (4)←2。
次小数是a3，故作业3应安排为第一个作业：(1)←3。 第3小数是a1，故作业1安排为第二个作业：(2)←1。 第4小数是b1，因作业1已安排过，故转看下一个数。 第5小数是b4，故作业4应安排为倒数第二个作业：
(3)←4。至此，所有作业均已安排完毕。
根据上述，很容易给出本例的调度图解。 求解该问题的算法如下。 1. 建立长为2n的数组C，
将a1, a2,┅, an依次放入C[1]~ C[n]中，
b1, b2,┅, bn依次放入C[n+1]~ C[2n]中。
/* O(n), 下面将对这2n个数进行排序*/
2. 对长为2n的数组D进行初始化： D[1]~D[n]中依次放1,2,┅,n，
D[n+1]~D[2n]中依次放-1,-2,┅,-n。 /* O(n), */ /*分别对应于a1, a2,┅, an和b1, b2,┅, bn的下标*/ 3. 对数组C进行排序，
D[k]始终保持与C[k]的对应关系。 （若C[i]与C[j]对换，则D[i]也与D[j]对换。 或将C，D放在同一结构体中。）
当a1, a2,┅, an及b1, b2,┅, bn按从小到大排好序之后， D[1]~ D[2n]也就按从小到大的次序记录了这些ai和bj 的下标即作业号（bj的下标前有一负号以区别于ai））。/*O(n log n)*/
4. 将E[1]~ E[n]全部置为“No”。
/* O(n)，表示所有任务均尚未被安排*/
5. 下标变量初始化：i←1；j←n；k←1； /*O(1)，*/
/*i指向当前最左空位F[i]，*/ /*放当前应最先安排的作业号;*/
/* j指向当前最右空位F[j]，*/ /*放当前应最后安排的作业号;*/
/* k从1开始逐次增1，D[k]（或-D[k]）*/ /*按ai和bj从小到大的次序依次给出作业号。*/ 6. while i j do
{ /* 作业尚未安排完毕，i从小到大, j从大到小*/ if D[k]>0 then /*D[k]>0即D[k]中放的是ai下标*/ {if E[D[k]]为“No”then /*作业D[k]尚未安排*/
{F[i]←D[k]; i增1; E[D[k]] 置为“Yes”}
/*作业D[k]放在当前最左空位*/
} else /*D[k]<0，则–D[k]是bj下标*/ {if E[–D[k]]为“No”then /*作业–D[k]尚未安排*/
{F[j]←–D[k]; j减1; E[–D[k]] 置为“Yes”} } /*作业–D[k]放在当前最右空位*/ k增1; /*准备检查下一个D[k]以便后续作业安排*/ } /*注意while循环每轮执行只需要O(1)时间*/ 算法分析：
第1，2，4句的初始化均只需要O(n)时间， 第3句的排序需要O(n log n)时间，
第5句的下标变量初始化只需要O(1)时间， 第6句的循环，关键是“if D[k]>0”的执行次数。 由于D[1]~ D[2n]中放的是1,2,┅,n, -1,-2,┅,-n 共2n个数（注意C数组排序后次序已经打乱）， 且循环每执行一次k均增1，故或早或迟 D数组中任一m或-m（m=1,2,┅,n）至少有一个 会被“if D[k]>0”语句检查过。 若m先遇到，则使得i增1； 若-m先遇到，则使得j减1，
执行到第2n-1次时，每一对数至少有一个检查过， 即对m=1,2,┅,n，i增1、j减1必执行其一， 故最多执行2n-1次，必然出现i > j， 使得循环中止，故while执行时间是O(n)。 ∴算法的时间复杂度为O(n log n)。 小结：
满足1）高度重复性 2）最优子结构性质 时，一般 采用动态规划法，但偶尔也可能得不到高效的算法。 若问题本身不是NP-hard问题，
那么进一步分析后就有可能获得效率较高的算法。
若问题本身就是NP-hard问题， 那么与其它的精确算法相比， 动态规划法性能一般不算太坏，
但有时也需要对动态规划法作进一步的加工。 e.g. 0-1背包问题。
