1.假设有一个中央调度机,有n个相同的任务需要调度到m台服务器上去执行,由于每台服务器配置不一样,因此,服务器执行一个任务所花费的时间也不同,第i个服务器执行一个任务所花费的时间也不同。现在假设第i个服务器执行一个任务所需要的时间为t[i]。例如:有两个执行机a与b,执行一个任务分别需要7min,10min,有6个任务待调度,如果平分这6个任务,即a与b各三个任务,则最短需要30min执行完,如果a分4个任务,b分2个任务,则需要28min执行完。请设计一个调度算法,使得所有的任务完成所需要的时间最短。输入m台服务器,每台机器处理一个任务的时间为t[i],完成n个任务,输出n个任务在m台服务器上的分布
2.解析:可以使用贪婪法来解决,申请一个数组来记录每台机器执行时间,初始化为0,在调度任务的时候,对于每个任务,在选取机器的时候采用贪心策略,对于每台机器,计算机器已经分配任务的执行时间+这个任务需要的时间,选用最短时间的机器进行处理
3.代码如下:
def calculate_process_time(t,n):
"""
t 每个服务器处理的时间
n 任务的个数
return: 各个服务器执行完任务所需的时间
"""
if t == None or n <= 0:
return None
m = len(t)
proTime = [0] * m
i = 0
while i < n:
minTime = proTime[0] + t[0]
minIndex = 0
j = 1
while j < m:
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(f"第{i+1}台服务器有{proTime[i]/t[i]}个任务,执行总时间为:{proTime[i]}")
if proTime[i] > totalTime:
totalTime= proTime[i]
i += 1
print(f'执行完所需时间为:{totalTime}')
结果:
第1台服务器有4.0个任务,执行总时间为:28
第2台服务器有2.0个任务,执行总时间为:20
执行完所需时间为:28
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)