算法设计与分析

之前讲过一个相似的问题流水作业调度问题，那一道题最开始用动态规划，推到最后得到了一个Johnson法则，变成了一个排序问题，有兴趣的可以看一下https://www.cnblogs.com/wkfvawl/p/11667092.html

本篇博客主要参考自https://blog.csdn.net/qq_40685275/article/details/80403976

给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。作业Ji需要机器j的处理时间为tji。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

 例：设n=3，考虑以下实例：

 看到这里可能会对这些完成时间和是怎么计算出来的会有疑问，这里我拿123和312的方案来说明一下。

 对于调度方案（1,2,3）

作业1在机器1上完成的时间是2，在机器2上完成的时间是3

作业2在机器1上完成的时间是5，在机器2上完成的时间是6

作业3在机器1上完成的时间是7，在机器2上完成的时间是10

所以，作业调度的完成时间和= 3 + 6 + 10

这里我们可以思考一下作业i在机器2上完成的时间应该怎么去求？

作业i在机器1上完成的时间是连续的，所以是直接累加就可以。但对于机器2就会产生两种情况，这两种情况其实就是上图的两种情况，对于（1,2,3）的调度方案，在求作业2在机器2上完成的时间时，由于作业2在机器1上还没有完成，这就需要先等待机器1处理完；而对于（3,1,2）的调度方案，在求作业2在机器2上完成的时间时，作业2在机器1早已完成，无需等待，直接在作业1被机器1处理之后就能接着被处理。

综上，我们可以得到如下表达式

类Flowshop的数据成员记录解空间的结点信息，M输入作业时间，bestf记录当前最小完成时间和，数组bestx记录相应的当前最佳作业调度。

数组x[i]，bestx[i]，二维数组m[j][i];数组x记录当前调度；bestx记录当前最优调度；初始时，x[i]=i ;      bestx[i]=∞;     (i=0,1,......,n)二维数组m记录各作业分别在两台机器上的处理时间；m[j][i]表示在第i台机器上作业j的处理时间

变量f1,f2,cf,bestf；f1记录作业在第一台机器上的完成时间；f2记录作业在第一台机器上的完成时间；cf记录当前在第二台机器上的完成时间和；bestf记录当前最优调度的完成时间和；

在递归函数Backtrack中，当i>n时，算法搜索至叶子结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。当in) //到达叶子结点，搜索到最底部 { for( i=1; i