Machine Scheduling and Job Shop Scheduling 被认为是最难的组合优化问题之一，是复杂的设备制造系统和柔性制造系统领域中研究的重要课题，解决这个问题具有重要意义，因为即使提高一点求解效率也可能带来显著经济回报。JSP是NP-hard问题。JSP的高度复杂性使得它难以在大多数情况下用合理时间找到最优解。在前面的文章中，我们介绍了机器调度问题，给出了机器调度问题的数学模型，并调用cplex进行求解。但对于大规模机器调度问题来说，使用cplex求解可能需要花费大量的时间，而在实际生产生活当中无法满足时间的要求。于是，Egon Balas发明了Shifting bottleneck heuristic启发式算法来求解Job Shop问题。下面我们来介绍一下这个算法并用java给出算法代码。
顾名思义，转移瓶颈启发式算法中我们需要完成对瓶颈的转移，那么你现在可能会想什么是瓶颈呢？为什么将瓶颈转移了之后我们就可以解决问题呢？
首先我们回到机器调度问题的图的模型中来。还是用之前文章的问题，我们给出问题的图的模型：
我们先解决什么是瓶颈呢这一个问题:
先告诉大家，瓶颈就是每一台机器对应的最大拖延时间。那么什么是最大拖延时间呢？
首先我们需要引入释放时间(release time)和到期时间(due time)这两个概念。对于每一道工序，即图中的每一个顶点都存在一个释放时间和到期时间。释放时间也就是从执行第一道工序开始计时，一直到此工序开始加工的最长时刻。你可能会问什么叫做最长时刻呢？最长时刻就是指假设存在两条及以上从第一道工序（图中顶点U）到该顶点的路径，我们选择持续加工时间最长的一条路径。比如从图中的顶点U到顶点V，一共有三条路径，我们需要分别计算三条路径中所有边的权重之后，然后进行比较，权重之和最大的就是我们需要的最长路径。总结起来就是：发布时间（i，j）由图G中从源到节点（i，j）的最长路径决定。
如果你理解了释放时间，那么到期时间也就很好理解了。通过考虑图G中从节点（i，j）到顶点V的最长路径，再减去，可以计算出该工序（i，j）的截止时间。
对于每一台机器，我们引入最大拖延时间这个概念。我们会求出每一台机器的最大拖延时间，让后将这台机器所确定的各个工件的加工顺序（也就是图中的析取弧或者是虚线边）添加至图中。对于每一台机器，它的最大拖延时间就是机器加工的最后一道工序的完工时间减去该工序的到期时间。然后将不同的机器所对应的最大拖延时间进行比较，最大拖延时间所对应的机器就是我们所要的。
那么为什么选择最大拖延时间呢？
对于每一台机器我们需要确定机器内部各个工序的加工顺序，那么怎么去安排各个机器内部的各个加工工序呢？这其实是一个单机调度问题。我们在这个问题中求解单机调度问题的做法是先计算出每一台机器due time,然后我们将各个工序的due time 从小到大进行排序，该顺序就是机器内部加工工件的各个工序的先后顺序。按照给定的顺序，我们将计算出最大完工时间，将最大完工时间减去最后一道工序对应的due time，即可计算出机器对应的最大拖延时间。
在解决了所有这些单机问题后，选择具有最大最大延迟的机器。在剩下的机器中，这台机器在某种意义上是最关键的或“瓶颈”，因此是
中要包含的下一个机器。假设这是机器h，调用其最大延迟
，并根据与该机器相关的单机问题获得的最优解对其进行调度。如果在机器h上指定操作顺序的分离弧被插入到图G中，那么当前部分调度的最长时间至少增加了
，即
那么等号什么时候取到呢？就是当添加进来的析取弧正好都包含在从第一道工序一直到最后一道工序最长路径之中，这样完工时刻的增加值最小，在其他情况下，完工时间的增加值都大于这种情况。
我们新建一个txt文本文件，按照如下方式输入数据。其中第一行输入工件的数量（为方便一般性描述，我们设为a），第二行输入机器的数量，随后的a行数据输入的是每一个工件的工序，即各个工件分别在哪一台机器上进行加工，最后的a行数据表示每道工序的加工时间（process time）。
我们需要在eclipse中读取数据：
public class ReaderData {
public Graph readerData(String path) throws IOException {
//创建图对象
Graph graph = new Graph();
//定义按照工件划分的点集合
List<List<Vertex>> workpieceSet = new ArrayList<>();
//path位置填写txt文件的绝对路径
BufferedReader in = new BufferedReader(new FileReader(path));
//读取工件的数量
String str1 = null;
str1 = in.readLine();
String[] st1 = str1.split(":");
int numberOfWorkpieces = Integer.parseInt(st1[1]);
System.out.println(numberOfWorkpieces);
//读取机器的数量
String str2 = null;
str2 = in.readLine();
String[] st2 = str2.split(":");
int numberOfMachines = Integer.parseInt(st2[1]);
System.out.println(numberOfMachines);
//定义按工件划分的工序集合
for(int i = 0; i < numberOfWorkpieces; i++) {
List<Vertex> workpiece = new ArrayList<>();
workpieceSet.add(workpiece);
}
//定义按机器划分的工序集合
for(int i = 0; i < numberOfMachines; i++) {
List<Vertex> machine = new ArrayList<>();
graph.VertexOfMachine.add(machine);
}
//输入每个工件的工序，即输入工件在各个工序上加工的机器
for(int i = 1; i <= numberOfWorkpieces; i++) {
System.out.println("正在读取第"+i+"个工件的流程");
String str3 = in.readLine();
String[] arrProcess = str3.split(",");
int num = arrProcess.length;
for(int j = 0; j < num; j++) {
Vertex v = new Vertex();
int a = Integer.parseInt(arrProcess[j]);
graph.AllVertex.add(v);
workpieceSet.get(i-1).add(v);
graph.VertexOfMachine.get(a-1).add(v);
}
}
//读取每个工序的加工时间
for(int i = 1; i <= numberOfWorkpieces; i++) {
System.out.println("正在读取第"+i+"个工件的各个加工工序的加工时间");
String str4 = in.readLine();
String[] arrProcessTime = str4.split(",");
int num = arrProcessTime.length;
for(int j = 0; j < num; j++) {
int a = Integer.parseInt(arrProcessTime[j]);
workpieceSet.get(i-1).get(j).processedTime = a;
}
}
//定义合取弧（图中的实线边）
for(List<Vertex> list : workpieceSet) {
for(int i = 0; i < list.size()-1; i++) {
Edge e = new Edge();
e.tail = list.get(i);
e.head = list.get(i+1);
graph.AllEdges.add(e);
}
}
//向所有的边添加权重
for(Edge e : graph.AllEdges) {
e.weight = e.tail.processedTime;
}
//定义虚拟开始顶点流出边
for(List<Vertex> list : workpieceSet) {
Edge e = new Edge();
e.tail = graph.source;
e.head = list.get(0);
graph.AllEdges.add(e);
}
//定义虚拟结束顶点流入边
for(List<Vertex> list : workpieceSet) {
int num = list.size();
Edge e = new Edge();
e.tail = list.get(num-1);
e.head = graph.sink;
graph.AllEdges.add(e);
}
//定义各个顶点的流入和流出弧集合
for(Vertex v : graph.AllVertex) {
for(Edge e : graph.AllEdges) {
if(e.head == v) {
v.flowInEdges.add(e);
}
if(e.tail == v) {
v.flowOutEdges.add(e);
}
}
}
//向图中添加虚拟开始顶点和虚拟结束顶点
graph.AllVertex.add(graph.source);
graph.AllVertex.add(graph.sink);
//定义虚拟开始顶点的加工时间为0
graph.source.processedTime = 0;
//关闭文件
in.close();
return graph;
}
}
读取数据之后，我们需要计算出每道工序对应的release time和due time。因为release time和due time都需要计算图中的最长路径，因此，我们先介绍一下求解图中最长路径问题的算法。我们采用遍历的算法，找到开始顶点到图中各个顶点的所有路径，当某一个顶点的流入弧集合的所有边都被选中时，我们便可确定出该顶点的最长路径。我们给出最长路径的代码。
public class Vertex {
public int machine;
public int workpiece;
public List<Edge> flowOutEdges = new ArrayList<>();
public List<Edge> flowInEdges = new ArrayList<>();
public int processedTime;
public int dueTime;
public int releaseTime;
public int antireleaseTime;//反向释放时间，用于求dueTime时使用
//方法：计算各个顶点的释放时间
public int CalculateRealeaseTime(Graph graph,Vertex vertex) {
//定义永久点和临时点的集合
List<Vertex> Permanent = new ArrayList<>();
List<Vertex> Temporary = new ArrayList<>();
//将初始顶点添加至永久集合当中
Permanent.add(graph.source);
//将所有的顶点（除虚拟开始顶点之外）都添加至临时集合当中
for(Vertex v : graph.AllVertex) {
Temporary.add(v);
}
Temporary.remove(graph.source);
/*迭代规则：
临时顶点集合中的某个顶点的所有流入边的尾顶点都在永久集合当中时，
将该顶点从临时顶点集合中移动到永久顶点集合。
*/
while(!Temporary.isEmpty()) {
Vertex vtx = null;
for(Vertex v : Temporary) {
int sum = 0;
for(int i = 0 ; i < v.flowInEdges.size(); i++) {
if(Temporary.contains(v.flowInEdges.get(i).tail)) {
sum += 1;
}
}
if(sum == 0) {
vtx = v;
List<Integer> ReleaseTime = new ArrayList<>();//定义释放时间集合
for(Edge e : v.flowInEdges) {
int value = e.weight + e.tail.releaseTime;
ReleaseTime.add(value);
}
int max = ReleaseTime.get(0);
for(int a : ReleaseTime) {
if(a > max) {
max = a;
}
}
v.releaseTime = max;
}
}
Permanent.add(vtx);
Temporary.remove(vtx);
}
return vertex.releaseTime;
}
//方法：计算各个顶点的截至时间
public int CalculatDueTime(Graph graph,Vertex vertex) {
//定义永久点和临时点的集合
List<Vertex> Permanent = new ArrayList<>();
List<Vertex> Temporary = new ArrayList<>();
//将尾顶点添加至永久集合当中
Permanent.add(graph.sink);
//将所有的顶点（除尾顶点之外）添加至临时集合当中
for(Vertex v : graph.AllVertex) {
Temporary.add(v);
}
Temporary.remove(graph.sink);
/*迭代规则:
当某个临时顶点流所有流出边的头顶点都被在永久集合当中时，
将该顶点从临时顶点集合中移动至永久顶点集合
*/
while(!Temporary.isEmpty()) {
Vertex vtx = null;
for(Vertex v : Temporary) {
int sum = 0;
for(int i = 0 ; i < v.flowOutEdges.size(); i++) {
if(Temporary.contains(v.flowOutEdges.get(i).head)) {
sum += 1;
}
}
//System.out.println(sum);
if(sum == 0) {
vtx = v;
List<Integer> antiReleaseTime = new ArrayList<>();//定义反向释放时间集合
for(Edge e : v.flowOutEdges) {
int value = e.weight + e.head.antireleaseTime;
antiReleaseTime.add(value);
}
v.antireleaseTime = Collections.max(antiReleaseTime);
v.dueTime = graph.sink.releaseTime-v.antireleaseTime+v.processedTime;
//v.dueTime = graph.sink.releaseTime-v.antireleaseTime+v.processedTime;//取出释放时间集合当中最大的元素
}
}
//System.out.println("现在正在移动第"+vtx+"个顶点");
Permanent.add(vtx);
Temporary.remove(vtx);
//System.out.println(vtx.dueTime);
}
return vertex.dueTime;
}
}
在求出release time和due time之后，我们就可以计算出每一台机器的lateness time，选取最大lateness time对应的机器，将其对应的析取弧添加至图中，就可以更新图。此时，我们可以更新最大完工时间：
备注一下，这里的“=”是将等号右边的值赋值给等号左边的值，并不是表示两个值相等。
根据更新后的图，我们再次计算出更新后的各道工序对应的release time和due time，从而计算出各个机器对应的最大lateness time。我们再次选出最大lateness time对应的机器，将其析取弧添加至图中，再次完成对图的更新。依次迭代下去，直到所有的机器对应的析取弧都添加至图中，算法执行完毕。
我们给出转移瓶颈启发式算法进行迭代的代码：
public class Algorithm {
public static void main(String[] args) throws IOException {
ReaderData rd = new ReaderData();
Graph graph = rd.readerData("D:\\其他文件\\数据1.txt");
List<List<Vertex>> M = new ArrayList<>();
List<List<Vertex>> M0 = new ArrayList<>();
for(List<Vertex> list : graph.VertexOfMachine) {
M.add(list);
}
/*迭代规则：对于每一台机器所对应的顶点集合，求出它们的最大拖延时间，
(注：若有两个及以上相同的最大拖延时间，取下标最小的机器)
取出最大释放时间对应的机器并添加各个机器内部的析取弧，将确定的析取弧添加至图中。
此时，更新最大完工时间Cmax = Cmax + Lmax;
重复上述步骤，直到所有的机器内部析取弧都被确定。
*/
int Cmax = graph.sink.CalculateRealeaseTime(graph, graph.sink);//定义最大完工时间
System.out.println("初始的最大完工时间为："+Cmax);
while(!M.isEmpty()) {
List<Integer> latenessTimeSet = new ArrayList<>();
List<List<Vertex>> SequenceSet = new ArrayList<>();
graph.sink.releaseTime = graph.sink.CalculateRealeaseTime(graph, graph.sink);
for(List<Vertex> list : M) {
List<Vertex> sequence = new ArrayList<>();
List<Vertex> workpiece = new ArrayList<>();
for(Vertex v : list) {
workpiece.add(v);
}
for(int i = 0; i < list.size(); i++) {
list.get(i).dueTime = list.get(i).CalculatDueTime(graph, list.get(i))+Cmax-graph.sink.releaseTime;
list.get(i).releaseTime = list.get(i).CalculateRealeaseTime(graph, list.get(i));
}
int time = 0;
while(!(sequence.size() == list.size())) {
List<Integer> DueTimeSet = new ArrayList<>();
for(Vertex v : workpiece) {
DueTimeSet.add(v.dueTime);
}
int dmin = 100;
for(int i = 0 ; i < DueTimeSet.size(); i++) {
if(DueTimeSet.get(i) <= dmin) {
dmin = DueTimeSet.get(i);
}
}
for(int i = 0; i < workpiece.size(); i++) {
if(DueTimeSet.get(i) == dmin) {
sequence.add(workpiece.get(i));
DueTimeSet.remove(i);
time = time + workpiece.get(i).processedTime;
workpiece.remove(i);
}
}
int subdmin = 100;
for(int j = 0 ; j < DueTimeSet.size(); j++) {
if(DueTimeSet.get(j) <= subdmin) {
subdmin = DueTimeSet.get(j);
}
}
for(int i = 0; i < DueTimeSet.size(); i++) {
if(DueTimeSet.get(i) == subdmin) {
if(time < workpiece.get(i).releaseTime) {
time = workpiece.get(i).releaseTime;
}
break;
}
}
}
SequenceSet.add(sequence);
int latenessTime = time - sequence.get(sequence.size()-1).dueTime;//计算出该机器的拖延时间
if(latenessTime < 0) {
latenessTime = 0;
}
latenessTimeSet.add(latenessTime);
}
System.out.println(latenessTimeSet);
int Lmax = Collections.max(latenessTimeSet);//找到最大拖延时间对应的机器
System.out.println("最大拖延时间是："+Lmax);
Cmax += Lmax;//更新最大完工时刻
System.out.println("迭代后的最大完工时间为："+Cmax);
for(int i = 0; i < latenessTimeSet.size(); i++) {
if(latenessTimeSet.get(i) == Lmax) {
//将被选择的机器从M移动到M0
M.remove(i);
M0.add(graph.VertexOfMachine.get(i));
for(int j = 0; j < SequenceSet.get(i).size()-1; j++) {
Edge e = new Edge();
e.tail = SequenceSet.get(i).get(j);
e.head = SequenceSet.get(i).get(j+1);
e.weight = e.tail.processedTime;
SequenceSet.get(i).get(j+1).flowInEdges.add(e);
SequenceSet.get(i).get(j).flowOutEdges.add(e);
graph.AllEdges.add(e);
}
break;
}
}
}
}
}代码运行结果如下：
大量的数据实验研究表明，转移瓶颈启发式算法对于提高求解机器调度问题的效率是非常有效的。对于有10台机器和10个工件的问题，曾经花了20年都没有解决，而转移瓶颈启发式算法很快就找到了一个可行解。在使用分支定界过程得到相同的结果并验证了其最优性后，启发式方法所求的解实际上是最优的。同时，与启发式方法相比，分支和绑定方法需要很多小时的CPU时间。
但启发式算法也存在一些不足之处，比如我们不是每次都可以找到最优解，它只能给出一个可行解。