置换流水车间调度问题(Permutation Flow Shop Problem-PFSP),是车间调度领域一个经典的问题,具有重要的理论意义和现实意义。在理论上,该问题代表了一类具有排列性质的组合优化问题,其求解对于其他问题有很强的指导意义。在现实中,一个好的调度顺序,能够减少企业的生产时间,提高企业的资源配置能力,增强企业的竞争力。由于置换流水车间问题的NP-难性质,借鉴蚁群算法在旅行商问题上的成功应用,本文使用蚁群算法来对其求解进行了尝试。在求解质量和计算时间两个方面,提出了改进的机制。首先,提出蚁群算法解决置换流水车间调度问题的一般步骤,即针对该调度问题的蚁群算法的通用结构。在提高求解质量方面：提出了一种蚂蚁在周游的过程中一次选择两个任务的路径构造方法；提出了一种新的与任务“协调度”有关的本地启发规则,将这些工作组合成一个改进的蚁群算法,用于求解调度问题。实验中,将改进算法应用于标准的测试问题中,并将所求结果与文献中数据比较,比较显示改进工作能够求得较好的调度结果。在减少计算时间方面：提出了一种减少时空复杂度的类似快速排序的周游方案；根据置换流水车间问题的关键路径、关键块概念,设计了邻域搜索时的剪枝规则,用以提高计算的效率；对蚁群算法求解该调度问题,进行了并行计算方面的设计,通过实验验证了所做工作的有效性。