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

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

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

量地定义基本问题，但它只适合对小规模系统进行求解。１９９３年，邓子琼，李小宁对控制理论方法进行了深入地探讨ｎ引，主要集中在扰动分析法和极大代数法上面。扰动分析法兼容了仿真法与理论分析的长处，同时也避免了单纯用仿真法的大量计算和理论分析研究复杂问题所遇到的困难，主要用于研究制造系统的性能指标（生产率等）对参数变化的敏感性，并以此为基础对系统的运行进行优化，但是它对多参数的扰动很难用表或状态方程表示仿真运行过程，扰动较大，近似度较差。极大代数法用与解决线性系统相类似的方法对ＤＥＤＳ（离散事件动态系统）进行建模。它根据系统的运行关系建立起一系列事件发生时间的关系方程。但此方法必须在工件加工顺序事先确定的条件下，才能进行建模分析，因而只适合制造系统的性能分析，而不适合调度。１９９３邓子琼等人利用仿真语言对此又进行了研究分析，并取得一定的进展，但是此方法主要缺点是代价很高ｎ８１。１９９８年，姜思杰在《基于ＧＡ和ＴＳ的最小平衡算法及其在ＦＭＳ中的应用》一文中运用数学规划的方法对排队网络用于ＦＭＳ做了初步的分析心¨。但排队网络只能分析系统的生产率，平均时间等，很难将车间其它资源考虑进去，并且很难处理系统出现异常时的情况。此外还有对线性规划法理论的再研究，Ｌｅｎｏｎｉｄ，ＮｉｓｏｎＶａｓｅｒｓｔｅｉｎ等人对此方法的建模重新进行了详细地论述

【２６】

ｏ

大量启发式算法的出现解决了过去无法解决的许多实际问题。随着各种新的相关学科与优化技术的建立与发展，在车间调度领域也出现了许多新的优化方法，以遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ）．禁忌搜索（ＴａｂｕＳｅａｒｃｈ）、模拟退火（ＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇ）、人工神经网络（ＡｒｔｉｆｉｃｉａｌＮｅｕｒａｌＮｅｔｗｏｒｋ）、多智能体（Ｍｕｌｔｉ．ａｇｅｎｔ）为代表的智能优化算法在理论上取得了很大进展，并应用到车间调度问题中，取得了理想的效果。

一般的车间调度问题都是对于具体生产环境中复杂的、动态的、多目标的调度问题的一种抽象和简化，因而一个调度算法可以通过其如何表述这些复杂性进行分类。文［２６］中为了帮助区别不同的生产调度策略，给出了典型生产调度环境的５个特征：１）边界条件。２）分批大小和调整费用。３）加工路径。４）随机事件和扰动。５）性能指标和多目标。车间调度问题的研究方法最初是集中在整数规划、仿真和简单的规则上，这些方法不是调度结果不理想就是难以解决复杂的问题。

Ｍｕｒａｔａ对基于离散事件动态系统（ＤＥＤＳ）的解析模型这一方法进行了较早的研究，它主要有ＱＮ，极大代数法，动态规划法，但它们都适合制造系统的性能分析ｎ引。另外ＨｕＧＨ等人利用普通随机Ｐｅｔｒｉ网对ＦＭＳ调度与控制决

Ｃ策支持系统进行了研究。１９９１年，ＪｉａｎｇＱ，Ｓｉｎ曲ＭＧ用带有限缓存的排队

网络来描述带有有限存储容量的制造系统拍３１：由于制造系统的复杂性，以至于很难用精确的解析模型对其进行描述分析。但是仿真却能提供这种理想模型，且可以定量地进行评估，从而对实际系统采用合适的方法。这一方面，美国，德国的研究现在处于领先地位，１９９３年，

ＤｏｕｂｌｇｅｒｉＺ，ＤａｌｅｓｓａｎｄｒｏＧ在文口５１