假设一个中央调度机,有n个相同的任务需要调度到m台服务器上去执行。每台服务器的配置不同,执行一个任务花费的时间也不相同。如:服务器a、b执行一个任务花费的时间分别为7min、10min,有6个任务等待调度,如果a、b各分3个任务,最短执行时间为30min;如果a分4个,b分2个,最短执行时间为28min。实现int estimate_process_time(int[] t, int m, int n),给出m台服务器执行n个任务的最短执行时间,t[i]表示第i台服务器执行一个任务花费的时间。

使用minLoad(a1, a2, ..., am)表示将(a1+a2+…+am)个任务调度到m台服务器上的最短执行时间,

1
2
3
4
5
6
7
8
(a1+a2+...+am)+ 1个任务的最短执行时间为:
min{
minLoad(a1+1, a2, ..., am),
minLoad(a1, a2+1, ..., am),
...,
minLoad(a1, a2, ..., am+1),
}

每次调度一个任务的时,先尝试分配任务(求min{…}),amount_try保存尝试分配时,每台服务器分得的任务量。比较执行时间,确定最终分得任务的服务器min

1
2
3
4
5
6
int[] amount_try = new int[m];
System.arraycopy(amount, 0, amount_try, 0, m);
for(int j = 0; j < m; j++)
amount_try[j]++;
int min = minLoad(t, amount_try);

调度一个任务时,分配结果总是使其能最快被执行完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class MaxLoad {
public static void main(String[] args) {
System.out.println(estimate_process_time(new int[] {5, 9}, 2, 10));
}
public static int estimate_process_time(int[] t, int m, int n) {
int[] load = new int[m];// 保存服务器执行完分得的任务花费的时间
int[] amount = new int[m];// 保存服务器分得的任务量
for(int i = 0; i < n; i++) {
int[] amount_try = new int[m];
System.arraycopy(amount, 0, amount_try, 0, m);
for(int j = 0; j < m; j++)
amount_try[j]++;
int min = minLoad(t, amount_try);
// 确定任务i分配给服务器min
load[min] += t[min];
amount[min]++;
}
int max = maxLoad(load);
return max;
}
// 返回array中最大的元素
public static int maxLoad(int[] array) {
int max = array[0];
for(int i = 1; i < array.length; i++)
if(array[i] > max)
max = array[i];
return max;
}
// t与amount元素对应相乘,返回乘积最小值的下标
public static int minLoad(int[] t, int[] amount) {
int min = 0;
int minLoad = t[0] * amount[0];
for(int i = 1; i < t.length; i++) {
int load = t[i] * amount[i];
if(load < minLoad) {
minLoad = load;
min = i;
}
}
return min;
}
}

程序的执行结果:

1
2
3
4
5
35
#任务分配情况:
server#1: 7
server#2: 3