计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (1): 255-259.

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

动态子和声算法求解无等待批量流水线问题

潘玉霞,谢  光,杨  琳   

  1. 三亚学院,海南 三亚 572000
  • 出版日期:2014-01-01 发布日期:2013-12-30

Harmony search algorithm with dynamic sub-harmony memories for lot-streaming no-wait flowshop scheduling problem

PAN Yuxia, XIE Guang, YANG Lin   

  1. Sanya College, Sanya, Hainan 572000, China
  • Online:2014-01-01 Published:2013-12-30

摘要: 针对无等待批量流水线调度问题,根据和声算法的机理,提出了一种改进的和声算法对其进行求解。利用NEH和混沌序列相结合的方法产生初始解,并实现了和声向量与工序之间的转换;充分利用最优解,设计新的更新算子,为了避免陷入局部最优,引入了变异策略;结合蛙跳算法分组的特点,将和声库随机动态的分成了几个子和声;为平衡算法的全局开发和局部搜索的能力,对子和声中的最优解执行了局部搜索。通过仿真实验与其他几种算法进行比较,证明了算法的有效性。

关键词: 和声搜索, 批量, 无等待流水线调度

Abstract: An enhanced harmony search algorithm is proposed to solve lot-streaming no-wait scheduling problem. An initialization method based on the NEH(Nawaz-Enscore-Ham) heuristic and chaos is designed, and the job sequences and real-valued vector are interconverted. A local best harmony vector is used to produce a new individual. The algorithm may get trapped in a local optimum. To overcome this problem, a mutation scheme is applied to each harmony vector. Then, the harmony memory is dynamic divided into some small-sized sub-HM based on shuffled frog-leaping algorithm. Finally, to further enhance the exploitation capability and efficiency of the algorithm, a local search algorithm is embedded in the proposed harmony search algorithm. The computational results and comparisons show that the proposed algorithm is effective and efficient in finding better solutions for the problem considered.