假设有 n 个任务由 k 个可并行工作的机器来完成。完成任务 i 需要时间为ti ,设计完成这 n 个任务的最佳调度算法,使得完成全部任务的时间最早。
时间: 2023-05-02 18:05:38 浏览: 193
题意:有n个任务由k台可并行工作的机器来完成。完成任务i需要时间ti,设计完成这n个任务的最佳调度算法,使得完成全部任务的时间最早。
回答:该题目属于传统的作业调度问题,可以使用贪心算法求解。具体做法为,将每个任务按照完成时间从小到大排序,然后依次分配到可用的机器中。每次选择最早空闲的机器,将当前任务分配给它。这种做法的正确性可以通过反证法证明。因此,使用这种方法可以得到所有任务完成所需的最短时间。
相关问题
假设有n(n<=20)个任务由k(k<=20)个可并行工作的机器完成。完成任务i需要的时间为t
假设有n个任务需要由k台可并行工作的机器来完成。每个任务完成所需的时间分别为t1, t2,…, tn。我们需要找到一个最优的分配方案,使得所有任务能够在最短的时间内完成。
首先,我们可以将任务分配给不同的机器,以减少总体完成时间。可以考虑使用贪心算法来解决这个问题。具体的分配方法可以是将任务按照所需的时间从长到短排序,然后依次分配给空闲的机器。
其次,我们还可以考虑使用动态规划来解决这个问题。具体的方法可以是用一个二维数组dp[i][j]来表示前i个任务分配给j台机器所需要的最短时间。然后使用状态转移方程来更新dp数组,最终找到最优的分配方案。
除此之外,我们还可以考虑使用回溯算法来解决这个问题。具体的方法可以是遍历所有可能的分配方案,然后找到最短的完成时间。
总的来说,解决这个问题的方法有很多种,可以根据具体的情况选择合适的算法来解决。而算法的选择也取决于任务数量n和机器数量k的大小,以及每个任务完成所需的时间t。希望能够找到一个最优的分配方案,使得所有任务能够在最短的时间内完成。
n个任务,k个可以并行工作的机器,完成任务i的时间是ti,求最佳调度时间
这个问题可以用贪心算法来解决。具体步骤如下:
1. 将所有任务按照完成时间从小到大排序,完成时间越小的任务先执行。
2. 初始化一个长度为k的列表,用来存放每台机器完成任务的时间。将列表中的元素全部初始化为0。
3. 依次将每个任务分配给完成时间最早的机器,即将该任务分配给列表中时间最小的机器,并更新该机器的完成时间。
4. 重复步骤3,直到所有任务都被分配完毕。
最终的最佳调度时间为所有机器完成时间的最大值。
这个算法的时间复杂度为O(nlogn),其中n为任务的数量,因为需要对任务进行排序。空间复杂度为O(k),其中k为机器的数量,即需要一个列表来存放每台机器的完成时间。