求解零空闲流水线调度问题的和声退火算法

计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (30): 221-225.

求解零空闲流水线调度问题的和声退火算法

武磊，潘全科，潘玉霞，桑红燕

聊城大学计算机学院，山东聊城 252059

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-10-21 发布日期:2010-10-21

Harmony-annealing optimization for no-idle flow shop scheduling

WU Lei，PAN Quan-ke，PAN Yu-xia，SANG Hong-yan

School of Computer Science，Liaocheng University，Liaocheng，Shandong 252059，China

Received:1900-01-01 Revised:1900-01-01 Online:2010-10-21 Published:2010-10-21

摘要/Abstract

摘要： 针对以最大完工时间为目标的零空闲流水线调度问题提出了和声退火算法。首先引入了基于ROV规则的编码方式，使和声搜索应用于离散问题，从初始化方法、参数调整、候选解的产生、和声记忆库的更新方法等四个方面对基本和声搜索算法进行了改进，基于此提出了改进的和声搜索算法；其次，结合和声搜索和模拟退火算法的优点，分别对和声搜索过程中的最优解、和声记忆库中的随机选中的解及一个新解分别进行模拟退火，提出了三种不同的和声退火算法。仿真实验表明所提算法的有效性和优越性。

关键词: 零空闲流水线调度, 和声搜索算法, 最大完工时间, 和声退火算法

Abstract: An Improved Harmony Search（IHS） optimization algorithm is firstly presented to solve the No-Idle Flow Shop（NIFS） problem with the objective of minimizing the makespan of jobs in the literature.In the improved algorithm，a rule called the Ranked-Order-Value（ROV） is applied to enable the continuous harmony search algorithm to be used in all sequencing problems.Then three hybrid algorithms based on the IHS and the simulated annealing algorithm is studied for the NIFS in this literature.In the hybrid algorithms，several parts of the original harmony search are improved.Simulation results based on the well known benchmark suites in the literature show the effectiveness and superiority of the presented algorithms.

Key words: Key words： no-idle flow shop, harmony search, makespan, harmony-annealing optimization

武磊，潘全科，潘玉霞，桑红燕. 求解零空闲流水线调度问题的和声退火算法[J]. 计算机工程与应用, 2010, 46(30): 221-225.

WU Lei，PAN Quan-ke，PAN Yu-xia，SANG Hong-yan. Harmony-annealing optimization for no-idle flow shop scheduling[J]. Computer Engineering and Applications, 2010, 46(30): 221-225.

[1]	谢锐强，张惠珍. 求解柔性作业车间调度问题的两段式狼群算法[J]. 计算机工程与应用, 2021, 57(7): 251-256.
[2]	罗函明，罗天洪，吴晓东，陈科百. 求解混合流水车间调度问题的离散布谷鸟算法[J]. 计算机工程与应用, 2020, 56(22): 264-271.
[3]	姜天华. 猫群优化算法求解柔性作业车间调度问题[J]. 计算机工程与应用, 2018, 54(23): 259-263.
[4]	翟军昌1，秦玉平2. 随机交叉全局和声搜索算法[J]. 计算机工程与应用, 2018, 54(12): 21-26.
[5]	张文鹏，王兴. 改进型蝙蝠算法在作业车间调度问题中的应用[J]. 计算机工程与应用, 2017, 53(8): 137-140.
[6]	韩红燕1，潘全科2. 基于改进离散和声算法的批量流水线调度研究[J]. 计算机工程与应用, 2016, 52(16): 65-72.
[7]	姚远远，叶春明. 作业车间调度问题的布谷鸟搜索算法求解[J]. 计算机工程与应用, 2015, 51(5): 255-260.
[8]	李丽娟，吴晓，王志龙. 改进细菌觅食算法解决零空闲流水线调度问题[J]. 计算机工程与应用, 2015, 51(17): 255-258.
[9]	范志强. 带作业范围约束的岸桥调度模型及其算法设计[J]. 计算机工程与应用, 2015, 51(17): 259-264.
[10]	孙莉1，2，徐琪1. 混合和声搜索算法优化SVM的订单优先权评价[J]. 计算机工程与应用, 2015, 51(12): 241-245.
[11]	马邦雄，叶春明. 混合和声搜索算法求解基于学习效应的PFSP问题[J]. 计算机工程与应用, 2015, 51(11): 261-265.
[12]	李娥，王波. HS算法在生物生态组合污水处理中的应用[J]. 计算机工程与应用, 2015, 51(1): 238-242.
[13]	李锋刚1，2，魏炎炎1，2，杨龙1，2. 基于和声算法异构Hadoop集群资源分配优化[J]. 计算机工程与应用, 2014, 50(9): 98-102.
[14]	黄帅，马良. 改进和声搜索算法求解一般整数规划问题[J]. 计算机工程与应用, 2014, 50(3): 250-252.
[15]	陈虹1，王飞1，肖振久1，2，孙丽娜1. 基于IHS_LSSVR的网络安全态势预测方法[J]. 计算机工程与应用, 2014, 50(23): 91-94.