一类求解置换流水车间问题的蚁群算法.doc

文档介绍：
一类求解置换流水车间问题的蚁群算法#
尚可,冯祖仁,柯良军**
(西安交通大学机械制造系统工程国家重点实验室)
5
摘要:本文提出了一类有限级蚁群优化算法来求解置换流水车间问题,该算法的主要特点是
信息素迹的更新数量独立于目标函数值,并且采用了 ellin 提出的启发信息。提出的算
法应用于 Taillard 给出的基准问题,实验结果表明了所提出算法的的有效性。
关键词:系统工程;蚁群算法;有限级信息素;置换流水车间问题
中图分类号:TP301
10
An ant colony algorithm for permutation flow shop
SHANG Ke, FENG Zuren, KE Liangjun
(State Key Laboratory for Manufacturing Systems Engineering, Xi'an Jiaotong University)
Abstract: In this paper, an algorithm, called finite grade ant colony optimization, is proposed to
15
20
25
30
35
solve permutation flow shop problem, its main characteristic is that the updated quantities of
pheromone trails are independent of objective function values, and the heuristic information
provide by ellin is adopted. The developed algorithm has been applied to the benchmark
problems given by Taillard, Comparison results demonstrate that the performance of the proposed
algorithm is promising.
Key words: Systems Engineering; ant colony algorithm,finite grade pheromone,permutation flow
shop problem
0 引言
本文研究了置换流水车间问题,其目标是最小化完工时间,或者最大化完成时间。该问
题是在给定的加工时间内,在 m 台机器上调度 n 个任务,并且所有任务在每台机器上的加
工顺序是确定的。在任何时间,每个任务最多只能在一台机器上加工,并且每台机器最多只
能加工一个任务,并且不允许抢占[1]。
该问题通过 F / prmu / Cmax 表示,是非常有名的 NP 难组合优化问题。到目前为止,已
经有了很多近似算法能够在较短的时间内找到一个足够好的序列。所有文献中的近似算法可
以归为构造性或改进型方法。到目前为止,Campbell et al. [2], Dannenbring [3], Röck et al. [4],
Nawaz et al. [5] 等人已经提出了最好的构造型算