生产调度问题及其优化算法
信息014 孙卓明
二零零三年八月十四日
生产调度问题及其优化算法
背景及摘要
这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含种排列。因为问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。
本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。
一．问题重述
某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工，其工序与加工周期如下表：
工序
产品 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 24 D 6
2 A 4 D 5 B 3 C 4
3 C 3 D 7 A 15 B 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
二．模型假设
1．每一时刻，每台机器只能加工一个工件，且每个工件只能被一台机器所加工 ，同时加工过程为不间断；
2．所有机器均同时开工，且工件从机器I 到机器J 的转移过程时间损耗不计；
3．各工件必须按工艺路线以指定的次序在机器上加工多次；
4．操作允许等待，即前一操作未完成，则后面的操作需要等待，可用资源有限。
三．符号说明及初始数据表达分析
- 第i个工件
- 机器顺序阵 表示i工件的第 j个操作的机器号
- 第j台机器
- 工件排列阵 表示i机器上第j次加工的工件号
- 加工时间阵为i工件的第 j个操作的时间周期
- 整个任务完成时间
整理数据后得到： =[ C A B C D 0 0 0 ] = [ 8 2 4 24 6 0 0 0 ]
[ A D B C 0 0 0 0 ] [ 4 5 3 4 0 0 0 0 ]
[ C D A B A 0 0 0 ] [ 3 7 15 20 8 0 0 0 ]
[ B C D A D C 0 0 ] [ 7 6 21 1 16 3 0 0 ]
[ D B C D A C D 0 ] [ 10 4 8 4 12 6 1 0 ]
[ A B A C D A C A ] [ 1 4 7 3 5 2 5 8 ] 上述二阵直接从题目得出，而则是我们要求的。
关于工件的加工时间表：(表二>
产品/工件
总净加工时间
加工工序总数
关于机器的加工时间表：(表三>
机器/设备(j>: A B C D 总计
总净加工时间 60 42 70 75 247
加工操作次数 10 6 10 9 35
分析：
因为各产品总净加工时间和各机器总净加工时间之中最大值为 75，而总计为247，那么 总时间 C 介于[75，247]。同时各工件加工繁杂程度不一，各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。 希望最优化答案是75，这样达到最小值，如果答案是75，那么意味着机器D不间断工作,直至全部加工任务完成。
四．贪婪法快速求解
如果按照一定规则排序，当多个工件出现“抢占”同一机器的局面的时候,我们可以制定如下的工序安排规则:
1.优先选择总剩余时间或总剩余操作较多的工件。
2.机器方面来说,尽量避免等待空闲时间，优先考虑剩余净加工时间或者剩余加工总次数较多的机器,尤其是机器D,即倘若能够使机器D不间断工作且其他机器完工时间均不多余75时,那么就可以得到最优解。
首先按照最优化时间为75的设想避免D出现等待，排序后得到升以下具体排列顺序。
各机器承担任务表为(其中粗体字为对应工件产品号，括号内为对应时间周期段>：
操作1 操作2 操作3 操作4 操作5 操作6 操作7 操作8 操作9 操作10
A 6
(1> 2
(2-5> 1
(12-13> 6
(14-20> 3
(21-35> 4
(36> 5
(43-54> 6
(55-56> 3
(57-64> 6
(66-73>
B 4
(1-7> 6
(8-11> 5
(12-15> 1
(16-19> 3
(36-55> 2
(56-58>
C 3
(1-3> 1
(4-11> 4
(12-17> 5
(18-25> 6
(26-28> 1
(29-52> 5
(55-60> 6
(61-65> 2
(66-69> 4
(70-72>
D 5
(1-10> 3
(11-17> 4
(18-38> 5
(39-42> 6
(43-47> 2
(48-52> 4
(53-68> 1
(69-74> 5
(75>
(表四>
103717844216448425375242015163166151242^^^^38801020304050607080D机器C机器B机器A机器^ (图一>
上图为加工周期图
五．计算机随机模拟
1．编码： 随机产生生产的工序操作优先顺序，进行编码，如：K=[ 4 35 6 6 2 3
1 4
1 6 3 5 4 53 6 6 4 1 5 5 1 3 2 6 2 2 4 4 1 5 6 6
5]
通过排列组合得出，总共有类似K的排列序列 2多种！
当然，这其中只对应解[75，247]，意味着有大量排列序列对应同一加工方案，而大量加工方案又对应同一时间解。
2．解码：
即对编码进行翻译，产生具体可操作工序安排方案，这里采用活动化解码算法。例如工件2第i步操作
<3,j）后，只要<2，i）在工件2已经排序好的操作之后进行，那么操 作<2，i）可插入到机器A处最前可安置的时间段进行。
在这里，一个编码序列对应一个加工方案，而一个加工方案可对应一个或多个编码序列，这就是二者之关系。
3．编程：
通过一组随机编码产生一生产加工优先序列，通过解码过程产生相应加工方案及其总耗费时间C .
N次模拟后即可得出解C的概率密度分布情况以及相对最优解
4．计算机模拟所得数据分析
a. 进行100次模拟得出最优解情况：(共运行10次>
82，83，82，84，78，80，81，83，87，82 平均值 82.2，每回耗时约3秒
b. 进行1000次模拟得出最优解情况：(共运行10次>
80，79，78，78，79，79，76，80，77，78 平均值 78.4 , 每回耗时25秒
c. 进行10000次模拟得出最优解情况：(共运行10次>
76，77，77，75，76，76，77，76，76，77 平均值 76.3, 每回耗时4分钟
d. 模拟1000000次得到的解C的概率密度分布情况为：
结论：如果想将2中排序序列以平均出现一次的可能性进行模拟，
即运行2次，计算机需运行将近150万亿年！当然，我们没有这个必要，因为我们只需要运行数万次，就很可能得到最优解75，
六．遗传算法模型建立和步骤解法
遗传算法
Algorithm）作为一种优化算法特别适合于对象模型难于建立、搜索空间非常庞大的复杂问题的优化求解。它和模糊控制技术一样，虽然在理论上还没有完善，但是在实践中已经得到了广泛的应用。遗传算法的基本思想是：模仿生物系统“适者生成"的原理，通过选择、复制、交叉、变异等简单操作的多次重复来达到去劣存优的目的，从而获得问题的优化结果。遗传算法的实现由两个部分组成，一是编码与解码，二是遗传操作。其中遗传操作又包括选择、复制、交叉、变异等步骤。
本文根据实际情况采取了1-6整数编码。数字1，2，3，4，5，6分别代表6件待加工产品。
本文遗传算法基本流程:
通过编码，解码程序随机产生N个
a) 从初始中群中选取2个具有最优染色体
b) 如果此2个体中有一个个体通过解码操作能够实现最优排序
c) 对2个临时个体以一定方式(循环交叉>执行染色体交叉变换和变异选择
d) 对父代和子代共4个个体进行选择，从中选出最佳的2个个体，做为下一代的父代；
e) 重复执行第二步(b>操作；
f) 如果执行完M步后仍然未得出答案75，那么将目前的最优解作为本算法的最优解答案。