作业排程问题

问题描述

Automobile factory with two assembly lines(汽车厂两条装配线)

– Each line has n stations: S1,1, . . . , S1,n and S2,1, . . . , S2,n(每条装

配线有n个工序站台)

– Corresponding stations S1, j and S2, j perform the same function

but can take different amounts of time a1, j and a2, j (每条装配线的

第j个站台的功能相同,但是效率不一致)

– Entry times e1 and e2 and exit times x1 and x2(上线和下线时间)

描述并实现动态规划的作业排程算法,并显示下图的排程结果。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
* OperationSequencing
* 作业排程算法实现
*/
/**
* int arrayA[2][5] = { 7,9,3,4,8,8,5,6,4,5 }; int arrayT[2][4] = {
* 2,3,1,3,2,1,2,2 };
*/
public class OperationSequencing {

public static List<Route> routes = new ArrayList<>();

public void addToRoutes(Node node, Integer costTime) {
boolean flag = false;

for (Route route : routes) {
if (route.getWorkIndex() == node.getWorkIndex() && costTime < route.getCostTime()) {
route.setLineIndex(node.getLineIndex());
route.setCostTime(costTime);
flag = true;
} else if (route.getWorkIndex() == node.getWorkIndex()) {
flag = true;
}
}
if (!flag) {
routes.add(new Route(node.getLineIndex(), node.getWorkIndex(), costTime));
}
}

public void printRoutes() {
Collections.sort(routes, new Comparator<Route>() {
@Override
public int compare(Route r1, Route r2) {
return r1.getWorkIndex() - r2.getWorkIndex();
}
});
System.out.print("enter-->");
for (Route route : routes) {
System.out.print("(" + route.getLineIndex() + "," + route.getWorkIndex() + ")-->");
}
System.out.print("exit");
}

public Integer getShortestTime(WorkingGraph workingGraph, Node endNode) {
WorkingGraph _workingGraph = new WorkingGraph(workingGraph);
if (endNode.getParents().size() == 1) {
return Edge.getEdgeWeight(_workingGraph.getEnterNode(), endNode, _workingGraph.getEdges())
+ endNode.getWorkTime();
}
Integer leftParentTime = Edge.getEdgeWeight(endNode.getParents().get(0), endNode, _workingGraph.getEdges());
Integer rightParentTime = Edge.getEdgeWeight(endNode.getParents().get(1), endNode, _workingGraph.getEdges());
// 去掉与末尾节点相关的边
Edge.removeEdgeWithNode(endNode, _workingGraph.getEdges());
_workingGraph.getNodes().remove(endNode);

Integer leftTime = getShortestTime(_workingGraph, endNode.getParents().get(0)) + leftParentTime;
Integer rightTime = getShortestTime(_workingGraph, endNode.getParents().get(1)) + rightParentTime;
addToRoutes(endNode.getParents().get(leftTime > rightTime ? 1 : 0),
leftTime > rightTime ? rightTime : leftTime);
return Math.min(leftTime, rightTime) + endNode.getWorkTime();
}

public static void main(String[] args) {
WorkingGraph workingGraph = new WorkingGraph();
// -1-1代表起始节点,-2-2代表离开节点
Node enter = new Node(-1, -1, 0);
Node exit = new Node(-2, -2, 0);

Node a11 = new Node(1, 1, 7);
Node a12 = new Node(1, 2, 9);
Node a13 = new Node(1, 3, 3);
Node a14 = new Node(1, 4, 4);
Node a15 = new Node(1, 5, 8);

Node a21 = new Node(2, 1, 8);
Node a22 = new Node(2, 2, 5);
Node a23 = new Node(2, 3, 6);
Node a24 = new Node(2, 4, 4);
Node a25 = new Node(2, 5, 5);

enter.addToChildren(a11);
enter.addToChildren(a21);

a11.addToParents(enter);
a11.addToChildren(a12);
a11.addToChildren(a22);

a21.addToParents(enter);
a21.addToChildren(a12);
a21.addToChildren(a22);

a12.addToParents(a11);
a12.addToParents(a21);
a12.addToChildren(a13);
a12.addToChildren(a23);

a22.addToParents(a11);
a22.addToParents(a21);
a22.addToChildren(a13);
a22.addToChildren(a23);

a13.addToParents(a12);
a13.addToParents(a22);
a13.addToChildren(a14);
a13.addToChildren(a24);

a23.addToParents(a12);
a23.addToParents(a22);
a23.addToChildren(a14);
a23.addToChildren(a24);

a14.addToParents(a13);
a14.addToParents(a23);
a14.addToChildren(a15);
a14.addToChildren(a25);

a24.addToParents(a13);
a24.addToParents(a23);
a24.addToChildren(a15);
a24.addToChildren(a25);

a15.addToParents(a14);
a15.addToParents(a24);
a15.addToChildren(exit);

a25.addToParents(a14);
a25.addToParents(a24);
a25.addToChildren(exit);

exit.addToParents(a15);
exit.addToParents(a25);

List<Node> nodes = new ArrayList<>();

nodes.add(enter);

nodes.add(a11);
nodes.add(a12);
nodes.add(a13);
nodes.add(a14);
nodes.add(a15);

nodes.add(a21);
nodes.add(a22);
nodes.add(a23);
nodes.add(a24);
nodes.add(a25);

nodes.add(exit);
List<Edge> edges = new ArrayList<>();

edges.add(new Edge(enter, a11, 2));
edges.add(new Edge(a11, a12, 0));
edges.add(new Edge(a12, a13, 0));
edges.add(new Edge(a13, a14, 0));
edges.add(new Edge(a14, a15, 0));
edges.add(new Edge(a15, exit, 3));

edges.add(new Edge(enter, a21, 4));
edges.add(new Edge(a21, a22, 0));
edges.add(new Edge(a22, a23, 0));
edges.add(new Edge(a23, a24, 0));
edges.add(new Edge(a24, a25, 0));
edges.add(new Edge(a25, exit, 6));

edges.add(new Edge(a11, a22, 2));
edges.add(new Edge(a21, a12, 2));
edges.add(new Edge(a12, a23, 3));
edges.add(new Edge(a22, a13, 1));
edges.add(new Edge(a13, a24, 1));
edges.add(new Edge(a23, a14, 2));
edges.add(new Edge(a14, a25, 3));
edges.add(new Edge(a24, a15, 2));

workingGraph.setNodes(nodes);
workingGraph.setEdges(edges);
workingGraph.setEnterNode(enter);
workingGraph.setExitNode(exit);

OperationSequencing operationSequencing = new OperationSequencing();
System.out.println(operationSequencing.getShortestTime(workingGraph, exit));
operationSequencing.printRoutes();
}

}

