生产调度问题及其优化算法.doc

生产调度问题及其优化算法.doc生产调度问题及其优化算法
＜采用遗传算法与 MATLAB编程）
信息014孙卓明
二零零三年八月十四日
生产调度问题及其优化算法
背景及摘要
这是一个典型的Job-
Shop动态排序问题。目前调度问题的理论研究成果主要集中在以 Job
Shop 冋题为代表的基于最小化完工时间的调度冋题上。一个复杂的制造系统不 仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的 调度规模。解空间容量巨大，N个工件、M台机器的问题包含凹 种排列。因 为问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法， 即便在单目标优化的静态调度问题中也难以有效应用。
本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编 解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发 展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用 MATLAB^件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较 显示出遗传算法之优化效果。对车间调度系列冋题的有效解决具有一定参考和 借鉴价值。
一•问题重述
某重型机械厂产品都是单件性的，其中有一车间共有 A，B，C，D四种不同设 备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工，其 工序与加工周期如下表：＜S-设备号、T-周期）
工序
产品
1
2
3
4
5
6
7
8
S
T
S
T
S
T
S
T
S
T
S
T
S
T
S
T
1
C
8
A
2
B
4
C 1
24
r d 1
6
2
A
4
D
5
B
3
C
4
3
C
3
D
7
A
15
B 1
20
:A :
8
4
B
7
C
6
D
21
A
1
D
16
C
3
5
D
10
B
4
C
8
D
4
:A :
12
C :
6
D
1
6
A
1
B
4
A
7
C
3
D
5
A
2
C
5
A
8
（表一 ＞
条件：1、每件产品必须按规定的工序加工，不得颠倒；
2每台设备在同一时间只能担任一项任务。
＜每件产品的每个工序为一个任务）
问题：做出生产安排，希望在尽可能短的时间里，完成所接受的全部任务。 要求：给出每台设备承担任务的时间表。
注：在上面，机器 A B，C，D即为机器1，2，3，4，程序中以数字1，2，3，4表示， 说明时则用A，B, C, D
二•模型假设
•每一时刻，每台机器只能加工一个工件，且每个工件只能被一台机器所加 工，同时加工过程为不间断；
2•所有机器均同时开工，且工件从机器I到机器J的转移过程时间损耗不 计；
•各工件必须按工艺路线以指定的次序在机器上加工多次；
•操作允许等待，即前一操作未完成，则后面的操作需要等待，可用资源有 限。
三•符号说明及初始数据表达分析
凶-
-
S- IrJ- 匡-
第i个工件＜i=1…6）
机器顺序阵 二一表示i工件的第j个操作的机器号
第j台机器＜j=1…4）
工件排列阵 上| ［表示i机器上第j次加工的工件号
加工时间阵—I为i工件的第j个操作的时间周期
-整个任务完成时间
整理数据后得到:
工=[C A B C D 0 0 0 ] ~[ A D B C 0 0 0 0 ]
[C D A B A 0 0 0 ]
[B C D A D C 0 0 ]
[D B C D A C D 0 ]
[A B A C D A C A ]
t = [ 8 2 4 24 6 0 0 0 ] [4 5 3 4 0 0 0 0 ]
[3 7 15 20 8 0 0 0 ]
[7 6 21 1 16 3 0 0]
[10 4 8 4 12 6 1 0]
[1 4 7 3 5 2 5 8 ]
上述二阵直接从题目得岀，而 丨则是我们要求的
关于工件的加工时间表：（表二＞
产品/工件＜i ）:
1
2
3
4
5
6
总计
-总净加工时间 ＜周期）
44
16
53
54
45
35
247
凶加工工序总数 ＜个）
5
4
5
6
7
8
35
关于机器的加工时间表：（表三＞
机器/设备（j＞：
A
B
C
D
总计
因总净加工时间
60
42
70
75
247
M加工操作次数
10
6
10
9