离散和声求解带启动时间批量流水线调度问题  

Discrete harmony search algorithm for lot-streaming flow shop scheduling problem with setup time

作　　者：潘玉霞[1] 谢光[2] 肖衡[1] 

机构地区：[1]三亚学院公共计算机教学部,海南三亚572000 [2]三亚学院理工分院,海南三亚572000

出　　处：《计算机应用》2014年第2期528-532,557,共6页journal of Computer Applications

基　　金：三亚市院地科技合作项目(2012YD42);校级青年基金资助项目(XYQN12-9)

摘　　要：分别在有等待和无等待的情况下,深入分析了带有启动时间的批量调度问题,以最小化最大完成时间为目标,提出了两种离散和声搜索算法。针对算法本质连续而问题离散的矛盾,对和声搜索算法进行改进。首先提出了基于工序的编码方式,采用inver-over和重组两种离散算子产生候选解的进化机制;并利用改进的NEH(NawazEnscore-Ham)方法进行初始化,产生的高质量和多样化的初始种群有效地指导了算法的进化方向,提高收敛速度;最后将一种简单而有效的局部邻域搜索方法嵌入到和声搜索算法中以增强其局部搜索能力。仿真实验和比较结果表明了所提算法的有效性。In this paper, two discrete Harmony Search （HS） algorithms were proposed to solve lot-streaming flow shop scheduling problem with setup time under both the wait and no-wait cases. The objective was to minimize the maximum completion time or makespan. Unlike the original HS algorithm, the proposed algorithm represented a harmony as a discrete job permutation and applied inver-over and reconstruction operators to generate a new mechanism. An efficient initialization scheme based on the modified Nawaz-Enscore-Ham （NEH） heuristic was presented to construct an initial population with a certain level of quality and diversity. A simple but effective local search was added to enhance the intensification capability. The computational results and comparisons show that the proposed algorithm is effective and efficient in finding better solutions for the problem considered.

关 键 词：和声搜索 批量流水线调度 启动时间 最大完工时间 局部搜索 

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