“加工顺序问题”又被称为“批处理作业调度问题”。

设有n个工件需要在机器M1和M2上加工，每个工件的加工顺序都是先在M1上加工，然后在M2上加工。t1j，t2j分别表示工件j在M1，M2上所需的加工时间（j=1，2，···，n）

问：应如何在两机器上安排生产，使得第一个工件从在M1上加工开始到最后一个工件在M2上加工完所需的总加工时间最短？关于此（类）问题的回溯法求解被作为经典案例在很多教材或参考文献中出现，现要求设计求解此问题的动态规划算法。

请用数学语言对“加工顺序问题”加以抽象，在此基础上给出动态规划求解该问题的递归公式。要求对所给公式中的符号意义加以详细说明，并简述算法求解步骤。用一种你熟悉的程序设计语言加以实现。

流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压两种情况。

设全部作业的集合为N={1,2,...,n}，S⊆N，S是N的一个子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。这种情况下，完成S中作业所需的最短时间记为T(S,t)，流水作业调度问题的最优值为T(N,0) 证明最优子结构性质

因为公式手写比较方便，所以暂时使用手写，待转电子版。

递归计算最优值

由流水作业最优子结构的性质可知，全部作业集合N的最优调度时间T(N,0)计算方式如下：

推广到一般情形下，便有递归函数： max{t-ai,0} 这一项是由于：在作业i完成M1上的加工，该转到M2上加工的时候，M2的状态可能是空闲/占用。

上述递归函数的更详细的解释如下图： 为了便于理解，手动走一下递归↓（更完整的手动递归过程，见页面最下附录） 然后就是代码了。关于如何存储求解的小问题，避免重复运算，下面是思考过程。

脑洞大开过程↓

一开始，我想模仿矩阵连乘问题求解，用二维数组表示被加工的工件，横坐标表示工件的起点，纵坐标表示工件的终点。但是发现本问题中的工件不连续（5个工件就有32种不同的组合），无法用二维数组表示。

既然工件组合不连续，我又考虑模仿0-1背包问题的解法求解。0-1背包是建立一个二维数组，横坐标是背包的容量，纵坐标是可以装入的物品编号。然后从装入物品编号为0开始，将将背包容量从0开始，一点一点扩大，计算能装入的最大的物品价值。当可装入的物品编号为总物品个数的情况下，当背包容量达到实际容量时，能装入物品的最大价值就是整个问题的最优解。 但是流水作业调度问题和背包问题差别仍然很大。 1、交换0-1背包问题的放入顺序，最优解仍然是最优解，而交换流水作业的加工顺序，最优解可能就不是最优了。 2、0-1背包息壤得到装入的最大价值；流水作业希望得有最少的加工时间。 于是放弃模仿0-1背包问题。

考虑后发现，流水线作业调度问题具有两个特点： 1、子问题的工件不连续，可跳跃 2、一般情况下，交换两个工件的加工顺序后，总加工时间会改变。

又受到某五子棋人机对战算法的启发（此处省略五子棋算法），具体是将每种赢的状态用0和1表示出来（整个棋盘二维数组上只有5个连续的1，其余全是0，可以表示其中一种赢的状态）。

类比可得，本流水线调度问题也可以用0和1表示所有可能的工件集合（每一个工件被加工或不被加工的状态）。

比如说有5个工件，每一个工件都可能被加工或不被加工，因此共有2^5=32种状态（组合方式）

又考虑到在每种状态下，如果想要求最小加工时间，还要知道该状态下机器M2上的等待时间。于是建立一个类JiHe，实例化为JiHe[32]，里面设置minTime[]属性，存储在当前组合方式下，等待时间为数组下标时的最短加工时间。

这样，就成功的存储了子问题的最优解。求解顺序就是：从加工零个工件开始填写minTime[]，一直到加工完所有工件。

首先，我们假设有5个工件待加工，分别为：J0,J1,J2,J3,J4,J5。 它们在两个机器上加工时间如下： 1、定义一个类GongJian，记录每个工件两个加工步骤分别需要的时间（程序运行时用户输入）。 输入时间后 2、定义一个类JiHe，表示一种状态（组合方式），表示有哪些工件被加工。 用类似于二进制加一的方式，填写所有可能的工件组合。比如，5个工件有2^5=32种组合方式。 之后遍历32种工件组合JiHe[32]，把每种组合下，被加工的总工件个数保存在jihe[i].num中，此操作便于后续根据总工件个数（0，1，2，3，4，5），按顺序进行自底向上计算。

3、自底向上，计算每个状态的最短时间

而5个工件被加工时，等待时间为0时的最短加工时间即为整个流水作业调度问题的解。 以下为逐步调试过程：

初始状态下，数组值都为0↓ 0个工件被加工时，等待时间为0,1,2,3,…,100时的最短加工时间↓ 1个工件被加工时，等待时间为0,1,2,3,…,100时的最短加工时间↓ 2个工件被加工时，等待时间为0,1,2,3,…,100时的最短加工时间↓ 3个工件被加工时，等待时间为0,1,2,3,…,100时的最短加工时间↓ 4个工件被加工时，等待时间为0,1,2,3,…,100时的最短加工时间↓ 5个工件被加工时，等待时间为0,1,2,3,…,100时的最短加工时间（至此，全部计算完成）↓ 此时，jihe[31].minTime[0]存放的就是加工完全部工件所需的最短时间，也就是在加工5个工件，且M2等待时间为0时，加工所需要的最短时间（最优解）。

最后将此时间输出即可。

注意：使用时，要在代码的宏定义中修改工件总数NUM，手动计算并填写POWNUM = 2^NUM 如下图所示，工件总数为6，2^6=64，因此宏定义NUM=6 POWNUM=64 输入1

2 5 7 3 6 2 4 7 6 9 8 2

输出1

最短时间:35

输入2

2 5 4 2 3 3 6 1 1 7

输出2

最短时间:19

工件总数根据宏定义可变，需要在运行前，填写宏定义的NUM POWNUM 各个工件在机器上的加工时间在运行时由用户录入