【概述】

多机调度问题可表达为：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; }

 

总结

以上是生活随笔为你收集整理的基础算法 —— 调度问题 —— 多机并行调度问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。