贪心法之多机调度问题
问题描述：
设有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的处理时间为t[i]。 任何作业可以在任何一台机器上面加工处理，但未完工之前不允许中断处理。任何作业不能拆分成更小的作业。 要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
这个问题是NP完全问题，到目前为止还没有有效的解法(求最优解)，但是可以用贪心选择策略设计出较好的近似算法(求次优解)。
算法分析：
采用最长处理时间作业优先的贪心选择策略，可以设计出解多机调度问题较好的近似算法。
当n<=m(作业数小于机器数)时，只要将机器 i 的 时间区间分配给作业 i 即可；
当n>m时，首先将n个作业从大到小排序，然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中，选择需要处理时间最长的，然后依次选择处理时间次长的，直到所有的作业全部处理完毕，或者机器不能再处理其他作业为止。如果我们每次是将需要处理时间最短的作业分配给空闲的机器，那么可能就会出现其它所有作业都处理完了只剩所需时间最长的作业在处理的情况，这样势必效率较低。
假定有7个独立作业，所需处理时间分别为｛2，14，4，16，6，5，3｝，由三台机器M1,M2,M3加工。按照贪心算法产生的作业调度如下图所示，所需总加工时间为17.
代码实现：
#include<stdio.h> #define N 7 //作业数 #define M 3 //机器数 int s[M] = {0,0,0};//每台机器当前已分配的作业总耗时 //求出目前处理作业的时间和 最小的机器号 int min(int m) { int min = 0; int i; for(i=1;i<m;i++) { if(s[min] > s[i]) { min = i; } } return min; } //求最终结果（最长处理时间） int max(int s[],int num) { int max = s[0]; int i; for(i=1;i<num;i++) { if(max < s[i]) { max = s[i]; } } return max; } //机器数大于待分配作业数 int setwork1(int t[],int n) { int i; for(i=0;i<n;i++) { s[i] = t[i]; } int ma = max(s,N); return ma; } //机器数小于待分配作业数 int setwork2(int t[],int n) { int i; int mi = 0; for(i=0;i<n;i++) { mi = min(M); printf("第%d号作业,时间和最小的机器号为%d.时间和为%d：\n",i,mi,s[mi]); s[mi] = s[mi]+t[i]; } int ma = max(s,M); return ma; } int main(void) { int time[N] = {16,14,6,5,4,3,2};//处理时间按从大到小排序 int maxtime = 0; if(M >= N) { maxtime = setwork1(time,N); } else { maxtime = setwork2(time,N); } printf("最多耗费时间%d。",maxtime); }
View Code
运行结果：
时间复杂度分析：当n<=m时，算法所需O(1)时间
当n>m时，所需时间为O(nlogn)时间
参考文献：王晓东《算法设计与分析》第二版
版权声明：本文为cy0628原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。