用2 台处理机A 和B 处理n 个作业。设第i 个作业交给机器A 处理时需要时间ai ，若由机器B 来处理，则需要时间bi。由于各作业的特点和机器的性能关系，很可能对于某些i， 有ai ≥ bi ，而对于某些j,j≠i，有aj < bj 。既不能将一个作业分开由2 台机器处理，也没有一台机器能同时处理2 个作业。设计一个动态规划算法，使得这2 台机器处理完这n 个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。研究一个实例：(a1,a2,a3,a4,a5,a6)＝(2,5,7,10,5,2)；(b1,b2,b3,b4,b5,b6)＝(3,8,4,11,3,4) 。
独立任务最优调度问题是一个经典的计算机科学中的调度优化问题，它涉及到如何在有限的资源下，合理分配任务以达到最优化的目标。在这个问题中，我们有两台处理机A和B，以及n个作业，每个作业在A或B上处理所需的时间不同。目标是设计一个动态规划算法，使得两台机器处理完所有作业的总时间最短。
我们可以建立状态转移方程来解决这个问题。设F[k][x]表示前k个作业中，A处理了x个作业时，两台机器总共所需的最短时间。我们需要找到最优策略，即对于第k个作业，应该分配给A还是B处理，使得总时间最短。
状态转移方程可以表示为：
F[k][x] = Min{ F[k-1][x] + b[k], F[k-1][x-a[k]] }
其中，F[k-1][x] + b[k]表示第k个作业由B处理，前k-1个作业中A处理了x个作业，总时间为F[k-1][x]加上第k个作业在B上的处理时间b[k]；而F[k-1][x-a[k]]表示第k个作业由A处理，前k-1个作业中A处理了x-a[k]个作业，总时间为F[k-1][x-a[k]]加上第k个作业在A上的处理时间a[k]。
接下来，我们需要初始化状态数组。对于第一个作业，我们只有两种选择：要么由A处理，要么由B处理。所以，F[0][0]表示不处理任何作业时的最短时间为B的处理时间b[0]，F[0][1]表示处理第一个作业且由A处理时的最短时间为a[0]。因此，F[0][0] = Max(0, b[0])，F[0][1] = Max(1, a[0])。
在计算过程中，我们需要维护一个变量x，表示A处理过的作业数量，范围从0到n。对于每个x值，我们根据状态转移方程更新F[k][x]。F[n][x]中的最小值即为我们所求的最短总时间。
以给定实例(a1, a2, a3, a4, a5, a6) = (2, 5, 7, 10, 5, 2)和(b1, b2, b3, b4, b5, b6) = (3, 8, 4, 11, 3, 4)为例，我们可以通过遍历所有可能的作业分配情况，计算出每种情况的总时间，最终找到最优解。这个实例的解是15，意味着两台机器可以在15个单位时间内完成所有作业，这是通过动态规划算法计算得出的最小总时间。
总结来说，独立任务最优调度问题的关键在于利用动态规划的方法，通过状态转移方程找出最优的作业分配策略。实际应用中，这个问题广泛存在于多处理器系统、并发编程等领域，优化调度能够显著提升系统效率。在实现算法时，需要注意合理设计状态空间，避免重复计算，以及正确初始化和更新状态数组，以确保找到全局最优解。
