【概述】

流水調度問題的表達為：有n 個作業在兩臺機器?M1、M2 組成的流水線上進行加工，每個作業 i 都必須花費 ai 在 M1 上行加工，然后再花費 bi 在 M2 上加工，確定 n 個作業的加工順序，使得 n 個作業完成加工的時間最短。

關于流水調度問題，可用 Johnson 法則來求最優調度方案，其時間復雜度為?O(nlogn)

算法描述為：設 N1 位 a<b 的作業集合，N2 為 a>=b 的作業集合，將 N1 的作業按 a 非減序排列，N2 中的作業按 b 非增序排列，則 N1 作業接 N2 作業構成最優順序。

【問題分析】

求一個加工順序使加工總時間最短，就是讓機器空閑時間最短，一旦機器 M1?開工，那么 M1?會不停的進行作業沒有空閑時間，而機器 M2 會有兩種情況：機器空閑、作業積壓，而且在第一個部件在機器 M1 開始加工時，機器 M2 必須等待，最后一個部件在機器 M2 加工時，機器 M1 也在等待機器 M2 的完工。

要使機器總空閑時間最短，就要將在機器 M1 上加工時間最短的部件先進行加工，這樣使得機器 M2 在最短的時間內可以開工，再把機器 M2 上加工時間最短的部件最后加工，這樣使得機器 M1 在最短的時間內等待機器 M2 完工。

根據 Johnson 法則，設：Mi=min{ai,bi}

將 M 按照從小到大的順序排序，然后從第一個開始處理：

• 若 Mi=ai，則：將第 i 個部件放在其從頭開始的加工的部件后面
• 若 Mi=bi，則：將第 i 個部件放在其從尾開始的加工的部件的前面

最后得到的序列即為最優加工順序。

例如：n=5，(a1,a2,a3,a4,a5)=(3,5,8,7,10)，(b1,b2,b3,b4,b5)=(6,2,1,4,9)

則 M=(m1,m2,m3,m4,m5)=(3,2,1,4,9)

將 M 進行排序，有：(m3,m2,m1,m4,m5)，然后進行處理

• 處理 m3：由于 m3=b3，因此 m3 放在后面，加工順序為：(? ,? ,? ,? ,3)
• 處理 m2：由于 m2=b2，因此 m2?放在后面，加工順序為：(? ,? ,? ,2,3)
• 處理 m1：由于 m1=a1，因此 m1?放在前面，加工順序為：(1,? ,? ,2,3)
• 處理 m4：由于 m4=b4，因此 m4?放在后面，加工順序為：(1,? ,4,2,3)
• 處理 m5：由于 m5=b5，因此 m5?放在后面，加工順序為：(1,5,4,2,3)

因此，最優的加工順序就是 (1,5,4,2,3)，最短時間為 34

【實現】

struct Node{int num;int id;bool operator < (const Node &rhs)const{return num<rhs.num;} }m[N]; int a[N],b[N]; int res[N]; int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&b[i]);//記錄mfor(int i=1;i<=n;i++){m[i].num=min(a[i],b[i]);m[i].id=i;}//對m進行排序sort(m+1,m+1+n);//對m進行處理int head=0,tail=n+1;for(int i=1;i<=n;i++){int num=m[i].num;int id=m[i].id;if(num==a[id])res[++head]=id;elseres[--tail]=id;}//計算最優時間int timeA=0,timeB=0;for(int i=1;i<=n;i++){timeA+=a[res[i]];if(timeB<timeA)timeB=timeA;timeB+=b[res[i]];}printf("%d\n",timeB);for(int i=1;i<=n;i++)printf("%d ",res[i]);printf("\n");return 0; }

?

總結

以上是生活随笔為你收集整理的基础算法 —— 调度问题 —— 流水调度问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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