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

求解作业车间调度问题的改进遗传算法摘要：本论文中，我们提出了一种解决job-shop调度问题的新遗传算，这个提出的方法在建立分区块假设和模式定理基础之上，用基于作业的表示，提出了一种新的交叉方法。通过筛选排序目标值短，适配高的模式作为遗传算子，此交叉方法可以有效转换父代重要的排序信息从而达到全局优化。用C++编码产生的基于机器的仿真结果表明我们遗传算子是强有效的而且适合车间作业调度问题。我们的方法要比之前的以GA为基础的方法要更有效。关键词：车间作业调度，遗传算法，模式定理，建立分块假设B.1引言车间作业调度问题是众所周知的最难的排序问题之一，其算法需要大量的计算步骤，其步骤也会随着问题的大小呈指数增长。该问题通过决定各工件在机器上的加工顺序来使作业时间最小化，该作业时间就是完成所有工件所需要的时间。尽管JSP调度问题的最优解可以通过统计技术（分支定界法和数学规划法）来得到，这些方法对于即使是中等规模的问题也需要过高的计算量。DavisL.是第一个提出将遗传算法应用到解决JSP问题中的，那是在1985年，最近，用遗传算法来求解JSP问题比以前有了进一步的发展，工件的加工顺序由遗传编码来确定，然后用过滤束搜索方法来解决这个问题。到目前为止，已经有许多研究者提出了基于遗传算法的解决方法。由于Davis已经展示了将遗传算法应用到调度问题中，所以有很多研究者在致力于研究这一主题。他们中的一些人用这种交叉方法设计的有效的作业或操作讨论了流水车间调度问题或者是排序问题像旅行商问题：边缘重组算子和基于位置的交叉。其他人致力与介绍具体问题的代表性模式，因此提出了比传统遗传算子更为复杂的算子来解决动态计划和机器的JSP调度问题。不管怎么样，都不可能来公正的比较这些基于遗传算法的方法，因为这些方法都是跟具体问题相匹配的。1991年，Nakanoetal将常规遗传算法应用到众所周知的ｎ个工件的JSP调度问题中，他们选择的二进制基因型包含了工件在每台机器上加工顺序信息和传统的二进制交叉和变异，但是需要一个修复机制来纠正遗传操作后的不合法调度。Fangetal也成功的将遗传算法应用到解决JSP调度问题，是由基于常规交叉变异的方法的一个变种的父代排序而来的有效调度，它们的性能增强主要是因为基于目标的基因变异，它们交叉和变异的切入点是由基因在种群中的差异来决定的。然而这些基因表示是有多余的，因而存在假性竞争。不管怎样，遗传算法能够让我们迅速得到高质量的解决方法而且很容易的同其他搜索技术进行比较。尽管遗传算法能够使我们获得比其他方法更快更好的解决方法，一些方法已经被运用于解决车间作业问题，但是在遗传计算法和其他具体的方法之间还存在一些代沟，本文中位置转换认为是一个主要的搜索引擎。为了能够把遗传算法成功的运用于解决车间作业调度问题，应该达到些列标准。1完整性，，任何解决方法都应该有编码。2安全性，每个遗传算法的编码都应该有相对应的调试方法3简洁性，编码和提哦啊是方法应该是一对一。4持续性，正如儿童遗传父母的特点。本文中我们运用以操作为基础展现编码，介绍一种改进的部分调度交换交叉，它基于模式定理和建设作为交叉算子块假说。通过选择短的，适合阶段模式的一串操作，这个位置转换可以保存这样的特点。以上述标准看来，这种编码或位置转换非常有效，并且这是通过实验在理论和实际操作上都证明了其有效性。B.2模式定理和建立分块假说为了分析遗传算法的操作，本文介绍了该模式的概念。这个模式可以定义为包含所有类似字符的串，它们是包含在一个种群中的高适应值的染色体中的，这个种群中，不相似的字符用*表示，下面的这个方程就是我们所知道的模式定理，它给出了这个模式下一代预计大小的下界。mH(i+1)=FH(i)mH(i)[1-PC1lld][(1-Pm)n]/F(i)式中：mH(i+1)：模式Ｈ在i+1带的样本数；mH(i)：模式Ｈ在i+1带的样本数；FH(i)：包含Ｈ的染色体在第ｉ代的平均适配值；Pc：交叉概率；ｌ：染色体长度；ld：计算而来的模式中字符长度最大值，如果交叉取代了定义的最大长度，那么模式Ｈ被打乱的概率就会增加。Pm：变异概率；n：模式Ｈ的顺序，它的大小是等于模式Ｈ中定义的字符的。这里1-Pm代表个体不发生变异的概率，这个命题可以归纳为：如果FH(i)F(i)，模式Ｈ被选择到下一代的概率高，这就意味着上述平均适配值的模式被选择来复制的概率就高。因此，可以作出结论短的排序，高于平均水平的适配值的模式将在后代样本中增加。这些队列短的高与平均适配值的模式就被叫做建立分块，建立分块假说表明遗传算法通过这些分块并置来搜索邻近的最优解。B.3遗传算法B.3.1遗传概述本文采用的是有YasuhiroMeta提出的基于工序的表达法，这种表达法将调度用一系列工序来编码，每一个基因代表一个工件，染色体可以直接解码为一个调度。一个染色体由ｎ＊ｍ个基因组成，每一个基因表示一个工件，每一个基因根据工件－机器加工顺序表按显示的顺序进行调度。例如：对于表B.1，假设有一个染色体[2,1,3,3,1,2,2,1,3],第一个基因2表示工件2的第一道工序，第二个基因2表示工件1的第一道工序，第三个基因3表示工件3的第1道工序，根据表格1所示的工件－机器加工顺序表，如图B.1所示，这个调度安排为：J2的第一道工序在M1上加工时间为1，完工时间是12.图B.1一个可行调度B.3.2适配值函数在每一次迭代过程中，都要用适配手段来评价当代个体。这些评价函数有大量的特征。在优化问题应用中，适配值是通过原目标函数来计算的，在本论文中，每一个体的适配值是通过下面的相关调度的总运行时间（周程时间）来评价的表B.1工件机器加工安排工件加工顺序123加工时间J1332J2153J3323机器顺序J1M1M2M3J2M1M3M2J3M2M1M3f(Si)=Nj1min{ft(j)}式中ft(j)——工件j的完工时间。B.3.3交叉本文中，我们根据模式定理和建立分块假说改进了局部调度的交换交叉，这是由Gen和Cheng提出的。这个改进的交叉算子总结如下：（1）在父代1中随机选择一个位置，第二个选择的基因位置和第一个基因的相同，两个基因之间块的长度最短，然后局部调度１就由这些基因组成。（2）产生局部调度2，重复步骤（1）得到父代2.（3）交换局部调度产生子代1和子代2.（4）给子代1和子代2找出遗漏的和浪费的基因。（5）通过随机删除浪费的基因和插入遗漏的基因来使子代1和子代2合法化，对于高于局部调度的调度尽力让它的顺序保持与调度顺序相近。例如：父代1=3212341244134123父代2=4132134123421234子代1=3213412341244134123子代2=4132123421234合法的后代：子代1＝3142134123412432子代2＝432123421234431B.3.4变异尽管交叉在尽力提高后代的适配值，现有解决方存在法使后代汇集的可能。有一个避免机制就是变异，它以微小的概率在相同的个体中随机变化，我们把变异算子定义如下：在个体中随机产生在两个位置然后交换它们的基因，如果这两个基因是相同的，则重新选择新的位置。例如：父代1＝p1=1243214223141433子代1=1244214223131433B.4数值试验为了研究本文所述方法的有效行，文字研究和比较了之前的方法。在试验只能够，算法通过C++来进行编码，遗传算法的所有参数按以下所示：种群大小500，变异概率0.15，交叉概率0.7，表B.2展示了传统方法和本文所述方法的调度结果。对每一个问题，本文所述的方法能够立即得到最优调度。MT10的调度甘特图如图B.2所示。表B.2本文所述方法和其他方法比较调度结果图B.2MT10调度甘特图B.5结论作业车间调度问题是属于最难的组合调度问题，本论文采用了模式定理和建立分块假说，这个新的方法通过选择短的队列，高匹配的模式作为遗传算子来有效解决ＪＳＰ调度问题，本方法通过了著名的基准问题测试，计算结果表明本方法在在所有测试的基准问题中是可行的，我们相信这个算法可以有效的运用到实际调度问题中。时间机器