基于改进遗传算法的混合车间调度问题研究1(15)

基于改进遗传算法的混合车间调度问题研究

基］：改进遗传算法的混合车问生产调度问题研究

了操作之间的顺序约束，将这种方法用于一般的ＪｏｂＳｈｏｐ调度问题Ｈ引。

ＨＸ，ＣｈｅｎｇＢＣｈｅｎＣ提出用动态规划算法解决作业级子问题的方法，较好地解决将子问题分解到操作级可能出现解振荡的问题Ｈ引。此外，一些高级局域搜索法由于具有普遍适用性和较低的经验复杂性等优点而得到了广泛的重视和应用，它们有：遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＧＡ）、禁忌搜索法、模拟退火算法（ＳＡ）。遗传算法的思想源于生物遗传学和适者生存的自然规律，是由美国Ｍｉｃｈｉｇａｎ大学的Ｈｏｌａｎｄ教授和他的学生发展建立的。Ｈｏｌａｎｄ的两篇文献和ＤｅＪｏｎｇ的博士论文奠定了ＧＡ的理论基础。１９８３年，Ｇｏｌｄｂｅｒｇ在其博士论文中，首次将遗传算法应用到实际的工程系统的优化当中，从而为遗传算法的应用研究和理论研究的更加深入和丰富提供了广阔的前景。由于遗传算法在理论上和经验上被证实能提供在复杂空间中的鲁棒搜索，因而被广泛应用于机器学习，控制，优化等领域。遗传算法不同于前面叙述的梯度法，即它不倾向于局部最优解：另外，它也不同于随机算法，因为她能够引导搜索过程向有希望的区域进行。一般来说，遗传算法是由复制，交叉，和变异三个遗传算子组成。但是遗传算法的最大优点是通过群体间的相互作用，保持已经搜索到的信息，这是基于单次搜索过程的优化方法所无法比拟的。但是，对于某些问题遗传算法也存在着计算速度较慢的问题。这时通常将遗传算法和其他优化算法结合使用，有利于改善搜索效率．禁忌搜索法（ＴａｂｕＳｅａｒｃｈ，ＴＳ）对于复杂的组合优化问题，通过领域搜索以获取最优解的方法，８０年代，Ｇｌｏｖｅｒ在文¨”中叙述了它的基本原理，ＢａｒｎｅｓａｎｄＮｏｗｉｃｋｉ对ＴＳ作了改进。９０年代初，ＴａｉｌａｒｄＥ提出了解决ｎｏｗ．ｓｈｏｐ调度问题的禁忌搜索算法¨引，１９９５年张长水，沈刚为了更有效地搜索解空间，引入了插入移动和移动相结合的机制提高了搜索效率，用来求解Ｊｏｂ．ｓｈｏｐ问题¨９１。模拟退火算法（ＳＡ）将组合优化问题与统计力学中的热平衡问题类比，通过模拟退火过程，可找到全局（或近似）最优解。模拟退火法的改进算法有加温退火法、有记忆的模拟退火法等。１９８２年Ｋｉｒｋｐａｔｒｉｃｋ等人将金属热加工中的退火工艺的思想首次运用于组合优化问题邻域提出了一种新的搜索技术。１９９４年，田澎在文章中对ｆｌｏｗ．ｓｈｏｐ问题构造了一类模拟退火法拍０Ｊ。１９９５年，ＨｉｓａｏＬ，ＳｈｉｎｔａＭ提出一种改进的模拟退火法，用来解决具有最小Ｍａｋｅｓｐａｎ指标的

ａｄａｂｈｕｓｈｉＲ，Ａｒｆｌｏｗ．ｓｈｏｐ排序问题，并与禁忌搜索法等进行了比较啼¨。模拟退火法也可与其他方法相结合进行求解，ＭｉｔｔｅｎｔｈａｌＪ，Ｍｉ仃Ｒ先用贪心法搜索，

将得到的作业序列作为初始解，再用模拟退火法求解单机调度问题哺别。由于模拟退火法能以一定的概率接受差的能量值，因而有可能跳出局部极小，但它的

‘

收敛速度较慢，很难用于实时动态调度环境。

由于各种调度算法都不同程度存在这样或那样的缺点，除了传统组合的启发式规则外，近年来，许多人开始把各种近似算法的组合应用研究作为研究的热点，以弥补各自的缺点。ＬｉｕＨｕａｉｉｅ等人将启发式规则与仿真方法结合用于调度问题，然后将仿真结果训练ＡＮＮ，通过ＡＮＮ选择最优调度规则∞３１。实际的车间调度往往是多目标的，而且这些目标间可能相互冲突。鉴于现有的调度