多机调度问题 贪心算法

问题描述:设有n个独立的作业{1,2,…n},由m台相同的机器进行加工处理。作业i所需的处理时间为t; (t;为正整数)。约定每个作业均可在任何一台机器.上加工处理，但未完工前不允许中断处理，即作业不能拆分成更小的子作业。要求给出一种作业调度方案，使得所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

贪心选择策略:按处理时间从大到小的顺序将作业分配给空闲的机器。

个人感觉这个算法难点在于变量多

数组t[…n]: t[i]表示作业i所需的处理时间。

数组num[1…m]: num[j]表示第j台机器上处理的作业数。

数组M[1…m, …n]: M[j, 1…num[j]]表示第j台机器上处理的作业集。

数组fT1…m]: f[j]表示第j台机器被占用的时间。

输入:作业数n,机器数m,表示n个作业所需的处理时间的整数数组t[…n]。

输出:在m台机器上处理n个作业所需的近似最短时间mint,表示m台机器上分别处理的作业数的数组num[1…m],表示m台机器_上分别处理的作业集的数组M[1…m, 1…n]。

num[1..m]=0; f[1..m]=0 /初始化
/对t1..n]按降序地址排序，排序结果返回到数组a[ ..n]中,
//使得t[a[1]]>=f[a[2]>...>=t[a[]]。
a=sort(t, n)
for i=l to n
	j=min(f, m) //求f[..m]的最小值对应的下标。
	num[j]=num[j]+1 //在 第j台机器上安排作业a[i]
	M[j, num[]]=a[i]
	f[j]=f[j]+t[a[i]]
end for
mint=max(f, m) //求f[..m]的最大值。
return mint, num, M