刘海涛，邓停铭，唐健均，尹 慢

（1.航空工业成都飞机工业（集团）有限责任公司，四川 成都 610000；2.西南交通大学机械工程学院，四川 成都 610000）

1 引言

作业车间调度属于NP 难题，半个多世纪以来一直是学术界的焦点。对于机床×工件=20×50 以内的中小规模[1]调度问题，目前采用启发式算法[2]可以获取较好的结果；超出此规模，即当工件＞50，工件×机器＞1000 时[3]，便成为大规模作业车间调度问题，这种问题往往过于复杂，求解的时间会急速恶化[4]。对此进行了实验，当规模达到4000 时，在MATLAB 环境下采用遗传算法和一台2.8GHz 处理器、8GB 内存的计算机上寻优，9h 后才获得优化近似解。

为解决这类问题，众多学者采用了对问题进行分解的方法，按照一定的策略获取子问题并分别求解，再根据各问题之间的关系重构大规模调度问题的可行解。文献[5]将滚动时域混合瓶颈及分解策略，利用时空两个维度进行大规模调度问题的分解。文献[6]将调度问题中约束和目标函数进行叠加处理后，大规模调度数学模型即转变成若干个分解问题。文献[7]将大邻域搜索融合自适应随机方法，并基于一定的规则策略来分解大规模柔性作业车间调度问题。文献[8]根据工艺相似性进行动态相似度编码，并改进编码规则提高优化求解效率。文献[9]利用模拟退火搜索总拖延期最小的工序集分解方案，并采用粒子群算法求解各调度子问题，最后重组问题获取总调度问题的可行解。文献[10]提出根据交付期分解问题，并采用混合移动瓶颈、模拟退火和可变邻域搜索方法求解大规模问题，求解精度较高，但是时间较长。……