实验要求
设有n个任务由k个可并行工作的机器来完成，完成任务i需要时间为ti。试设计一个算法找出完成这n个任务的最佳调度，使完成全部任务的时间最早。（要求给出调度方案）。
程序输入：从data.txt文件获取数据。
第一行为任务数n和机器个数k。
第二行为完成任务i需要的时间ti，包含n个数据，以空格间隔。
例如：
3 2
2.0 3.1 4.2
表示有3个任务，2个机器。完成3个任务的时间分别为2.0, 3.1, 4.2。
程序输出：
输出所有任务完成的总时间，及调度方案。
例如：
针对上述数据，耗费的总时间为5.1，调度方案为机器1(任务1，任务2)，机器2(任务3)。
目录
1.实验内容
2.实验目的
3.源码+注释
4.算法测试结果
5.实验过程中遇到的困难及收获
1.实验内容
设有n 个任务由k 个可并行工作的机器来完成，完成任务i 需要时间为ti 。试设计一个算法找出完成这n 个任务的最佳调度，使完成全部任务的时间最早。（要求给出调度方案）。
2.实验目的
1.掌握回溯算法的基本框架
2.利用回溯算法解决实际问题
3.源码+注释
定义MinimumTimeRequired 类，用来求解所需的最小工作时间和分配方案。MinimumTimeRequired 类有两个属性，res 用来保存最小的最长工作时间，allocation 用来保存工作分配方案，如下所示。
private double res = Double.MAX_VALUE;
private List[] allocation;
minimumTimeRequired 方法接收double 类型的数组jobs 和int 型变量k 。jobs[i] 代表第i 个工作完成所花费的时间；k 代表着机器总数目。
public void minimumTimeRequired(double[] jobs, int k)
方法中定义了一个大小为k 的List 数组allocationTemp 并初始化，用来保存当前的工作分配情况。然后调用backtrack 方法计算最短时间和工作分配方案。
backtrack 方法double 数组jobs 和worker ，整型变量i ，double 型变量max 和List 数组allocationTemp 。jobs[i] 代表第i 个工作完成所花费的时间，worker [j] 保存了第j 个机器已经分配的工作的总时间，max 保存当前最小的最长工作时间，allocationTemp 用来记录当前的分配方案。
private void backtrack(double[] jobs, int i, double[] worker, double max, List[] allocationTemp)
在该方法中，当i=jobs.length 即遍历完整个jobs 数组时，如果res>max 即已经保存的最短时间大于当前分配方案的最短时间，则更新res 和allocation ，否则直接返回。由于Java中赋值运算符对于非基本数据类型是赋地址值，因此不能采用allocation=allocationTemp 或allocation=allocationTemp.clone() 的方式更新allocation 。
//边界条件判断
if (i == jobs.length)
{
if (res > max)
{
res = Math.min(res, max);
allocation = new List[worker.length];
for (int j = 0; j < allocationTemp.length; j++)
{
allocation[j] = new ArrayList<>();
for (int num : allocationTemp[j])
{
allocation[j].add(num);
}
}
}
return;
}
对递归进行剪枝，遍历worker 数组的过程当中，如果发现worker[j]+jobs[i]>=res 即若将第i 个任务分配给第j 个机器后，第j 个机器的工作时间就会大于当前最优时间res 的话，则不进行该次分配，并且该条分配路径上的之后的分配行为都可以跳过，这样可以减少计算量。
for (int j = 0; j < worker.length; j++)
{
//如果时间已经超过之前找的尽可能小的最大工作时间，就跳过
if (worker[j] + jobs[i] >= res) continue;
//选择
worker[j] += jobs[i];
allocationTemp[j].add(i);
backtrack(jobs, i + 1, worker, Math.max(worker[j], max), allocationTemp);
//撤销选择
worker[j] -= jobs[i];
allocationTemp[j].remove((Integer) i);
}
4.算法测试结果
读取data.txt中的数据，输入程序中运行，得到的结果如下图所示。最长时间为12.4，然后列出了每个机器的分配任务情况。
5.实验过程中遇到的困难及收获
通过排列树回溯法的计算，可得到最优分配方案，但此问题的叶节点个数接近n! ，遍历时间为Ω(n!) ，呈阶乘级增长，效率不是很高。
本题目在输入的工作时长为整型的情况下可以做进一步优化：
1.可以使用二分查找来寻找最小的res值，下限为所有工作中的最大工作量，上限为所有工作的工作量之和。每一个工作都必须被分配，因此必然有一个工人承接了工作量最大的工作；在最坏情况下，只有一个工人，他必须承接所有工作。
2.优先分配工作量大的工作。感性地理解，如果要求将小石子和大石块放入玻璃瓶中，优先放入大石块更容易使得工作变得简单。在搜索过程中，优先分配工作量小的工作会使得工作量大的工作更有可能最后无法被分配。
6.实验源代码
MinimumTimeRequired.java
import java.util.ArrayList;
import java.util.List;
public class MinimumTimeRequired
{
private double res = Double.MAX_VALUE;
private List[] allocation;
public double getRes()
{
return res;
}
public List[] getAllocation()
{
return allocation;
}
public void minimumTimeRequired(double[] jobs, int k)
{
List[] allocationTemp = new List[k];
for (int i = 0; i < allocationTemp.length; i++)
{
allocationTemp[i] = new ArrayList<>();
}
backtrack(jobs, 0, new double[k], 0, allocationTemp);
}
private void backtrack(double[] jobs, int i, double[] worker, double max, List[] allocationTemp)
{
//边界条件判断
if (i == jobs.length)
{
if (res > max)
{
res = Math.min(res, max);
allocation = new List[worker.length];
for (int j = 0; j < allocationTemp.length; j++)
{
allocation[j] = new ArrayList<>();
for (int num : allocationTemp[j])
{
allocation[j].add(num);
}
}
}
return;
}
for (int j = 0; j < worker.length; j++)
{
//如果时间已经超过之前找的尽可能小的最大工作时间，就跳过
if (worker[j] + jobs[i] >= res) continue;
//选择
worker[j] += jobs[i];
allocationTemp[j].add(i);
backtrack(jobs, i + 1, worker, Math.max(worker[j], max), allocationTemp);
//撤销选择
worker[j] -= jobs[i];
allocationTemp[j].remove((Integer) i);
}
}
}
Test.java
import java.util.ArrayList;
import java.util.List;
public class MinimumTimeRequired
{
private double res = Double.MAX_VALUE;
private List[] allocation;
public double getRes()
{
return res;
}
public List[] getAllocation()
{
return allocation;
}
public void minimumTimeRequired(double[] jobs, int k)
{
List[] allocationTemp = new List[k];
for (int i = 0; i < allocationTemp.length; i++)
{
allocationTemp[i] = new ArrayList<>();
}
backtrack(jobs, 0, new double[k], 0, allocationTemp);
}
private void backtrack(double[] jobs, int i, double[] worker, double max, List[] allocationTemp)
{
//边界条件判断
if (i == jobs.length)
{
if (res > max)
{
res = Math.min(res, max);
allocation = new List[worker.length];
for (int j = 0; j < allocationTemp.length; j++)
{
allocation[j] = new ArrayList<>();
for (int num : allocationTemp[j])
{
allocation[j].add(num);
}
}
}
return;
}
for (int j = 0; j < worker.length; j++)
{
//如果时间已经超过之前找的尽可能小的最大工作时间，就跳过
if (worker[j] + jobs[i] >= res) continue;
//选择
worker[j] += jobs[i];
allocationTemp[j].add(i);
backtrack(jobs, i + 1, worker, Math.max(worker[j], max), allocationTemp);
//撤销选择
worker[j] -= jobs[i];
allocationTemp[j].remove((Integer) i);
}
}
}
