算法201405-动态规划.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 对于作业调度中一个作业i(1?i?n)，在加工过程中，除去调度中的第1个作业，其他作业可能需要等待一段时间才可以开始其在M2上的加工，不妨将其他作业构成的集合记为S，S?N。 设若机器M2需等待t(t?0)个时间单位以后才可以对S中的作业加工，利用T(S,t)表示在此情况下完成S中全部作业的最短时间。 调度开始时，S=N，t=0，T(N,0)对应为完成N中全部作业的需要的最短时间， 即如果首先安排作业i，则完成其他作业需要的最短时间为 2 最优值递归关系 其中bi+max{t-ai,0}是当选定作业i为S中第一个加工作业之后，在机器M2上开始对S-{i}中的作业进行加工之前，所需要的等待时间为bi+max{t-ai,0}。 How to use “bi+max{t-ai,0}” ？ tai,作业i在机器1上完成后仍需等待； t=ai, tai, ???????? 此处指向机器等待时间，而不是作业等待时间 3 递归计算最优值 按照递归关系式（5-11）可以设计出最优调度问题的动态规划算法 问题：需要计算的子问题个数与集合N有什么关系？ 答：与集合N的子集个数相关，集合N的非空子集合个数为2n-1，说明利用动态规划方法可以求解，但不能设计出有效的算法，需要考虑其他的方法。 注意：作业在机器M2上的加工空闲等待时间是影响问题的关键 设π是作业子集S的某一个调度，该调度首先安排作业i，其次安排作业j，机器M2需等待t个时间单位以后才可以用于S中的作业加工。记t’= bi+max{t-ai,0}， 调度π的T(S,t)为 T(S,t)=ai+ T(S-{i}, t’) 　　= ai+ aj+ T(S-{i,j}, bj+max{t’-aj,0}) Ｗｈｙ？ bj+max{t’-aj,0} = bj+max{bi+max{t-ai,0}-aj, 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} 调度π的T(S,t)=ai+ aj+ T(S-{i,j}, tij) 若将调度π中的作业i与j的加工次序交换（其它加工次序不变） 所得调度记为π’， 调度π’的最早完工时间为T’(S,t)=ai+ aj+ T(S-{i,j}, tji) 。 ？？？？？？ 如果tij ≤ tji， 则T(S,t) ≤ T’(S,t)，即i在前，j在后的安排用时较少，若tij tji，则j在前，i在后的安排用时较少。 调度π的T(S,t)=ai+ aj+ T(S-{i,j}, tij) 调度π’的T’(S,t)=ai+ aj+ T(S-{i,j}, tji) 。 判断tij 和tji大小关系的方法 tij-tji= 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{ ai, ai+aj-bi}?max{ aj, ai+aj-bj} ?max{-aj, -bi}?max{ -ai, -bj} tij?tji? min{aj, bi} ?min{ai, bj} tij?tji? min{aj, bi} ?min{ai, bj} (Johnson不等式 ) 即当min{ ai , aj , bi , bj}为ai或者bj时，作业i和j满足Johnson不等式 当作业i和j满足Johnson不等式时，tij?tji，此时把作业i安排在前，作业j安排在后的调度用时较少， 当tji?tij时，此时把作业j安排在前，作业i安排在后的调度用时较少。 推广到一般情形则有： tij?tji? min{aj, bi} ?min{ai, bj} (Johnson不等式 ) （1）当min{ a1, a2,?, an , b1, b2, ?, bn }=ak时， 对任何i≠k，都有min{ai, bk} ≥ min{ak, bi}成立，此时应将作业k安排在最前面， 作为最优调度的第一个执行的作业； （２）