假设有一个中央调度机,有n个相同的任务需要调度到m台服务器上去执行,由于每台服务器的配置不一样,因此服务器执行一个任务所花费的时间也不同。
现在假设第i个服务器执行 一个任务需要的时间为t[i].
例如:有2个执行机a,b,执行一个任务分别需要7min,10min,有6个任务待调度。如果平分这6个任务,即a,b各3个任务,则最短需要30min执行完所有。
如果a分4个任务 ,b分2个任务,则最短28min执行完。
解决思路:
用一个数组记录每台机器已执行的时间(初始为0),在调度每一个任务的时候,对每一台机器需要执行的时间进行对比(已执行的时间加上需要执行该任务的时间),
选取执行时间最短的机器进行处理.
程序设计:
程序结果:
与例子的描述结果是一致的。
四、贪心算法总结
从单线程和多线程角度分析问题,并且着重描述了多机调度的两种不同问题所采用的方法,需要慢慢去消化理解,但是总体的思路还是很清晰,这便是贪心算法的
一大优点。从上述的问题中,几乎所有的问题都要排序,就算没有直接排序,也还是会进行比较,以便做出当前最好的选择。