/**
* 图上的节点类
*/
class Node {
// 父节点
private List<Node> parents;
// 子节点
private List<Node> children;
// 流水线编号
private Integer lineIndex;
// 工作顺序编号
private Integer workIndex;
// 加工时间
private Integer workTime;

public Node() {

}

public Node(Integer lineIndex, Integer workIndex, Integer workTime) {
this.children = new ArrayList<>();
this.parents = new ArrayList<>();

this.lineIndex = lineIndex;
this.workIndex = workIndex;
this.workTime = workTime;
}

public List<Node> getParents() {
return parents;
}

public void setParents(List<Node> parents) {
this.parents = parents;
}

public void addToParents(Node parent) {
this.parents.add(parent);
}

public List<Node> getChildren() {
return children;
}

public void setChildren(List<Node> children) {
this.children = children;
}

public void addToChildren(Node child) {
this.children.add(child);
}

public Integer getLineIndex() {
return lineIndex;
}

public void setLineIndex(Integer lineIndex) {
this.lineIndex = lineIndex;
}

public Integer getWorkIndex() {
return workIndex;
}

public void setWorkIndex(Integer workIndex) {
this.workIndex = workIndex;
}

public Integer getWorkTime() {
return workTime;
}

public void setWorkTime(Integer workTime) {
this.workTime = workTime;
}

}

