刘博省，毛范海，钱 峰

（大连理工大学机械工程学院，辽宁 大连116024）

1 引言

车间调度是一个历史悠久的优化问题，其本质是通过资源的分配和时间的先后顺序来完成不同的生产任务，使预定目标最优化。随着汽车行业的发展，其部件的装配生产线越来越多的面对着多品种、小批量和个性化的制造需求［1］。一方面，传统的凭借经验或简单的确定性规则的排产算法（大多数企业当前的排产方法）难以得到使预订目标最优化的调度；另一方面，动态规划、分枝定界等优化方法可以得到理论上的最优解，但由于算力的制约无法解决大规模的调度问题。所以研究者们将一系列元启发式算法应用在车间调度问题上，取得了一些成果。

文献［2］针对作业车间调度问题，提出了一种并行模拟退火算法，在小规模Job-shop问题上取得了较好的效果；文献［3］提出了一种改进遗传算法来解决JSP问题，运用多种策略丰富解的空间，获得了较好的解；文献［4］针对采用粒子群优化算法解决流水车间调度问题进行了研究综述；文献［5］采用粒子群算法来解JSP问题，用MK01-MK10等十个问题验证了解的有效性。

为解决发动机缸体混流生产线的生产调度问题，将其抽象为Job-shop问题后提出一种基于蚁群和禁忌搜索的混合算法，并进行实例仿真得出此方法的有效性和性能。

2 JSP问题描述及其数学模型建立

2.1 Job-shop问题的描述

n个工件在m台机器上加工，工件均包含m个工序，要求最大完工时间最小（Makespan：最大完工时间，JSP中最常用的研究指标）。……