张丽萍(青岛科技大学 信息科学技术学院，山东 青岛266061)

置换流水车间是很多实际流水线生产调度问题的简化模型，是目前研究最广泛的一类经典的调度问题。由于置换流水车间调度问题属于NP-hard难题，不存在多项式精确求解算法，因此，对这类问题的研究具有重要意义。

求解置换流水车间调度问题的方法大致可以分为三类[1]：经典算法(如线性规划、动态规划、整数规划、分枝定界等)、启发式算法(如 Gupta 法、Palmer法、Johnson 法、CDS法、NEH法等)和基于人工智能的元启发式算法(如模拟退火、禁忌搜索、遗传算法、蚂蚁算法等)。经典算法的计算复杂性一般很大，只适合求解小规模置换流水车间调度问题，在工程中往往不实用。启发式算法通过一定的规则可以快速地构造出问题的解，但通常解的质量较差[2]。基于人工智能的元启发式算法能够较快地构造出问题的解，因此，在置换流水车间调度问题中被广泛使用。

蚁群算法是受到自然界中真实蚂蚁的启发，由意大利学者DORIGO M于1991年提出的一种元启发式算法。该算法具有鲁棒性和通用性等良好特性，在求解作业车间、流水车间等调度问题上取得了较好的效果。但是，传统的蚁群算法存在计算时间长和易陷入停滞的问题，故本文从结合NEH算法和自适应调节策略两方面来改善蚁群算法的性能，经Taillard基准测试验证，改进后的蚁群算法有效。

1 问题描述

置换流水车间调度问题研究的是n个工件在m台机器上的流水加工过程，所有工件以相同的顺序在每一台机器上加工完成，同时约定每个工件在每台机器上只加工一次，每台机器每次最多只能加工一个工件，各工件在各机器上所需的加工时间已知，要求得到某调度方案使得总加工时间最小。……