动态规划之装配线调度问题

一、问题描述

装配线调度问题如下：

Colonel汽车公司在有两条装配线的工厂内生产汽车，一个汽车底盘在进入每一条装配线后，在每个装配站会在汽车底盘上安装不同的部件，最后完成的汽车从装配线的末端离开。如下图1所示。
每一条装配线上有n个装配站，编号为j=1,2,...,n，将装配线i（i为1或2）的第j个装配站表示为S(i,j)。装配线1的第j个站S(1,j)和装配线2的第j个站S(2,j)执行相同的功能。然而这些装配站是在不同的时间建造的，并且采用了不同的技术，因此，每个站上完成装配所需要的时间也不相同，即使是在两条装配线上相同位置的装配站也是这样。把每个装配站上所需要的装配时间记为a(i,j)，并且，底盘进入装配线i需要的时间为e(i)，离开装配线i需要的时间是x(i)。正常情况下，底盘从一条装配线的上一个站移到下一个站所花费的时间可以忽略，但是偶尔也会将未完成的底盘从一条装配线的一个站移到另一条装配线的下一站，比如遇到紧急订单的时候。假设将已经通过装配站S(i,j)的底盘从装配线i移走到另一条装配线所花费的时间为t(i,j)，现在的问题是要确定在装配线1内选择哪些站以及在装配线2内选择哪些站，以使汽车通过工厂的总时间最小。

二：问题分析

step1：通过工厂最快路线的结构。

考虑底盘从起始点到装配站S1,j的最快可能路线。如果j=1，则底盘只有一个路线，对于J=2，3 。。则有两种情况。这个底盘可能从装配站S1,j-1直接到S1,j;也可能来自装配站S2,j-1；然后移动到装配站S1,j移动的代价为t2,j-1;

通过装配站S1,j的最快路线一定通过了装配站S1,j-1:这是这个问题的最优子结构。

step2.一个递归的解

在dp中，第二个步骤是利用子问题的最优解来递归定义一个最优解的值。我们选择在两条装配线上通过装配站j的最快路线的问题来作为子问题。j=1,2 .. .n ;

令f i [j]表示一个底盘从起点到装配站Si，j的最快可能时间.

最终目标是确定底盘通过工厂所有路线的最快可能时间。极为f*;底盘必须一路经由2装配线1或2通过装配站n,然后到达工厂的出口。

f*=min(f1[n]+x1,f2[n]+x2);

递归公式为：

step3:计算最快时间.

step4:构造通过工厂的最快路线.

通过这个问题，可以清楚看到dp的设计步骤：

1）描述最优解的结构

2）递归定义最优解的值

3）按自底向上的方式计算最优解的值

4）由计算的结果构造一个最优解 // 在只要求计算最优解的值可以略去

三：代码求解：

#include<iostream>
using namespace std;
int a[3][100]; //a[1][j]表示底盘在装配线s[1][j]所用时间
int t[3][100]; //t[1][j]表示底盘从s[1][j]移动到s[2][j+1]所用时间
int n;//装配站的数目
int e1,e2; //进入装配线1,2时间
int x1,x2;// 离开时间

int f1[100],f2[100];

int L1[100],L2[100]; 
//L1[j]记录第一条装配线上,最优解时第j个装配站的前一个装配站是第一条线还是第二条线上
int f,L;  //最优解是f,最小花费时间,L代表最后是从哪里出来的

void fastest_way()
{
    f1[1]=e1+a[1][1];
    f2[1]=e2+a[2][1];
    for(int j=2;j<=n;j++)

    {
        if((f1[j-1]+a[1][j])<(f2[j-1]+t[2][j-1]+a[1][j]))
        {
            f1[j]=f1[j-1]+a[1][j];
            L1[j]=1;
        }
        else
        {
            f1[j]=f2[j-1]+t[2][j-1]+a[1][j];
            L1[j]=2;
        }
            if((f2[j-1]+a[2][j])<(f1[j-1]+t[1][j-1]+a[2][j]))
        {
            f2[j]=f2[j-1]+a[2][j];
            L2[j]=2;
        }
        else
        {
            f2[j]=f1[j-1]+t[1][j-1]+a[2][j];
            L2[j]=1;
        }
    }
    

        if((f1[n]+x1)<=(f2[n]+x2))
        {
            f=f1[n]+x1;
            L=1;
        }
        else
        {
            f=f2[n]+x2;
            L=2;
        }
     
}


void print_station()
{
    int i=L;
    cout<<endl<<"line "<<L<<"  Station "<<n<<endl;
    for(int j=n;j>=2;j--)
    {
        if(i==1)
            i=L1[j];
        else
            i=L2[j];
        cout<<"line "<<i<<"  Station "<<j-1<<endl;
    }
}


int main()
{
    freopen("station.txt","r",stdin); //可以有文件来输入
    cout<<"请输入装配站的数目\n";
    cin>>n;
    cout<<"请输入进入装配线1,2所需时间";
    cin>>e1>>e2;
    cout<<"请输入离开装配线1,2所需时间";
    cin>>x1>>x2;
    cout<<"输入装配线1上各站加工时所需时间a1[j]";
    for(int j=1;j<=n;j++)
        cin>>a[1][j];
    cout<<"输入装配线2上各站加工时所需时间a1[j]";
    for(int j=1;j<=n;j++)
        cin>>a[2][j];
    cout<<"请输入装配线1上的站到装配线2上的站所需时间t[1][j]";
    for(int j=1;j<n;j++) //j<n
        cin>>t[1][j];
    cout<<"请输入装配线2上的站到装配线1上的站所需时间t[2][j]";
    for(int j=1;j<n;j++) //j<n
        cin>>t[2][j];

    fastest_way();
    print_station();

    return 0;
}

输入如上图，结果如下：