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

计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (16): 65-72.

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

韩红燕1，潘全科2

1.聊城大学数学科学学院，山东聊城 252059
2.东北大学流程工业综合自动化国家重点实验室，沈阳 110819

出版日期:2016-08-15 发布日期:2016-08-12

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

HAN Hongyan1, PAN Quanke2

1.School of Mathematics Science, Liaocheng University, Liaocheng, Shandong 252059, China
2.State Key Laboratory of Synthetical Automation for Process Industry, Northeastern University, Shenyang 110819, China

Online:2016-08-15 Published:2016-08-12

摘要/Abstract

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

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

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

韩红燕1，潘全科2. 基于改进离散和声算法的批量流水线调度研究[J]. 计算机工程与应用, 2016, 52(16): 65-72.

HAN Hongyan1, PAN Quanke2. Research of lot-streaming flow shop scheduling problem based on improved discrete harmony search algorithm[J]. Computer Engineering and Applications, 2016, 52(16): 65-72.

[1]	陈瑶，陈思. 基于自适应多普勒及动态邻域的改进BA算法[J]. 计算机工程与应用, 2021, 57(22): 166-176.
[2]	宋钰，石立宝. 参数动态调整的自适应布谷鸟算法[J]. 计算机工程与应用, 2020, 56(23): 61-67.
[3]	翟军昌1，秦玉平2. 随机交叉全局和声搜索算法[J]. 计算机工程与应用, 2018, 54(12): 21-26.
[4]	翁理国，王骥，夏旻，纪壮壮. 自适应种群更新策略的多目标粒子群算法[J]. 计算机工程与应用, 2017, 53(15): 181-186.
[5]	李建美，高兴宝. 基于自适应变异的混沌粒子群优化算法[J]. 计算机工程与应用, 2016, 52(10): 44-49.
[6]	孙莉1，2，徐琪1. 混合和声搜索算法优化SVM的订单优先权评价[J]. 计算机工程与应用, 2015, 51(12): 241-245.
[7]	马邦雄，叶春明. 混合和声搜索算法求解基于学习效应的PFSP问题[J]. 计算机工程与应用, 2015, 51(11): 261-265.
[8]	李娥，王波. HS算法在生物生态组合污水处理中的应用[J]. 计算机工程与应用, 2015, 51(1): 238-242.
[9]	李锋刚1，2，魏炎炎1，2，杨龙1，2. 基于和声算法异构Hadoop集群资源分配优化[J]. 计算机工程与应用, 2014, 50(9): 98-102.
[10]	黄帅，马良. 改进和声搜索算法求解一般整数规划问题[J]. 计算机工程与应用, 2014, 50(3): 250-252.
[11]	陈虹1，王飞1，肖振久1，2，孙丽娜1. 基于IHS_LSSVR的网络安全态势预测方法[J]. 计算机工程与应用, 2014, 50(23): 91-94.
[12]	郭正红1，赵丙辰2. 改进和声搜索算法优化LSSVM的脑CT图像分类[J]. 计算机工程与应用, 2013, 49(22): 146-149.
[13]	魏林1，付华2，尹玉萍2. 和声蚁群耦合算法求解整数规划的应用研究[J]. 计算机工程与应用, 2013, 49(20): 5-8.
[14]	蒋国瑞，胡应兰. 基于D-S证据理论的多Agent辩论谈判策略研究[J]. 计算机工程与应用, 2013, 49(12): 36-40.
[15]	倪志伟1，2，尹道明1，2，王力1，2，李怀英1，2，王士凯1，2. 基于和声搜索算法的知识即服务动态组合优化[J]. 计算机工程与应用, 2012, 48(32): 212-217.