Abstract: An Improved Discrete Harmony Search（IDHS） algorithm is presented for solving the Lot-streaming Flow Shop Scheduling Problem（LFSP） with the objective of minimizing the total flow time. Firstly, unlike the traditional Harmony Search（HS） algorithm, to enable the continuous harmony search algorithm to be used in all scheduling problems, the proposed IDHS algorithm utilizes discrete job permutations to represent harmonies, at the same time, an effective initialization scheme based on the NEH heuristic and SWAP are used to construct an initial harmony memory with a certain level of quality and diversity. Secondly, the adaptive pitch adjustment rate and INSERT heuristic are used to generate new harmonies, the optimization performance of the IDHS algorithm is improved. Lastly, to enhance the algorithm’s local searching ability, two hybrid algorithms are designed by combining the insert neighborhood search algorithm and swap operator. Simulation results show the feasibility and effectiveness of the above algorithm.

Key words: lot-streaming flow shop, harmony search algorithm, total flowtime, adaptive strategy

摘要： 针对批量流水线调度问题，提出了以总流经时间为目标的改进离散和声算法。与基本的和声算法相比，该算法首先采用了基于工件序列的编码方式，使其直接应用于调度问题，同时运用NEH和SWAP方法产生初始和声库，保证了初始种群具有较高的质量和多样性。使用自适应和声微调概率参数和INSERT方法产生新解，提高了算法的优化性能。为了提高算法的局部搜索能力，结合交换扰动策略和插入邻域搜索算法给出了两种混合求解策略。仿真实验表明所提算法的有效性。

关键词: 批量流水线调度, 和声搜索算法, 总流经时间, 自适应策略