【概述】

多機調度問題可表達為：n 個工件由 k 個可并行工作的機器加工，完成任務 i 需要的時間為 ti，調度目標是確定這 n 個工件完成的最佳加工順序，使得完成全部任務的時間最早，其可利用 回溯法 來求解

【問題分析】

問題實質是要從 n 個作業中找出有最小完成時間和的作業調度，因此批處理作業調度問題的解空間是一棵排列樹。

開始時，所給的 t[n] 為 n 個作業的完成時間，則相應的排列樹由 t[1:n] 的所有排列構成

用數組 len[n] 存儲一組空間解，getTime() 計算一個完整調度的完成時間，res 記錄當前最佳調度的完成時間

在進行搜索時，從第一個任務開始，對樹的深度進行遞歸：

• 當 deep=n 時，搜索至葉結點，得到一個新的作業調度方案，此時更新最優值與相應的最佳調度
• 當 deep<n 時，若當前擴展結點位于排列樹的第 n-1 層，說明需要對下一個要安排的作業進行搜索，并向第 n-2 層回溯，從而對相應子樹進行搜索

【實現】

int n,k; int t[N]; int len[N]; int res=INF; int getTime() {int temp=0;for(int i=0; i<k; i++)temp=max(len[i],temp);return temp; } void dfs(int deep) {if(deep==n) {int temp=getTime();res=min(res,temp);return;}for(int i=0; i<k; i++) {len[i]+=t[deep];if(len[i]<res)dfs(deep+1);len[i]-=t[deep];} } int main() {scanf("%d%d",&n,&k);for(int i=0; i<n; i++)scanf("%d",&t[i]);dfs(0);printf("%d\n",res);return 0; }

?

總結

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

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