有m台相同的机器，需要处理n个独立的作业，作业i所需的处理时间为t[i]。 每个作业都可以在任何一台机器上加工处理，但未完工之前不允许中断处理。任何作业不能拆分成更小的作业。 如何对作业进行调度，使得所给的n个作业由m台机器在尽可能短的时间内加工处理完成。
二、解题思路使用贪心算法求解多机调度问题，其策略是耗时最长的作业优先，把“处理时间最长的作业”分配给“最先空闲的机器”，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。按照“耗时最长的作业优先处理”的策略：
当机器数m>=作业数n时，只要将机器 i 的[0，t[i]]时间区间分配给作业 i 即可。这种情况下，耗时最长的作业的处理时间就是所求的最短时间。
当机器数m<作业数n时，按照如下步骤处理：
第1步：将n个作业按其所需处理时间从大到小降序排列；
第2步：将m个机器按照工作时长从小到大升序排列；
第3步：将“耗时最长的作业”分配给“最先空闲的机器”，增加该机器的工作时长。
重复第二步和第三步，直到所有作业都被处理。这种情况下，累加耗时最长的机器的工作时长就是所求的最短时间。
三、Java编码实现根据上一节的算法步骤，我们很容易就能编程解决多机作业调度问题。
具体实现如下：
package com.test.algorithm.multimachinealgothrim;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
public class MultiMachineSchedule {
public static int greedy(int[] a, int m) {
int n = a.length;
int total = 0;
if (n <= m) {
for (int i = 0; i < n; i++) {
if (total < a[i]) {
total = a[i];
}
}
System.out.println("为每个作业分别分配一台机器");
return total;
}
List jobNodes = new ArrayList<>(); // jobNodes保存所有的作业
for (int i = 0; i < n; i++) { // 将所有的作业存入List中，每一项包含标号和时间
JobNode jb = new JobNode(i + 1, a[i]);
jobNodes.add(jb);
}
Collections.sort(jobNodes); // 按照作业时长降序排列
// jobNodes.forEach(jobNode -> System.out.println(jobNode.id + " : " + jobNode.time));
LinkedList machineNodes = new LinkedList<>(); // machineNodes保存所有的机器
for (int i = 0; i < m; i++) { // 将所有的机器存入LinkedList中
MachineNode x = new MachineNode(i + 1, 0); // 初始时，每台机器的空闲时间（完成上一个作业的时间）都为0
machineNodes.add(x);
}
for (int i = 0; i < n; i++) {
Collections.sort(machineNodes); // 按照机器工作时长升序排列
// machineNodes.forEach(machineNode -> System.out.println(machineNode.id + " : " + machineNode.avail));
MachineNode machineNode = machineNodes.peek(); // 取出工作时长最小的机器节点
System.out.println(
"机器: " + machineNode.id +
", 时段: " + machineNode.avail + "到" + (machineNode.avail + jobNodes.get(i).time) +
", 分配作业: " + jobNodes.get(i).id +
", 作业时长: " + jobNodes.get(i).time
);
machineNode.avail += jobNodes.get(i).time;
}
Collections.sort(machineNodes); // 按照机器工作时长升序排列
MachineNode machineNode = machineNodes.peekLast(); // 取出工作时长最大的机器节点
if (Objects.nonNull(machineNode)) {
total = machineNode.avail;
}
return total;
}
public static class JobNode implements Comparable {
int id; // 作业标号
int time; // 作业时长
public JobNode(int id, int time) {
this.id = id;
this.time = time;
}
@Override
public int compareTo(Object x) { // 按作业时长降序排列
int times = ((JobNode) x).time;
return Integer.compare(times, time);
}
}
public static class MachineNode implements Comparable {
int id; // 机器标号
int avail; // 机器工作时长
public MachineNode(int id, int avail) {
this.id = id;
this.avail = avail;
}
@Override
public int compareTo(Object o) { // 按照工作时长升序排列，LinkedList的first为最小的
int xs = ((MachineNode) o).avail;
return Integer.compare(avail, xs);
}
}
public static void main(String[] args) {
// 作业耗时列表
int[] a = {5, 4, 2, 14, 16, 6, 5, 3};
// int[] a = {5, 4, 2};
// 机器个数
int m = 3;
int total = MultiMachineSchedule.greedy(a, m);
System.out.println("总时间为：" + total);
}
}
运行结果为：
机器: 1, 时段: 0到16, 分配作业: 5, 作业时长: 16 机器: 2, 时段: 0到14, 分配作业: 4, 作业时长: 14 机器: 3, 时段: 0到6, 分配作业: 6, 作业时长: 6 机器: 3, 时段: 6到11, 分配作业: 1, 作业时长: 5 机器: 3, 时段: 11到16, 分配作业: 7, 作业时长: 5 机器: 2, 时段: 14到18, 分配作业: 2, 作业时长: 4 机器: 3, 时段: 16到19, 分配作业: 8, 作业时长: 3 机器: 1, 时段: 16到18, 分配作业: 3, 作业时长: 2 总时间为：19
