冯世扣，鲍 敏 ，张 伟

(浙江理工大学机械与自动控制学院，浙江杭州310018)

0 引 言

生产车间调度是离散制造系统中关键的一个环节，车间调度通过合理分配现有的资源、安排零件加工次序和加工时间，能够有效的提高生产效率，对车间调度进行研究具有深远的意义［1-2］。生产车间调度问题种类繁多，本研究主要针对单件作业车间调度问题(job shop problem，JSP)。在用遗传算法求解JSP 问题时，初期种群之间差异非常大，很容易造成整个种群过早收敛，算法后期种群趋于一致，个体之间优势不明显，导致种群进化停滞不前［3-5］。为了使调度方案更实用高效，遗传算法得到不断改进和发展。Parviz Fatah［6］在求解过程中建立一个数学性规划模型，用启发式遗传算法结合模拟退火算法求解;张超勇［7］设计了一个种基于工序和机器编码的改进遗传算法，具有更好的遗传特性;王万良等［8］提出了改进自适应遗传算法，改进自适应遗传算法提高了获得最优解的速度;Victor 等［9］改进了混合遗传算法的交叉操作，并将改进的算法应用与车间调度问题中。

本研究针对遗传算法搜索效率低，易于过早收敛等缺点，提出一种新的混合遗传算法。这种算法核心在于:在每一代遗传进化过程中，引入退火思想，在迭代初期退火算法具有很高温度，此时算法有很强的概率突跳性，有利于打破过早收敛问题;引入自适应交叉和变异概率，能使算法在优化过程中自动改变交叉和变异概率，避免盲目交叉，从而提高搜索效率;设计新型的交叉和变异算子，以避免交叉后产生不可行解，相对于传统的算子新算子能够使种群更加的多样化，从而提高找到最优解的概率。……