一、問題描述
裝配線排程問題如下：
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;
}