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

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

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

An enhanced harmony search algorithm is proposed to solve lot-streaming no-wait scheduling problem. An ini-tialization 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 effec-tive and efficient in finding better solutions for the problem considered.