改进遗传变邻域算法求解飞机装配线调度问题

蔡 玮，赵 轶，陈浩杰，张 剑

（1.西南交通大学 先进设计与制造技术研究所；2.成都飞机工业（集团）有限责任公司成都，610000）

0 引言

飞机装配具有作业数量大、装配关系复杂等特点，且驾驶舱等部段区域可容纳资源的空间有限，所以飞机装配线作业调度问题可看作是一类具有特殊空间约束的资源受限项目调度问题[1]（Resource Constrained Project Scheduling Problem，RCPSP），该类问题已被证明为一类复杂的强NP-hard问题[2]，针对不同约束和目标的RCPSP建模及求解技术，国内外学者展开了大量的研究。

建模中，Elmaghraby和Kamburowski[3]对活动紧前紧后约束进行了归纳并提出了相应的建模方法，Slowinski[4]则从资源约束的角度对RCPSP建模，杨红光[5]等对双边装配线模型进行了研究，曹阳华[6]等考虑了U型装配线的生产效率模型并对该问题进行了求解，孙宝凤[7]等建立了混流装配线的双目标投产排序模型。从求解角度来看，解决RCPSP及其扩展问题的算法可分为三大类：精确算法、启发式算法和元启发式算法（智能算法），其中精确算法虽然能得到理论最优解，但仅适用于小规模求解，由此近似算法开始被应用于求解大规模RCPSP问题[8]。自1963年，Kelley[9]提出了调度生成方案后，在此基础之上各种启发式算法相继被提出，但其不具备优化能力，往往受到问题本身的影响而得不到满意解。元启发式算法和智能算法的应用使问题的求解得到了新的发展，如喻小光[10]等引入局部搜索中的模拟退火算法（Simulated Annealing，SA）来求解RCPSP，进化算法（如遗传算法[11]，Genetic Algorithm，GA）和群体智能算法（如蚁群优化算法[12]，Ant Colony Optimization，ACO）都在求解RCPSP问题上得到了广泛的应用。……