摘要：作业车间调度问题是一个典型的NP-HARD问题，也是一个前沿性的研究课题，已受到学术界和工业界的广泛关注。该文采用一种改进蚁群算法来求解作业车间调度问题。在本文提出的改进蚁群算法，先是应用蚁群算法获得一些作业车间调度问题的较优解(调度方案)；再从这些调度方案中挖掘出一些有用的调度知识；最后应用这些调度知识来辅助蚁群算法完成后续的优化过程。通过将调度知识有效地融入到蚁群算法中，使得本文提出的改进蚁群算法在优化效率大大改进。
关键字：作业车间调度问题；蚁群算法；调度知识
1 引言
作业车间调度问题(Job Shop Scheduling Problem，JSSP)是用台机器(资源)来加工个工件(任务)，并且每个工件又由个工序组成，每个工序要按照一定的顺序来完成[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的领域知识及专家的经验知识等对于最终的求解质量和求解效率都起着至关重要的作用。因此，考虑将领域知识和经验知识集成到蚁群算法中的尝试，具有重要的理论意义和实践意义。鉴于此，本文提出了一种求解作业车间调度问题的改进蚁群算法。该方法将调度知识有效地融入到蚁群算法中，使其优化效率得到极大地改进。