問題描述：

一個找出通過工廠裝配線的最快方式的制造問題。共有兩條裝配線，每一條裝配線上有n個裝配站，編號為j = 0, 1, … , n – 1。裝配線i(i = 0或1)，在裝配站S[i][j]上所需的裝配時間記為a[i][j]。一個汽車底盤進入工廠，然后進入裝配線i的進入時間為e[i]，在通過一條線的第j個裝配站后，這個底盤來到任一條線的第(j + 1)個裝配站。如果留在相同的裝配線上，則沒有移動的開銷；如果在裝配站S[i][j]后，它移動到了另一條線上，則花費時間t[i][j]。在離開一條線的第n個裝配站后，完成的汽車離開裝配線i的離開時間為x[i] 。

狀態轉移方程：

代碼實現：

//動態規劃，工廠裝配線 #include<iostream> using namespace std; //e1,e2是兩條裝配生產線的輸入耗費x1，x2是輸出耗費，a1[i]是第一條生產線的第i個站耗時，t1，t2記錄了兩條生產線轉換時耗時 //f1[i]為記錄第一條生產線上第i個站生產耗時最少時間，L1[i]記錄了第一條生產線上第i個站生產耗時最少時，前一站是那條生產線上的 //length為每條生產線上的站數 void FastWay(int e1,int e2,int *a1,int *a2,int x1,int x2,int *f1,int *f2,int *L1,int *L2,int &L,int *t1,int *t2,int length) { f1[1]=e1+a1[1]; f2[1]=e2+a2[1]; int i; for(i=2;i<length;i++) { if(f1[i-1]+a1[i]<f2[i-1]+a1[i]+t2[i-1]) { f1[i]=f1[i-1]+a1[i]; L1[i]=1; } else { f1[i]=f2[i-1]+a1[i]+t2[i-1]; L1[i]=2; } if(f2[i-1]+a2[i]<f1[i-1]+a2[i]+t1[i-1]) { f2[i]=f2[i-1]+a2[i]; L2[i]=2; } else { f2[i]=f1[i-1]+a2[i]+t1[i-1]; L2[i]=1; } } //利用f1[length]來存儲所用最短時間 if(f1[length-1]+x1<f2[length-1]+x2) { f1[length]=f1[length-1]+x1; L=1; } else { f1[length]=f2[length-1]+x2; L=2; } } //輸出最短時間以及所需要的路線 void Printanswser(int *L1,int *L2,int L,int length,int *f1) { int i=L; cout<<"the fast time is : "<<f1[length+1]<<endl; cout<<"the station : "<<length<<" is on line: "<<i<<endl; int j; for(j=length;j>=2;j--) { if(i==1) { i=L1[j]; } else { i=L2[j]; } cout<<"the station : "<<j-1<<" is on line: "<<i<<endl; } } int main() { int e1=2,e2=4,x1=3,x2=2; int a1[8]={0,7,9,3,4,8,4}; int a2[8]={0,8,5,6,4,5,7}; int t1[6]={0,2,3,1,3,4}; int t2[6]={0,2,1,2,2,1}; int f1[8],f2[7],L1[7],L2[7],L; FastWay(e1,e2,a1,a2,x1,x2,f1,f2,L1,L2,L,t1,t2,7); Printanswser(L1,L2,L,6,f1); return 0; }

運行結果：

參考：算法導論第十五章動態規劃--工廠裝配線c++代碼實現-http://blog.csdn.net/liuzhanchen1987/article/details/7831a723

轉載于:https://blog.51cto.com/8672742/1368369

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的动态规划-装配线调度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。