双机调度问题

https://www.cnblogs.com/chuaner/p/11776669.html

假设有两个处理机 A、B，以及 n 个待处理的任务。第 i 个任务在处理处理机 A 上处理需要的时间为 $a_i$，在处理机 B 上处理的时间为 $b_i$，两个处理机可以并行处理任务，但单个处理机不能同时执行任务。求得顺序完成这些任务所需要的最短时间

设 $F(k,x)$ 表示完成前 k 任务情况下 A 耗时 x 的时候的 B 的耗时，根据第 k 个任务是 A 执行还是 B 执行有下面的递归式：

$$F(k,x)=min\{\begin{array}{l}F(k-1,x)+B_k\\ F(k-1,x-A_k)\end{array}$$

最终求

$$\underset{x}{\min }\{max(x,F(k,x))\}$$

这里将原本对称的描述变成不对称的才能做出来