1.1研究背景及现状分析

（1）装配作业车间调度问题概述

生产调度作为影响企业生产效率和市场响应能力的重要因素，并且由于其较强的复杂性，受到广泛地关注。作业车间调度问题（JobShop Scheduling Problem, JSSP）可以描述为若干个包含多道工序的待加工工件在一组功能不同的机器上加工，工艺路线不尽相同，在尽量满足约束的条件下，使有限的资源在一定时间内得到合理地利用，以优化某些性能指标^[1]。

上述的作业车间调度问题并没有考虑工序之间的装配问题，在复杂的定制化产品生产中通常含有装配工序，一个装配工序只有在所需的零部件都加工完成之后才能进行，零部件的协同调度就构成了一个独特而复杂的问题——装配作业车间调度问题^[2]（AssemblyJob Shop Scheduling Problem, AJSSP）

（2）装配作业车间调度问题的研究现状

研究初期，整数规划、动态规划和分支定界法等运筹学的经典方法被用来寻找车间调度问题的最优解。但多数调度问题属于NP-complete问题或NP-hard问题，不存在多项式时间的最优算法， 因此有效的启发式算法得到越来越多的关注和应用。

Jackson^[3]和Smith^[4]提出了最早的基于启发式算法的优先分配规则；FooY P S; Takefuji 和T^[5]提出将神经网络应用于车间调度问题, 他们提出一种基于改进的Tank和Hopfield神经网络模型的整数线性规划神经网络算法（ILPNN）来解决作业车间调度问题,实验结果表明ILPNN 算法不能保证产生最优解。

1999年杨圣祥和汪定伟 ^[6]对此进行改进，采用了满足约束条件的神经网络和启发式算法用于通用车间的调度。在该算法中，自适应神经网络具有在网络运行过程中神经元的偏置和连接权值自适应取值的特性，被用来求得调度问题的可行解，启发式算法分别被用来增强神经网络的性能、获得确定排序下最优解和提高可行解的质量，效果较好。

随后，一些模拟生物进化、人类行为和物理变化过程特点的元启发式算法（Meta-heuristics）也得到了成功地应用，如遗传算法（GeneticAlgorithm ,GA）、模拟退火（SimulatedAnnealing ,SA）、粒子群优化算法（ParticleSwarm Optimization ,PSO）、DNA算法等。此外，基于规则的算法（派工法则，如FIFO、SPT、JDD等）在一定的情况下也能表现出较好的调度性能。然而，虽然目前针对一般作业车间调度问题有比较多的研究，但对装配作业车间调度问题的研究相对较少。因此，设计一个性能优异、使用简单的装配作业车间调度算法对提高企业的生产效率和降低成本有着重要的现实意义。

（3）基于GEP算法的复合派工法则