1、*独立任务最优调度问题张 雪福州大学数学与计算机科学学院N问题的描述：问题的描述： 有 N个作业 x1,x2 xn等待处理。现在有 2台机器 A和 B，每个作业 xi在 A机器处理时间为 ai，在 B机器处理时间为 bi。 每个作业 不能分开 由 2台机器处理，每台机器 不能同时 处理 2个作业。 设计一个动态规划算法，使得这 2台机器处理完这 n个作业的时间最短 (从任何一台机器开工到最后一台机器停工的总时间 )问题的描述：问题的描述： 研究一个实例（例 1-1）： (a1,a2,a3,a4,a5,a6) (2,5,7,10,5,2) (b1,b2,b3,b4,b5,b6) (3,8,4,1
2、1,3,4)x6x2,x1aibixi选择机器编号A机器总时间B机器总时间x1 A 2 0x2 B 2 8x3 B 2 12x4 A 12 12x5 B 12 15x6 A 14 15任 务属性Thus, the total time is: 15(2,5,7,10,5,2) (3,8,4,11,3,4)解动态规划题的四步骤解动态规划题的四步骤分析最优解的结构（难点）分析最优解的结构（难点）建立递归关系建立递归关系计算最优值计算最优值构造最优解构造最优解分析最优解的结构（一）分析最优解的结构（一） 起初，我们会这样分析最优解结构：设前 k个任务分配处理情况的一个最优解 Y1,Y2 Yk(其中
3、Yi A,B)，包含前 k-1个任务分配处理情况最优解 Y1,Y2Y k-1。 但是我们很快就找到反例（例 1-2 将例 1-1换位置）。 (a1,a2,a3,a4,a5,a6) (2,7,5,5,2,10) (b1,b2,b3,b4,b5,b6) (3,4,8,3,4,11) 当 k=1时， t1=2， x1在 A上执行 当 k=2时， t2=4， x2在 B上执行 当 k=3时， t3=7， x3在 A上执行 当 k=4时， t4=7， x4在 B上执行（ k=4时唯一最优解） 事实上，由最终解看出，当 k=3时， x3应该在 B执行才能达到最优解(2,7,5,5,2,10) (3,4,8
4、,3,4,11)分析最优解的结构（二）分析最优解的结构（二） 上述分析最优解结构的问题在于，只是单纯分析前 k个任务处理的最小时间，并没有将 xk在 A机器和 B机器上执行的时间分开考虑。就算前 k个任务处理的最小时间都是 mint，但是存在多个处理方式。 所以，如果考虑前 k个任务 x1,x2 xk， 剩下的任务都让 B机器处理 ， A机器处理时间总和为 sumak ， B机器处理时间总和为 sumbk。若在每个 固定 的 sumak情况下， sumbk达到最小，则最终解是针对每个 suman, 最短时间为： min(max(suman,sumbn) 此结论可证：此结论可证： 设 Y1,Y2
5、 Yn(其中 Yi A,B)是 n个任务的一个最优解。若有一个最优解 Z1,Z2 Zk(其中 Zi A,B)在与 Y1,Y2 Yk相同的sumak下， sumbzsumby 因为 是固定的， sumbz- sumby- 这意味着当 ik时，在 Zi解下 B机器处理总和比 Yi更大 那么我们取 Y(k+1)=Z(k+1) Yn=Zn， 得到的 Y1,Y2 Yn一定比Z1,Z2Z n优 (或者一样优 )。分析最优解的结构（三）分析最优解的结构（三）分析最优解的结构（三）分析最优解的结构（三） 或许有人会问： suma固定，那么 sumb不也是要一样的么？ 还是看这个例子（同例 1-1）： (a1,
6、a2,a3,a4,a5,a6) (2,5,7,10,5,2) (b1,b2,b3,b4,b5,b6) (3,8,4,11,3,4) 当 k=3并且 suma=7时， sumb的选择情况有两种，要么是 4+18，要么是 11+18. 或许有人会问：既然 k之后的 B机器处理时间相同，为什么要把它算在 sumb内？ 或许还有人问：那 suma是怎么求的？难道是穷举？ 稍后解答解动态规划题的四步骤解动态规划题的四步骤分析最优解的结构分析最优解的结构建立递归关系建立递归关系计算最优值计算最优值构造最优解构造最优解建立递归关系建立递归关系 设前 i个任务完成后， A机器处理时间总和为 j， B机器处理时间总和最小值存在 mij中 则递归式（式）如下：第 i个任务由A完成第 i个任务由 B完成最终结果是 max(min(j， mnj)
