动态规划思想求流水作业调度问题

动态规划是一种解决一类最优化问题的算法思想。在流水作业调度问题中，我们需要在一条流水线上安排若干个作业，每个作业需要经过若干个加工站才能完成。每个加工站可以同时处理一项作业，但同一作业在同一时间只能在一个加工站进行加工，且每个加工站的加工时间也不同。求解流水作业调度问题的目标是在保证作业完成时间最短的前提下，确定每项作业在每个加工站的加工顺序和加工时间。

对于这类问题，我们可以采用动态规划的思想来求解。具体做法如下：

1. 定义状态：设f(i,j)为第i个作业在第j个加工站结束的最早时间，则状态转移方程为：f(i,j) = max{ f(i-1,j), f(i,j-1) } + t(i,j)，其中t(i,j)为第i个作业在第j个加工站的加工时间。

2. 状态初始化：f(1,1) = t(1,1)，f(1,j) = f(1,j-1) + t(1,j)，f(i,1) = f(i-1,1) + t(i,1)，其中1<=i<=n，1<=j<=m，n为作业数，m为加工站数。

3. 状态转移：按照状态转移方程递推求解f(n,m)即可得到最短完成时间。

4. 逆推求解路径：由于动态规划求解得到的是最优解，因此可以通过逆推的方式求出每个作业在每个加工站的加工顺序和加工时间。