问答题
5. 假设有一个中央调度机，有n个相同的任务需要调度到m台服务器上去执行，由于每台服务器的配置不一样，因此，服务器执行一个任务所花费的时间也不同。现在假设第i个服务器执行一个任务所花费的时间也不同。现在假设第i个服务器执行一个任务需要的时间为t[i]。例如：有2个执行机a与b，执行一个任务分别需要7min，10min，有6个任务待调度。如果平分这6个任务，即a与b各3个任务，则最短需要30min执行完所有。如果a分4个任务，b分2个任务，则最短28min执行完。请设计调度算法，使得所有任务完成所需要的时间最短。输入m台服务器，每台机器处理一个任务的时间为t[i]，完成n个任务，输出n个任务在m台服务器的分布：estimate_process_time(t,m,n)。
【正确答案】本题可以采用贪心法来解决，具体实现思路如下：
申请一个数组来记录每台机器的执行时间，初始化为0，在调度任务的时候，对于每个任务，在选取机器的时候采用如下的贪心策略：对于每台机器，计算机器已经分配任务的执行时间+这个任务需要的时间，选用最短时间的机器进行处理。实现代码如下：
"""
param t 每个服务器处理的时间
param n 任务的个数
return 各个服务器执行完任务所需的时间
"""
def calculate_rocess_time(t,n):
if t==None or n＜=0:
return None
m=len(t)
proTime=[0]*m
i=0
while i＜n:
minTime=proTime[0]+t[0] #把任务给第j个机器上后这个机器的执行时间
minIndex=0 #把任务给第minIndex个机器上
j=1
while j＜m:
# 分配到第j台机器上后执行时间更短
if minTime＞proTime[j]+t[j]:
minTime=proTime[j]+t[j]
minIndex=j
j+=1
proTime[minIndex]+=t[minIndex]
i+=1
return proTime
if __name__=="__main__":
t=[7,10]
n=6
proTime=calculate_process_time(t,n)
if proTime==None:
print "分配失败"
else:
totalTime=proTime[0]
i=0
while i＜len(proTime):
print "第"+str((i+1))+"台服务器有"+str(proTime[i]/t[i])+"个任务,执行总时间为:"+str(proTime[i])
if proTime[i]＞totalTime:
totalTime=proTime[i]
i+=1
print "执行完所有任务所需的时间为"+str(totalTime)
程序的运行结果为：
第1台服务器有4个任务，执行总时间为：28
第2台服务器有2个任务，执行总时间为：20
执行完所有任务所需的时间为28
算法性能分析：
这种方法使用了双重循环，因此，时间复杂度为O(mn)。
【答案解析】[考点] 如何对任务进行调度