/**
* 边类
*/
class Edge {
// 起始节点
private Node startNode;
// 结束节点
private Node endNode;
// 边的权重
private Integer weight;

public Edge() {

}

public Edge(Node startNode, Node endNode, Integer weight) {
this.startNode = startNode;
this.endNode = endNode;
this.weight = weight;
}

/**
* 获取两个顶点之间的直线距离
*
* @param n1 起始节点
* @param n2 结束节点
* @param edges
* @return
*/
public static Integer getEdgeWeight(Node n1, Node n2, List<Edge> edges) {
for (Edge edge : edges) {
if (edge.getStartNode().equals(n1) && edge.getEndNode().equals(n2))
return edge.weight;
}
return 0;
}

/**
* 移除与指定节点相关的边
*
* @param Node
* @param edges
*/
public static void removeEdgeWithNode(Node Node, List<Edge> edges) {
List<Edge> _removeEdges = new ArrayList<>();
for (Edge edge : edges) {
if (edge.getStartNode().equals(Node) || edge.getEndNode().equals(Node)) {
_removeEdges.add(edge);
}
}
for (Edge edge : _removeEdges) {
edges.remove(edge);
}
}

public Node getStartNode() {
return startNode;
}

public void setStartNode(Node startNode) {
this.startNode = startNode;
}

public Node getEndNode() {
return endNode;
}

public void setEndNode(Node endNode) {
this.endNode = endNode;
}

public Integer getWeight() {
return weight;
}

public void setWeight(Integer weight) {
this.weight = weight;
}

}

class Route {
private Integer lineIndex;
private Integer workIndex;
private Integer costTime;

public Integer getLineIndex() {
return lineIndex;
}

public void setLineIndex(Integer lineIndex) {
this.lineIndex = lineIndex;
}

public Integer getWorkIndex() {
return workIndex;
}

public void setWorkIndex(Integer workIndex) {
this.workIndex = workIndex;
}

public Integer getCostTime() {
return costTime;
}

public void setCostTime(Integer costTime) {
this.costTime = costTime;
}

public Route(Integer lineIndex, Integer workIndex, Integer costTime) {
this.lineIndex = lineIndex;
this.workIndex = workIndex;
this.costTime = costTime;
}

}

/**
* 工作图类
*/
class WorkingGraph implements Cloneable {

private List<Node> nodes;

private List<Edge> edges;

private Node enterNode;

private Node exitNode;

public WorkingGraph() {

}

public WorkingGraph(WorkingGraph workingGraph) {
this.nodes = new ArrayList<>(workingGraph.getNodes());
this.edges = new ArrayList<>(workingGraph.getEdges());
this.enterNode = workingGraph.getEnterNode();
this.exitNode = workingGraph.getExitNode();
}

@Override
public WorkingGraph clone() {
WorkingGraph o = null;
try {
o = (WorkingGraph) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
return o;
}

public List<Node> getNodes() {
return nodes;
}

public void setNodes(List<Node> nodes) {
this.nodes = nodes;
}

public List<Edge> getEdges() {
return edges;
}

public void setEdges(List<Edge> edges) {
this.edges = edges;
}

public Node getEnterNode() {
return enterNode;
}

public void setEnterNode(Node enterNode) {
this.enterNode = enterNode;
}

public Node getExitNode() {
return exitNode;
}

public void setExitNode(Node exitNode) {
this.exitNode = exitNode;
}
}

实验分析

使用动态规划的思想,从上至下,从出口到入口。我这里还用了贪婪的策略,只需要保证每一次都是最短的工作耗时即可。

最长子序列问题

问题描述

描述并实现最长共同子序列动态规 划 算 法 , 并 显 示 S1= ACCGGTCGAGATGCAG,S2 = GTCGTTCGGAATGCAT *的最长共同子序列。 *

共同子序列可以是不连续的,且每个元素在母串中的位置也是可以不相同,但是顺序必须一致

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.util.ArrayList;
import java.util.List;

/**
* MaxSubsequence
*/
/**
* 描述并实现最长共同子序列动态规 划 算 法 , 并 显 示 S1= ACCGGTCGAGATGCAG,S2 = GTCGTTCGGAATGCAT
* 的最长共同子序列。 共同子序列可以是不连续的,且每个元素在母串中的位置也是可以不相同,但是顺序必须一致
*/
public class MaxSubsequence {

/**
* 求解最长子序列
*
* @param str1 字符串1
* @param str2 字符串2
* @return
*/
public static String lcs(String str1, String str2) {
int len1 = str1.length();
int len2 = str2.length();
StringBuffer sb = new StringBuffer();
int c[][] = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
for (int j = 0; j <= len2; j++) {
if (i == 0 || j == 0) {
c[i][j] = 0;
} else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
c[i][j] = c[i - 1][j - 1] + 1;
} else {
c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
}
}
}
for (int m = 0; m < Math.max(len1, len2); m++) {
for (int n = 0; n < Math.max(len1, len2); n++) {
System.out.print(c[m][n] + "\t");
}
System.out.println();
}
int m = len1;
int n = len2;
while (c[m][n] > 0) {
if (str1.charAt(m - 1) == str2.charAt(n - 1)) {
sb.append(str1.charAt(m - 1));
m--;
n--;
} else if (c[m][n] == c[m][n - 1]) {
n--;
} else if (c[m][n] == c[m - 1][n]) {
m--;
}
}
return sb.reverse().toString();
}

