陶丽华，许之强

（长春工业大学 机电工程学院，长春 130012）

0 引言

Job shop（JSP）问题作为典型的NP-hard 问题一直是制造自动化领域中的经典和热点问题，设计求解JSP 的有效算法一直是调度优化领域的重要课题。

遗传算法（GA）作为一种全局优化搜索算法，具有简单、高效、很容易与其他算法相结合［1］的特点，国内外学者对遗传算法的应用进行了大量的研究。但是在应用GA 求解实际生产调度中的JSP 问题时，常常由于产品工艺复杂，生产约束条件较多，对传统遗传算法在编码方式、遗传算子和解码方式的设计上提出了很高的要求，标准的遗传算法常常会因为搜索效率低、容易提前收敛、陷入局部最优解等问题而无法满足企业生产调度的实际需要。

本文根据离散制造业中典型的Job Shop 调度问题的需求，在标准遗传算法全局搜索的基础上，利用极值优化算法对遗传算子进行改进，提出了一种具有基于工序的编码、活动解码、自适应交叉和变异运算的改进遗传算法，并通过软件仿真实验，验证了改进遗传算法的性能。

1 JobShop 问题描述

典型的Job Shop 调度问题可描述为：有n 个工件可在m 台机器上加工，每个工件由多道工序加工完成，需要考虑如下约束：

1）每个工件必须按照工艺约束要求按顺序依次在指定的机器上加工，即必须在每个工件的前一道工序加工完成后才可以开始后一道工序；

2）工件在一台机器上一旦开始加工，便不可以中断，必须等到此工件加工完成后，才能在该机器上加工另外的工件，即一台机器在某一时刻只能加工一个工件；……