求解作业车间调度的改进遗传算法.doc

《求解作业车间调度的改进遗传算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、求解作业车间调度问题的改进遗传算法摘要：本论文中，我们提出了一种解决job-shop调度问题的新遗传算，这个提出的方法在建立分区块假设和模式定理基础之上，用基于作业的表示，提出了一种新的交叉方法。通过筛选排序目标值短，适配高的模式作为遗传算子，此交叉方法可以有效转换父代重要的排序信息从而达到全局优化。用C++编码产生的基于机器的仿真结果表明我们遗传算子是强有效的而且适合车间作业调度问题。我们的方法要比之前的以GA为基础的方法要更有效。关键词：车间作业调度，遗传算法，模式定理，建立分块假设B.1引言车间作业调

2、度问题是众所周知的最难的排序问题之一，其算法需要大量的计算步骤，其步骤也会随着问题的大小呈指数增长。该问题通过决定各工件在机器上的加工顺序来使作业时间最小化，该作业时间就是完成所有工件所需要的时间。尽管JSP调度问题的最优解可以通过统计技术（分支定界法和数学规划法）来得到，这些方法对于即使是中等规模的问题也需要过高的计算量。DavisL.是第一个提出将遗传算法应用到解决JSP问题中的，那是在1985年，最近，用遗传算法来求解JSP问题比以前有了进一步的发展，工件的加工顺序由遗传编码来确定，然后用过滤束搜索方

3、法来解决这个问题。到目前为止，已经有许多研究者提出了基于遗传算法的解决方法。由于Davis已经展示了将遗传算法应用到调度问题中，所以有很多研究者在致力于研究这一主题。他们中的一些人用这种交叉方法设计的有效的作业或操作讨论了流水车间调度问题或者是排序问题像旅行商问题：边缘重组算子和基于位置的交叉。其他人致力与介绍具体问题的代表性模式，因此提出了比传统遗传算子更为复杂的算子来解决动态计划和机器的JSP调度问题。不管怎么样，都不可能来公正的比较这些基于遗传算法的方法，因为这些方法都是跟具体问题相匹配的。1991年

4、，Nakanoetal将常规遗传算法应用到众所周知的ｎ个工件的JSP调度问题中，他们选择的二进制基因型包含了工件在每台机器上加工顺序信息和传统的二进制交叉和变异，但是需要一个修复机制来纠正遗传操作后的不合法调度。Fangetal也成功的将遗传算法应用到解决JSP调度问题，是由基于常规交叉变异的方法的一个变种的父代排序而来的有效调度，它们的性能增强主要是因为基于目标的基因变异，它们交叉和变异的切入点是由基因在种群中的差异来决定的。然而这些基因表示是有多余的，因而存在假性竞争。不管怎样，遗传算法能够让我们迅速得

5、到高质量的解决方法而且很容易的同其他搜索技术进行比较。尽管遗传算法能够使我们获得比其他方法更快更好的解决方法，一些方法已经被运用于解决车间作业问题，但是在遗传计算法和其他具体的方法之间还存在一些代沟，本文中位置转换认为是一个主要的搜索引擎。为了能够把遗传算法成功的运用于解决车间作业调度问题，应该达到些列标准。1完整性，，任何解决方法都应该有编码。2安全性，每个遗传算法的编码都应该有相对应的调试方法3简洁性，编码和提哦啊是方法应该是一对一。4持续性，正如儿童遗传父母的特点。本文中我们运用以操作为基础展现编码，

6、介绍一种改进的部分调度交换交叉，它基于模式定理和建设作为交叉算子块假说。通过选择短的，适合阶段模式的一串操作，这个位置转换可以保存这样的特点。以上述标准看来，这种编码或位置转换非常有效，并且这是通过实验在理论和实际操作上都证明了其有效性。B.2模式定理和建立分块假说为了分析遗传算法的操作，本文介绍了该模式的概念。这个模式可以定义为包含所有类似字符的串，它们是包含在一个种群中的高适应值的染色体中的，这个种群中，不相似的字符用"*"表示，下面的这个方程就是我们所知道的模式定理，它给出了这个模式下一代预计大小的下

7、界。mH(i+1)=H(i)mH(i)[1-PC][(1-Pm)n]/(i)式中：mH(i+1)：模式Ｈ在i+1带的样本数；mH(i)：模式Ｈ在i+1带的样本数；H(i)：包含Ｈ的染色体在第ｉ代的平均适配值；Pc：交叉概率；ｌ：染色体长度；ld：计算而来的模式中字符长度最大值，如果交叉取代了定义的最大长度，那么模式Ｈ被打乱的概率就会增加。Pm：变异概率；n：模式Ｈ的顺序，它的大小是等于模式Ｈ中定义的字符的。这里1-Pm代表个体不发生变异的概率，这个命题可以归纳为：如果H(i)>(i)，模式Ｈ被选择到下一代的

8、概率高，这就意味着上述平均适配值的模式被选择来复制的概率就高。因此，可以作出结论短的排序，高于平均水平的适配值的模式将在后代样本中增加。这些队列短的高与平均适配值的模式就被叫做建立分块，建立分块假说表明遗传算法通过这些分块并置来搜索邻近的最优解。B.3遗传算法B.3.1遗传概述本文采用的是有YasuhiroMeta提出的基于工序的表达法，这种表达法将调度用一系列工序来编码，每一个基因代表一个工件，染色体可以直接解