基于改进离散和声算法的批量流水线调度研究  

Research of lot-streaming flow shop scheduling problem based on improved discrete harmony search algorithm

作　　者：韩红燕[1] 潘全科[2] HAN Hongyan;PAN Quanke(School of Mathematics Science, Liaocheng University, Liaocheng, Shandong 252059, China;State Key Laboratory of Synthetical Automation for Process Industry, Northeastern University, Shenyang 110819, China)

机构地区：[1]聊城大学数学科学学院,山东聊城252059 [2]东北大学流程工业综合自动化国家重点实验室,沈阳110819

出　　处：《计算机工程与应用》2016年第16期65-72,共8页Computer Engineering and Applications

基　　金：国家自然科学基金(No.60874075);新世纪优秀人才支持计划(No.NCET-13-0106);高等学校博士学科点专项科研基金(No.20130042110035);辽宁省教育厅重点实验室基础研究项目(No.LZ2014014)

摘　　要：针对批量流水线调度问题,提出了以总流经时间为目标的改进离散和声算法。与基本的和声算法相比,该算法首先采用了基于工件序列的编码方式,使其直接应用于调度问题,同时运用NEH和SWAP方法产生初始和声库,保证了初始种群具有较高的质量和多样性。使用自适应和声微调概率参数和INSERT方法产生新解,提高了算法的优化性能。为了提高算法的局部搜索能力,结合交换扰动策略和插入邻域搜索算法给出了两种混合求解策略。仿真实验表明所提算法的有效性。An Improved Discrete Harmony Search(IDHS)algorithm is presented for solving the Lot-streaming FlowShop Scheduling Problem(LFSP)with the objective of minimizing the total flow time. Firstly, unlike the traditional HarmonySearch(HS)algorithm, to enable the continuous harmony search algorithm to be used in all scheduling problems, the proposedIDHS algorithm utilizes discrete job permutations to represent harmonies, at the same time, an effective initializationscheme based on the NEH heuristic and SWAP are used to construct an initial harmony memory with a certain level ofquality 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. Simulationresults show the feasibility and effectiveness of the above algorithm.

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

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