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

很多参考书在讲解动态规划算法的时候都会使用到一个例子----流水线的装配调度问题。如图所示： 从in进入到流水线1需要e1的时间，这里的每个表格代表一个装配站，在同一条流水线中，从一个装配站到另一个装配站是不需要时间的，而跨流水线则需要时间，我们定义一个数组 t来保存流水线的切换时间，（例如：从流水线1【2】到流水线2【3】)，那么这个时间为 t[1][2]，在每个装配站上装配也需要时间，我们定义一个数组 a来保存装配时间,例如：在流水线1上的装配站2所需的装配时间为 a[1][2]。现在所要求的是从 in到 out的最短时间。 分析路线构造（描述最优解的结构）： 先对这个问题进行分析，假设我们现在已经装配到了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这个数组的过程。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！