本文主要是介绍算法导论--动态规划（装配线调度），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、装配线调度问题
问题：
现有两条装配线，Sij表示第i条上完成第j道工序的装配站。汽车完成组装需要依次完成1~n工序。请找出完成装配并离开装配线的最快路线。
符号说明：
ei：汽车进入装配线i的时间，i=1,2
xi：汽车离开装配线i的时间
aij：在装配站Sij完成装配需要的时间
tij：在装配站Sij完成后离开第i条装配线，进入另一条装配线需要的转移时间
注意，如果完成工序后，下一个工序还在同一条装配线上，则不需要转移时间。
问题求解
我们用Fij表示在第i条装配线上完成第j道工序的最快时间，用F表示完成汽车装配并离开装配线的时间。如果知道F1n和F2n，则有
而要求出F1n和F2n，又需要知道F1n-1和F2n-1，从而有
依次类推，可得如下递归公式
分析
1、采用递归算法求解。
我们采用树的形式来进行说明
每个节点里的符号，表示相应的问题，其孩子节点表示在求解该问题时需要求解的子问题。由此我们很容易得出，对于问题Fij，采用递归算法计算时，需要求解的次数为.
2、动态规划
如果我们不是从上到下求解，而是从下到上求解，求解结果在某个地方保存起来，则可以大大改善求解速度。
例子：
其动态规划解法饿C语言实现
int e0=2,e1=4; //进入第一个装配站时间
int x0=3,x1=2; //离开装配站n（最后一个装配站）的时间
int T[2][5]={{2,3,1,3,4},{2,1,2,2,1}}; //T[i][j]表示装配站S[i][j]完成后转移到另一条装配线的时间
int cF[2][6]; //cF[i][j]表示配站 S[i][j]需要的时间
int L[2][6];
int BestF;
int BestL;
cF[0][0]=e0+A[0][0];
cF[1][0]=e1+A[1][0];
L[0][0]=0; //第一个装配站没有其它装配站，所以直接设为0,其实也可以设其它值
L[1][0]=0; //第一个装配站没有其它装配站，所以直接设为0,其实也可以设其它值
//下面是求Fij的过程
int station;
for (station=1;station<6;station++)
{
//the first line
if(cF[0][station-1]<=cF[1][station-1]+T[1][station-1])
{
cF[0][station]=cF[0][station-1]+A[0][station];
L[0][station]=0;
}
else
{
cF[0][station]=cF[1][station-1]+T[1][station-1]+A[0][station];
L[0][station]=1;
}
//the second line
if(cF[1][station-1]+A[1][station]<=cF[0][station-1]+T[0][station-1]+A[1][station])
{
cF[1][station]=cF[1][station-1]+A[1][station];
L[1][station]=1;
}
else
{
cF[1][station]=cF[0][station-1]+T[0][station-1]+A[1][station];
L[1][station]=0;
}
}
//下面是求BestF和BestL的
if (cF[0][5]+x0<cF[1][5]+x1)
{
BestF=cF[0][5]+x0;
BestL=0;
}
else
{
BestF=cF[1][5]+x1;
BestL=1;
}
int i=0,j=0;
for (i=0;i<2;i++)
{
printf("\n");
}
for (i=0;i<2;i++)
{
printf("\n");
最优路线：0-1-0-1-1-0
这篇关于算法导论--动态规划（装配线调度）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
