半导体作业车间调度问题一般可以描述为:m个工件在n台机器上加工, 一个工件可以分为k道工序, 每一台机器在每个时刻只能加工某个工件的某道工序, 只能在上道工序加工完成后才能开始下一道工序的加工, 前者称为占用约束, 后者称为顺序约束。所以JSP问题的研究内容包括工件的加工顺序和工件各工序的加工时间以及工件工序的加工设备分配。常见的半导体生产车间调度问题应满足如下约束: (1) 一个工件不能同时在不同机器上加工; (2) 对整个工件来说, 在加工过程中采用平行移动方式, 即当上一道工序完工之后, 立即送往下道工序加工; (3) 不容许中断, 当一个工件一旦开始加工, 必须一直进行到完工, 不容许中途停下来, 插入其他工件; (4) 每台机器可以执行多种工序的加工任务, 但每台机器同时只能加工一个工件; (5) 工件数、机器数、加工时间已知, 且加工时间与加工顺序无关; (6) 容许工件在工序之间等待, 容许机器在工件未到达时闲置; (7) 工件加工技术上的约定事先给定。
本文采用基于工序的编码方法。对于m个工件n台机器的半导体生产车间调度问题, 基于供需的编码方法将每个染色体用m×n个代表工件的基因组成, 是所有工件的一个排列, 其中各工件均出现n次。一条染色体可以表示为X={x 1, x2, ...mx×n}, 其中xk=i1 (≤i≤m, 1≤k≤m×n) 。如果xk是染色体X中从1x到xk的第j (j≤m) 个i, 则表示工件i的第j个工序, 个体X表示各工件各工序基于作业加工顺序的一个排列。加工时间矩阵T:m×n矩阵, 存储m个工件m×n个工序加工时间。调度方案编码矩阵X:m×n矩阵, 储存m个工件在n台机器上的加工先后顺序。遗传进化迭代次数M:取20。种群规模N (取偶数) :取10。P向量:1×n的向量, n个工序中, 每一个工序所具有的机床数目, 本论文描述的问题中每个工件都要经过n道工序的加工。交叉概率cP:取0.8。变异率mP:取0.1。
对于半导体生产车间调度问题, 我们仍然采用目标函数的最小化的最大完工时间作为适应度函数, 即令Ckmax表示第k个染色体的最大完工时间, 那么适应值为:
设由N个染色体组成群体C={x1, x2, ..., xi}, 选择算子中主要解决的问题是群体中染色体的选择概率pr。
本文采用轮盘赌选择方法, 这在上一章中已经介绍过, 该方法根据每个染色体适应度值的比例来确定该染色体的选择概率或生存概率, 适应度值高的染色体被选入下一代的概率比较高, 因此, 容易继承比较好的染色体。
其中f (ix) 为染色体x的适应值。
在上一章已介绍过了常用的交叉算子, 本论文采用单点交叉, 即在染色体中随机产生一个交叉位置, 后代染色体继承父代1前半部分基因, 继承父代2的后半部分基因, 这样破坏个体性状和降低个体适应度值的可能性较小。
当交叉操作产生的后代适配值不再进化且没有达到最优时, 就意味着算法的早熟收敛。这种现象的根源在于有效基因的缺损, 变异操作在一定程度上克服了这种情况, 有利于增加种群的多样性, 本论文采用基本位变异法。
五个工件J1, J2, J3, J4, J5, J6分别需要5道工序。其中J1的五道工序分别耗时1 23 4 2分钟, J2的五道工序分别耗时2 4 1 32分钟, J3的五道工序分别耗时3 2 5 3 4分钟, J4的五道工序分别耗时2 3 5 4 1分钟, J5的五道工序分别耗时4 3 4 2 1分钟。这五道工序所具有的机床数目分别为23 2 4 2个。
通过仿真得到的结果是以甘特图的形式表现出来的。
在所做的仿真图中, 总的完成时间为18分钟。J1的第一道工序在M2上完成, 第二道工序在M3上完成, 第三道工序在M2上完成, 第四道工序在M4上完成, 第五道工序在M2上完成。后面几个工件的加工时序描述就不一一赘述。
这里分别将迭代次数改为40, 60, 80, 100时, 所得的加工流程都不相同, 所得最小加工时间也会有所不同。利用遗传算法得到的最优结果有一定的随机性, 每次运行程序得到的调度排序可能不同, 所以对于规模较小的问题容易得到最优或次优值, 对于规模较大的问题, 一般不易得到最优结果, 而且最后的完工时间也可能不同。
摘要：本文系统介绍了半导体生产车间调度问题以及遗传算法的基本原理, 并针对半导体生产车间调度问题的特点, 设计了一种遗传算法。最后使用Matlab编写程序求解半导体生产车间调度问题。并通过对不同的问题的仿真对程序性能进行分析。
关键词：半导体生产车间调度,遗传算法,MATLAB的应用
[1] 吴启迪, 乔非, 李莉, 等.半导体制造系统调度[M].电子工业出版社, 2006.
[2] 刘飞, 等.CIMS制造自动化[M].机械工业出版社, 1997.
[3] 王凌.半导体生产车间调度及其遗传算法[M].清华大学出版社, 2003, 5.
[4] 应保胜, 张华, 杨少华.敏捷制造半导体生产车间布局优化的启发式算法[J].计算机集成制造系统, 2004, 10 (8) :61～6 8.
[5] 王凌.车间调度及遗传算法[M].清华大学出版社, 2003.
[6] 周明, 孙树栋.遗传算法原理及应用[M].国防工业出版社, 1999, 6.
推荐阅读：
基于问题的学习在中小学的应用06-24
混合式课例研究是基于对问题的研究06-03
山大医学遗传学辅导教案06-08
遗传高血压是什么原因09-09
遗传学100个名词解释06-01
基于主题的情感分析06-24
基于dm广告的研究06-01
基于zigbee的课程设计06-15
基于arcgis的课程设计07-11
