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

这里给出一个使用优先队列式分支限界法求解最佳调度问题的算法：

1. 定义一个状态表示为 (ti1, ti2, ..., tik, depth, cost)，其中 ti1, ti2, ..., tik 表示 k 台机器的工作时间，depth 表示搜索树的深度，cost 表示当前状态完成全部任务的时间。

2. 将初始状态 (0, 0, ..., 0, 0, 0) 加入优先队列，其中 depth 和 cost 均为 0。

3. 循环执行以下步骤，直到找到最优解：

a. 从优先队列中取出一个状态，记为 S。

b. 如果 S 的深度等于 n，则更新最优解并继续取出下一个状态。

c. 对于每个任务 i，计算在 S 的基础上将任务 i 分配给机器 j 所得到的新状态 S'。具体地，如果第 j 台机器当前的工作时间为 t，则新状态为 (ti1, ti2, ..., ti(j-1), t+ti, ti(j+1), ..., tik, depth+1, max(cost, t+ti))。将所有新状态加入优先队列。

4. 得到最优解。

下面是使用 Python 实现的代码：

相关问题

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

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

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

假设有n（n<=20）个任务由k（k<=20）个可并行工作的机器完成。完成任务i需要的时间为ti。 试设计一个算法，对任意给定的整数n和k，以及完成任务i 需要的时间为ti ，i=1~n。计算完成这n个任务的最佳调度，使得完成全部任务的时间最早。

这是一个经典的作业调度问题，可以使用贪心算法来解决。

具体步骤如下：

1. 将任务按照完成时间从小到大排序。

2. 初始化k个机器的完成时间为0。

3. 对于每个任务，将其分配给完成时间最早的机器，并更新该机器的完成时间。

4. 重复步骤3，直到所有任务都被分配完毕。

5. 最终完成全部任务的时间即为k个机器中完成时间最大的值。

这个算法的时间复杂度为O(nlogn)，其中n为任务的数量。