求解零空闲流水线调度问题的改进蚁群算法  

Ant-colony heuristic algorithm for no-idle flow shop scheduling problem

作　　者：张风荣[1] 段俊华[1] 庞荣波[2] 韩红燕[3] 

机构地区：[1]聊城大学计算机科学学院,山东聊城252059 [2]聊城大学东昌学院,山东聊城252000 [3]聊城大学数学学院,山东聊城252059

出　　处：《计算机应用研究》2011年第3期859-861,共3页Application Research of Computers

基　　金：华中科技大学数字制造装备与技术国家重点实验室开放课题;中国博士后科学基金资助项目(20070410791)

摘　　要：针对零空闲流水线调度问题的最大完工时间,提出一种改进蚁群算法。该算法改进了信息素密度的初始化方法和更新规则,采用新的状态转移策略构建新解,结合快速插入邻域局部搜索算法,解决蚁群算法易陷入局部收敛的缺点,从而提高算法的搜索效率。基于典型算例的仿真实验,表明了改进算法具有高效性和优越性。This paper proposed an advanced ant colony algorithm for no-idle flow shop problem（NIFS） with makespan criterion.Improved the pheromone density initialization and updating rules by using a hybrid heuristic strategy,adoped a new state transition rule to construct an ant-sequence.Then,presented an local search algorithm based on the speed-up technology for inserting neighborhood structure for overcoming algorithm into the local convergence.And the simulation experiments show that the presented algorithm is effective and superiority in finding optimal or near optimal solutions.

关 键 词：蚁群算法 信息素密度 信息素更新规则 零空闲流水线调度 最大完工时间 邻域搜索 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP301.6[自动化与计算机技术—控制科学与工程]