n个任务,k个可以并行工作的机器,完成任务i的时间是ti,求最佳调度时间

这个问题可以用贪心算法来解决。具体步骤如下：

1. 将所有任务按照完成时间从小到大排序，完成时间越小的任务先执行。
2. 初始化一个长度为k的列表，用来存放每台机器完成任务的时间。将列表中的元素全部初始化为0。
3. 依次将每个任务分配给完成时间最早的机器，即将该任务分配给列表中时间最小的机器，并更新该机器的完成时间。
4. 重复步骤3，直到所有任务都被分配完毕。

最终的最佳调度时间为所有机器完成时间的最大值。

这个算法的时间复杂度为O(nlogn)，其中n为任务的数量，因为需要对任务进行排序。空间复杂度为O(k)，其中k为机器的数量，即需要一个列表来存放每台机器的完成时间。

相关问题

假设有 n 个任务由 k 个可并行工作的机器来完成。完成任务 i 需要时间为ti ，设计完成这 n 个任务的最佳调度算法，使得完成全部任务的时间最早。

题意：有n个任务由k台可并行工作的机器来完成。完成任务i需要时间ti，设计完成这n个任务的最佳调度算法，使得完成全部任务的时间最早。

回答：该题目属于传统的作业调度问题，可以使用贪心算法求解。具体做法为，将每个任务按照完成时间从小到大排序，然后依次分配到可用的机器中。每次选择最早空闲的机器，将当前任务分配给它。这种做法的正确性可以通过反证法证明。因此，使用这种方法可以得到所有任务完成所需的最短时间。

最佳调度问题：假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti，i=1~n。试设计一个优先队列式分支限界法，计算完成这n个任务的最佳调度，使得完成全部任务的时间最早。例如，7个任务的完成时间分别为2、14、4、16、6、5、3，交给3个机器完成，则最早完成时间为17。

最佳调度问题可以使用优先队列式分支限界法解决，具体步骤如下：

1.将n个任务按照完成时间从大到小排序，建立一个优先队列。

2.初始化当前最小完成时间min_time为0，当前调度方案schedule为一个长度为n的空列表。

3.从优先队列中取出一个任务，将其分配给当前完成时间最早的机器，更新该机器的完成时间。将该任务加入到schedule列表中。

4.计算当前完成时间，如果大于等于min_time，则剪枝，回溯到上一步。否则，如果schedule列表已经包含了所有任务，则更新min_time为当前完成时间，记录当前调度方案。

5.对于每个未分配的任务，在当前机器完成时间最早的情况下计算该任务的完成时间，将该任务加入到优先队列中。

6.重复步骤3到5，直到优先队列为空。

7.返回记录的最优调度方案和完成时间。

下面是一个Python实现的例子：

import heapq

def best_schedule(n, t, k):
    # 将任务按完成时间从大到小排序
    tasks = sorted(range(n), key=lambda i: -t[i])
    # 初始化优先队列和当前完成时间
    q = [(0, [False] * n, [None] * n)]
    # 初始化最小完成时间和最优调度方案
    min_time, best_schedule = float('inf'), None
    while q:
        # 取出当前完成时间最小的调度方案
        time, used, schedule = heapq.heappop(q)
        if time >= min_time:
            # 剪枝，回溯到上一步
            continue
        if all(used):
            # 更新最小完成时间和最优调度方案
            min_time, best_schedule = time, schedule
            continue
        # 将未分配的任务加入优先队列
        for i in range(n):
            if not used[i]:
                # 计算任务i的完成时间
                m = min(range(k), key=lambda j: time + t[i] if schedule[j] is None else schedule[j])
                new_time = time + t[i] if schedule[m] is None else max(time + t[i], schedule[m])
                # 将任务i分配给机器m
                new_used = used.copy()
                new_used[i] = True
                new_schedule = schedule.copy()
                new_schedule[m] = new_time
                # 将新的调度方案加入优先队列
                heapq.heappush(q, (new_time, new_used, new_schedule))
    return min_time, best_schedule

# 测试
n = 7
t = [2, 14, 4, 16, 6, 5, 3]
k = 3
min_time, best_schedule = best_schedule(n, t, k)
print(f"最早完成时间为{min_time}，最优调度方案为{best_schedule}")

在上面的例子中，我们将任务按完成时间从大到小排序，并使用一个优先队列来存储所有可能的调度方案。每次从队列中取出当前完成时间最小的调度方案，将一个未分配的任务分配给当前完成时间最早的机器，并将新的调度方案加入到优先队列中。如果当前完成时间已经大于等于最小完成时间，则剪枝，回溯到上一步。如果所有任务都已经分配完成，则更新最小完成时间和最优调度方案。最终返回最早完成时间和最优调度方案。