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

: .
生产调度问题及其优化算法
〈采用遗传算法与MATLAB编程）
信息014
孙卓明
二零零三产品总净加工时间和各机器总净加工时间之中最大值为75,而总计为247,那么总时间C介于［75,247］。同时各工件加工繁杂程度不一，各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。
希望最优化答案是75，这样达到最小值，如果答案是75,那么意味着机器D不间断工作,直至全部加工任务完成。
四．贪婪法快速求解
如果按照一定规则排序，当多个工件出现“抢占”同一机器的局面的时候,我们可以制定如下的工序安排规则:
优先选择总剩余时间或总剩余操作较多的工件。＜如果出现总剩余加工时间多者总剩余操作数反而较少的情况时,按照程度具体情况具体分析）。
机器方面来说,尽量避免等待空闲时间，优先考虑剩余净加工时间或者剩余加工总次数较多的机器，尤其是机器D,即倘若能够使机器D不间断工作且其他机器完工时间均不多余75时,那么就可以得到最优解。
首先按照最优化时间为75的设想避免D出现等待，排序后得到升以下具体排列顺序。
各机器承担任务表为（其中粗体字为对应工件产品号，括号内为对应时间周期段＞：
操作1
操作2
操作3
操作4
操作5
操作6
操作7
操作8
操作9
操作10
A
6
2
1
6
3
4
5
6
3
6
(1>
(2-5>
(12-13>
(14-20>
(21-35>
(36>
(43-54>
(55-56>
(57-64>
(66-73>
B
4
6
5
1
3
2
(1-7>
(8-11>
(12-15>
(16-19>
(36-55>
(56-58>
C
3
1
4
5
6
1
5
6
2
4
(1-3>
(4-11>
(12-17>
(18-25>
(26-28>
(29-52>
(55-60>
(61-65>
(66-69>
(70-72>
D
5
3
4
5
6
2
4
1
5
(1-10>
(11-17>
(18-38>
(39-42>
(43-47>
(48-52>
(53-68>
(69-74>
(75>
（表四〉
A机器
B机器
14入
27
15
1A122
8•8
74
44
A
20
3
C机器
3
8
6
8
3
24
A
6
5
4
3
D机器
10
7
21
4
5
5
16
6
1
1111111
01020304050607080（图一＞
上图为加工周期图＜甘特图），标注数字为相应操作的周期，完工时间为第75周期。
五．计算机随机模拟＜编程）1．编码：随机产生生产的工序操作优先顺序，进行编码，如：K=[435662341635453664155132622441566
5]＜注：同时作为下文的染色体之用）意思为：工件4优先被考虑进行第一次操作，然后3进行其第一步操作，然后5操作，6操作，再6操作其第二步工序，依次进行。如果前后互相不冲突，则可同时在不同机器上操作。
通过排列组合得出，总共有类似K的排列序列2多种！
当然，这其中只对应解[75,247]，意味着有大量排列序列对应同一加工方案，而大量加工方案又对应同一时间解。
1 •解码：
即对编码进行翻译，产生具体可操作工序安排方案，这里采用活动化解码算法。例如工件2第i步操作＜记为—＜2,i），且在机器A上进行）被安排在工件3第j步操作＜记为JMv3,j））后面进行，那么如果安排好v3,j）后，只要_＜2,i）在工件2已经排序好的操作之后进行，那么操作口＜2,i）可插入到机器A处最前可安置的时间段进行。
在这里，一个编码序列对应一个加工方案，而一个加工方案可对应一个或多个编码序列，这就是二者之关系。
2 •编程：
通过一组随机编码产生一生产加工优先序列，通过解码过程产生相应加工方案及其总耗费时间c.
N次模拟后即可得出解C的概率密度分布情况以及相对最优解vN个C的最小值，如80，77等，甚至出现75）。
a. 4•计算机模拟所得数据分析进行100次模拟得出最优解情况：（共运行10次〉82，83，82，84，78，80，81，83，87，