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

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

硕ｉ：学位论文

调度方案，这个寻求最优解的过程常称为优化模型。数学优化模型逻辑性强，能清楚地表示出复杂系统中的各种输入输出变量以及较好地反映出多个变量之间的关系，并能实现系统的优化，且建模方便，是车问调度问题中应用较多的一种建模方法。日本学者ＴａｄａｏＭｕｒａｔａ于１９８９年首次对Ｐｅｔｒｉ网的基本性质和应用做了详细的介绍，并将其用于对调度问题进行建模。基本Ｐｅｔｒｉ网模型具有直观易理解的优点，但其在描述复杂系统时节点数目过多，因而只适用于简单系统的建模。有关扩展Ｐｅｔｒｉ网在调度问题中的研究见Ｍｕｒａｔａ文献ｎ引，这里详细介绍了几种典型的扩展Ｐｅｔｒｉ网的研究情况。主要有以下几种模型的应用研究现状。ＥＰ．Ｎ模型，它通过增加决策节点，使Ｐｅｔｒｉ网具有描述诸如ＦＭＳ调度决策过程的能力。这种模型由于节点数目过多，只能用于简单系统的建模。Ｍｕｒａｔａ对此做了详细的论述。１９９１年ＷａｎｇＷＸ等人对扩展Ｐｅｔｒｉ网在制造系统中的应用做了详细论述比０１，由于ＣＰ．Ｎ是Ｐｅｔｒｉ网的压缩形式，同基本Ｐｅｔｒｉ网相比它具有较少的节点数目，所以比较适合复杂系统的建模，但其分析方法比较复杂。Ｖｅｎｋａｔｅｓｈ等人将ＴＰ．Ｎ模型应用到ＦＭＳ的局域网建模，控制和仿真当中口¨，它不仅能够描述系统中事件和状态演化中的逻辑关系，而且通过设置时间与变迁或库所的联系来分析Ｐｅｔｒｉ网演化过程。姜思杰将Ｐ／ＴＰ．Ｎ模型应用于ＧＡ（遗传算法）和ＴＳ（禁忌搜索算法）混合算法的建模当中口¨，虽然它比ＥＰ．Ｎ模型结构简单，但它没有决策节点。Ｊｅｎｓｅｎ将Ｐ／ＴＰ．Ｎ和ＣＰ．Ｎ结合起来提出了ＨＬＰ．Ｎ。严洪森在ＨＬＰ．Ｎ和ＥＰ．Ｎ的基础上提出了ＥＨＬＥＰ．Ｎ模型心纠，该网结构简单，节点少，很适合于ＦＭＳ的建模，仿真与控制。随着面向对象（ＯＯ）技术的发展与应用，人们开始研究如何将Ｐｅｔｒｉ网与ＯＯ技术结合起来，１９９６年，ＷａｎｇＬＣ通过将制造系统分为四个阶段，提出了一个集成的ＯＯＰＯ机制，增强了Ｐｅｔｒｉ网的设计描述能力和功能实现能力，降低其建模和分析的系统依赖性与难度乜副。随后他又对ＯＯＰＯ机制在单元控制建模中的发展和应用做了系统研究乜引。随着研究的深入，启发式算法因其易于实现，计算复杂度低等原因，在实际中得到了广泛的应用心纠。，并且多年来一直受到学者们的广泛关注，不断涌现出许多新的调度规则。例如，ＰａｎｗａｌｋａｒＳＡ对１ｌ３种启发式调度规则作了详细地总结，将其划分为简单规则，复合规则，启发式规则三类心”。纪树新等在文心引中举了常见的２０条规则，并针对一个实际的制造系统，分析了这些规则对系统性能如作业的平均等待时间、机床的平均利用率、作业总加工时间等的影响。随着计算机运算速度的飞速提高，人们希望寻找新的近似调度方法，它以合理的额外计算时间代价，换得比单纯启发式规则所得到的调度更好的调度，如文［２９］中提出的移动瓶颈方法。虽然启发式规则常被用于实际当中，但它们一般不具有全局优化的特点心引。这一阶段硕果累累，解决了一系列长期困惑人们的难题，为车间调度问题的研究打下了坚实的基础。

随着调度理论研究的更加深入以及各种交叉学科的发展，不断涌现出了许多新的求解问题的方法。１９９１年，Ｇｅｒｓｈｗｉｎ等人从控制理论的角度出发，全面阐述了控制理论的方法在制造系统的应用情况心“。控制理论方法比较适合定