流水线调度问题——动态规划

时间:2024-10-21 08:13:44
很多参考书在讲解动态规划算法的时候都会使用到一个例子----流水线的装配调度问题。如图所示:
从in进入到流水线1需要e1的时间,这里的每个表格代表一个装配站,在同一条流水线中,从一个装配站到另一个装配站是不需要时间的,而跨流水线则需要时间,我们定义一个数组 t来保存流水线的切换时间,(例如:从流水线1【2】到流水线2【3】),那么这个时间为 t[1][2],在每个装配站上装配也需要时间,我们定义一个数组 a来保存装配时间,例如:在流水线1上的装配站2所需的装配时间为 a[1][2]。现在所要求的是从 inout的最短时间。
分析路线构造(描述最优解的结构):
先对这个问题进行分析,假设我们现在已经装配到了n,可以是流水线1的n也可以是流水线2的n,那么从1到n-1都是最短时间完成的(也就是说从1到n-1的过程具有最短时间),这里有四种情况(上下两条是对称的),这里对流水线1进行分析:
1)、通过流水线1的装配站n-1,然后直接通过流水线1的n;
2)、通过流水线2的装配站n-1,然后从流水线2切换到1,之后通过流水线1的n;
对于流水线2的情况和流水线1一样。
构造递归解:
我们假设f*为最短时间,则f* = min(f[1][n]+x1 , f[2][n]+x2),那么根据题意我们知道:f[1][1] = e1+a[1][1];  f[2][1] = e2+a[2][1].  现在我们再来考虑如何计算f[i][j],(这里i=1或2;j=2,3,4,...,n)。
根据刚才对流水线路线的分析  1)、2)两条我们得出:
f[1][j] = min(f[1][j-1]+a[1][j] , f[2][j-1]+a[1][j]+t[2][j-1]);
f[2][j] = min(f[2][j-1]+a[2][j] , f[1][j-1]+a[2][j]+t[1][j-1]);
求最短时间:
根据上面的递归式,我们可以计算出f这个数组里的值,又因为我们定义的这个f数组里面所存放的就是从装配站1到j的最短时间,所以以此我们就可以计算出从in到out的最短时间。
下面我们所要做的就是将上面的递归式以程序算法的形式写出:
            f[1][1] = e1+a[1][1];
            f[2][1] = e2+a[2][1];

            for j = 2 to n
                  do if f[1][j-1]+a[1][j] < f[2][j-1]+a[1][j]+t[2][j-1]
                        then 
                            f[1][j] = f[1][j-1]+a[1][j] 
                             //line[1][j] = 1
                        else  
                            f[1][j] = f[2][j-1]+a[1][j]+t[2][j-1]   
                            //line[1][j] = 2

                      if f[2][j-1]+a[2][j] < f[1][j-1]+a[2][j] + t[1][j-1]
                      then 
                            f[2][j] = f[2][j-1]+a[2][j]
                           //line[2][j] = 2
                      else 
                            f[2][j] = f[1][j-1]+a[2][j]+t[1][j-1]
                           //line[2][j] = 1

            if f[1][n]+x1 <= f[2][n]+x2
                then f* = f[1][n]+x1
                else  f* = f[2][n]+x2
这个算法的过程还是比较好理解的,分为三部分,初始化、计算数组值、比较得出一个最小时间值。
当然这个算法只是仅仅的计算出了最短时间值,要是我们想要知道装配的每个站点,则还要用一个数组保存我们通过的流水线过程。假设使用一个数组line[i][j]来保存(i=1或2,j=2,3,...,n),那么我们就可以在每次计算出f[i][j]的地方对line这个数组进行赋值,也就是上面算法中加//的部分。
动态规划算法的设计可以大致分为以下四个步骤:
1)、描述最优解的结构;
2)、递归定义最优解的值;
3)、按自底向上的方式计算最优解的值;
4)、由计算结果构造一个最优解。
这里的第四步就相当于我们保存line这个数组的过程。