计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (30): 221-225.

• 工程与应用 • 上一篇    下一篇

求解零空闲流水线调度问题的和声退火算法

武 磊,潘全科,潘玉霞,桑红燕   

  1. 聊城大学 计算机学院,山东 聊城 252059
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-10-21 发布日期:2010-10-21

Harmony-annealing optimization for no-idle flow shop scheduling

WU Lei,PAN Quan-ke,PAN Yu-xia,SANG Hong-yan   

  1. School of Computer Science,Liaocheng University,Liaocheng,Shandong 252059,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-10-21 Published:2010-10-21

摘要: 针对以最大完工时间为目标的零空闲流水线调度问题提出了和声退火算法。首先引入了基于ROV规则的编码方式,使和声搜索应用于离散问题,从初始化方法、参数调整、候选解的产生、和声记忆库的更新方法等四个方面对基本和声搜索算法进行了改进,基于此提出了改进的和声搜索算法;其次,结合和声搜索和模拟退火算法的优点,分别对和声搜索过程中的最优解、和声记忆库中的随机选中的解及一个新解分别进行模拟退火,提出了三种不同的和声退火算法。仿真实验表明所提算法的有效性和优越性。

关键词: 零空闲流水线调度, 和声搜索算法, 最大完工时间, 和声退火算法

Abstract: An Improved Harmony Search(IHS) optimization algorithm is firstly presented to solve the No-Idle Flow Shop(NIFS) problem with the objective of minimizing the makespan of jobs in the literature.In the improved algorithm,a rule called the Ranked-Order-Value(ROV) is applied to enable the continuous harmony search algorithm to be used in all sequencing problems.Then three hybrid algorithms based on the IHS and the simulated annealing algorithm is studied for the NIFS in this literature.In the hybrid algorithms,several parts of the original harmony search are improved.Simulation results based on the well known benchmark suites in the literature show the effectiveness and superiority of the presented algorithms.

Key words: Key words: no-idle flow shop, harmony search, makespan, harmony-annealing optimization