/**
* 生成最长子序列的字符串
*
* @param arr 比较矩阵
* @param str1 字符串1
* @param str2 字符串2
*/
public void generateLcs(int[][] arr, String str1, String str2) {
int m = arr.length - 1;
int n = arr[0].length - 1;
StringBuffer sb = new StringBuffer();
while (arr[m][n] > 0) {
if (str1.charAt(m) == str2.charAt(n)) {
sb.append(str1.charAt(m));
m--;
n--;
} else if (arr[m][n] == arr[m][n - 1]) {
n--;
} else if (arr[m][n] == arr[m - 1][n]) {
m--;
}
}
System.out.println(sb.reverse().toString());
}

public static void main(String[] args) {
MaxSubsequence maxSubsequence = new MaxSubsequence();
String ms = maxSubsequence.lcs("ACCGGTCGAGATGCAG", "GTCGTTCGGAATGCAT");
System.out.println(ms);
}
}

实验结果

生成的子序列矩阵

查找到的最长子序列

实验分析

实现最长子序列的关键在于创建最长子序列矩阵,这里是使用二维数组来实现的,每一个点都与其上方,左边,左上方这三个点相关,是在判断对应字符相等于否的基础上,根据这几个点来确定当前点的值。当到达最右下角的点时,也就是点dist[dist.length-1][dist.lenght-1]时,也就得到了最长共同子序列的长度,然后再使用逆向思维获取最终的序列。

并且最长子序列并不是唯一的,可能有多个值,这取决于你选择的打印方式。

思考题

  1. 动态规划算法范式是什么?

动态规划与分治法相似,但是动态规划所划分的子问题并不是完全相互独立的,是有可能相互关联的,如果使用分治法来实现就有可能重复处理子问题,造成资源浪费。

动态规划需要将问题分为子问题,前一个子问题为后一个子问题提供信息,并且每一次求解时需要存储之前的结果,以期得到最佳答案。

  1. 利用动态规划算法设计方法解决矩阵链相乘问题?

矩阵链相乘问题在于寻找最好的括号加法,对于$A_{i~j}(使用该符号来代表矩阵A_iA_{i+1}..*A_j的最佳值)$可以选取一个数k,其中$i≤k≤j$成立,并且kij中的最佳分割点,即括号的所在处,那么我们的乘法矩阵m[][]就可以表示为:

1
2
3
4
5
if(i==j){
m[i][i] = 0;
}else{
m[i][j]=min{m[i][k] + m[k+1][j] + Pi-1PkPj}
}

然后使用自底向上的思想就可以计算出最佳括号加法获得问题的解