多机调度问题动态规划
时间: 2023-11-12 12:59:23 浏览: 89
调度中的动态规划问题
多机调度问题是指有n个任务需要在m台机器上完成,每个任务需要的时间不同,每台机器的处理速度也不同,如何安排任务才能使得所有任务完成的时间最短。这是一个经典的动态规划问题,可以使用贪心算法或者动态规划算法来解决。
具体来说,可以使用动态规划算法来解决多机调度问题。假设有n个任务和m台机器,令f[i][j]表示前i个任务分配给j台机器所需的最短时间。则有以下状态转移方程:
f[i][j] = min{max(f[k][j-1], sum[i]-sum[k])} (k<=i)
其中,sum[i]表示前i个任务的总时间。
最终的答案为f[n][m]。
阅读全文