马 军，李 薇

(1.安徽财经大学 国际经济贸易学院，安徽 蚌埠 233041；2.安徽财经大学 商务学院，安徽 蚌埠 233030）

0 引言

作业车间调度问题(Job Shop Scheduling Problem，JSSP)是用m台机器(资源)来加工n个工件(任务)，并且每个工件又由k个工序组成，每个工序要按照一定的顺序来完成[1]。JSSP的调度目标是在满足各工序加工顺序约束条件下，确定每台机器上各工序的加工顺序及加工开始时间，并使某个性能指标最优，如制造周期最短[2]。作业车间调度问题是一类典型的复杂生产调度问题，具有约束松弛度紧、NP-Hard等特性[3]。近年来，各国尝试采用不同方法来求解作业车间调度问题，例如：遗传算法 (genetic algorithm)[4～6]、禁忌搜索(taboo search)[7,8]、蚁群算法 (ant colony optimization)[9,10]、演化算法(evolutionary algorithm)[11,12]以及模拟退火(simulated annealing)[13,14]等。各国学者通常使用各种混合方法来求解作业车间调度问题：(1)将现有方法进行一定程度地改进[15～17]；(2)将一些启发式规则集成到已有方法中[18～20]；(3)多种现有方法 的 混 合 集 成[7～9]。 在 求解复杂JSSP的过程中，JSSP的领域知识及专家的经验知识等对于最终的求解质量和求解效率都起着至关重要的作用。因此，考虑将领域知识和经验知识集成到蚁群算法中的尝试，具有重要的理论意义和实践意义。鉴于此，本文拟提出一种求解作业车间调度问题的改进蚁群算法。该方法将调度知识有效地融入到蚁群算法中，以期使其优化效率得到极大地改进。

1 改进蚁群算法

为了有效地求解JSSP，本文提出了一种改进蚁群算法。该方法将调度知识有效地融入到蚁群算法中，使得优化效率得到极大地改进。……