[算法思考]周期任务负载均衡

Mr吞灵-avatar

Mr吞灵

2022-05-17T12:29:31+00:00

某平台有x个周期任务,这些任务的周期分别是t1 t2 t3 t4 ... tx。每个任务执行的时间为l1 l2 l3 l4 ... lx。

现在可以决定每个任务的起始时间,如何能确保同时执行的任务数的最大值最小。(一种简化的情况是假设每个任务执行的时间都为0,如何确保同时开始的任务数的最大值最小)


不大清楚解决这种问题的算法的名称,不大好描述,来论坛问问有没有了解的。
yzmyyff-avatar

yzmyyff

背包问题?说实话没咋看懂题面,但感觉和背包比较像
Mr吞灵-avatar

Mr吞灵

举个例子:
我有10个周期任务,每个任务的周期都是5分钟,执行时间都是1秒,那么我只要让第一个任务在00分启动,第二个在00分01秒启动,第三个在00分02秒启动。。。。就能保证每个任务都错开,从而达到均衡的效果。


此时同时运行的任务最大数的就是最小的,也就是 1。

但假如我让每个任务都在00分启动,那么同时运行的任务的最大数就是最大的10。
Mr吞灵-avatar

Mr吞灵

Quote[pid=613006262,32033893,1]Reply[/pid] Post by [uid=363254]yzmyyff[/uid] (2022-05-24 20:33):

背包问题?说实话没咋看懂题面,但感觉和背包比较像
多谢老哥,以背包问题+时间为关键字,搜索到了类似的。大概是叫带权值区间调度问题
返回主页