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

计算机应用 ›› 2014, Vol. 34 ›› Issue (2): 528-532.

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

潘玉霞¹,谢光²,肖衡¹

1. 三亚学院公共计算机教学部,海南三亚 572000
2. 三亚学院理工分院,海南三亚 572000

收稿日期:2013-07-22 修回日期:2013-09-07 出版日期:2014-02-01 发布日期:2014-03-01
通讯作者: 潘玉霞
作者简介:潘玉霞（1983-），女，山东德州人，讲师，硕士，主要研究方向：计算智能及优化调度；谢光（1983-），山东聊城人，讲师，硕士，主要研究方向：人工智能、专家系统；肖衡（1979-），海南三亚人，讲师，硕士，主要研究方向：人工智能、专家系统、计算机网络。
基金资助:
三亚市院地科技合作项目;校级青年基金资助项目

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

PAN Yuxia¹,XIE Guang²,XIAO Heng¹

1. Department of Basic Computer Education, Sanya University,Sanya Hainan 572000,China；
2. Polytechnic Institute, Sanya University, Sanya Hainan 572000,China

Received:2013-07-22 Revised:2013-09-07 Online:2014-02-01 Published:2014-03-01
Contact: PAN Yuxia

摘要/Abstract

摘要： 分别在有等待和无等待的情况下，深入分析了带有启动时间的批量调度问题，以最小化最大完成时间为目标，提出了两种离散和声搜索算法。针对算法本质连续而问题离散的矛盾，对和声搜索算法进行改进。首先提出了基于工序的编码方式，采用inver-over和重组两种离散算子产生候选解的进化机制；并利用改进的NEH(Nawaz-Enscore-Ham)方法进行初始化，产生的高质量和多样化的初始种群有效地指导了算法的进化方向，提高收敛速度；最后将一种简单而有效的局部邻域搜索方法嵌入到和声搜索算法中以增强其局部搜索能力。仿真实验和比较结果表明了所提算法的有效性。

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

Abstract: 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.

Key words: Harmony Search(HS), Lot-streaming Flowshop Scheduling, Setup Time, Makespan, local search

中图分类号:

TP18

潘玉霞谢光肖衡. 离散和声求解带启动时间批量流水线调度问题[J]. 计算机应用, 2014, 34(2): 528-532.

PAN Yuxia XIE Guang XIAO Heng. Discrete harmony search algorithm for lot-streaming flow shop scheduling problem with setup time[J]. Journal of Computer Applications, 2014, 34(2): 528-532.

[1]	邓文瀚, 张铭, 王李进, 钟一文. 混合群体增量学习算法求解闭环布局问题[J]. 计算机应用, 2021, 41(1): 95-102.
[2]	陈桢, 钟一文, 林娟. 求解0-1背包问题的混合贪婪遗传算法[J]. 计算机应用, 2021, 41(1): 87-94.
[3]	张架鹏, 倪志伟, 倪丽萍, 朱旭辉, 伍章俊. 基于改进离散人工蜂群算法的同类机调度优化[J]. 计算机应用, 2020, 40(3): 689-697.
[4]	张玉州, 徐廷政, 郑军帅, 饶舜. 考虑紧急度的救灾车辆路径问题建模与优化[J]. 计算机应用, 2019, 39(8): 2444-2449.
[5]	宋婷, 陈矛, 吴超, 张龚钊. 基于多类迭代局部搜索的自动化排课算法[J]. 计算机应用, 2019, 39(6): 1760-1765.
[6]	陈林烽, 齐学梅, 陈俊文, 黄琤, 陈付龙. 批量流水调度问题的量子候鸟协同优化算法[J]. 计算机应用, 2019, 39(11): 3250-3256.
[7]	吕进锋, 赵怀慈. 基于记忆库粒子群算法的海上协作搜寻计划制定[J]. 计算机应用, 2018, 38(9): 2477-2482.
[8]	李斌, 陈爱斌, 周国雄, 周涛. 基于Cell-DEVS的森林灭火资源调度狼群优化算法[J]. 计算机应用, 2018, 38(5): 1494-1499.
[9]	王晓静, 彭虎, 邓长寿, 黄海燕, 张艳, 谭旭杰. 基于均匀局部搜索和可变步长的萤火虫算法[J]. 计算机应用, 2018, 38(3): 715-721.
[10]	顾军华, 霍士杰, 武君艳, 尹君, 张素琪. 求解最大团问题的并行多层图划分方法[J]. 计算机应用, 2018, 38(12): 3425-3432.
[11]	王佳君, 喻强, 张晶晶. 基于先验置信传播的图像修复改进算法[J]. 计算机应用, 2016, 36(4): 1115-1119.
[12]	宋月振, 裴腾达, 裴炳南. 基于中心解的改进人工蜂群算法[J]. 计算机应用, 2016, 36(4): 1022-1026.
[13]	欧阳秋萍, 李杰, 沈林成. 考虑3G/4G网络特性的多无人机环保监测任务调度[J]. 计算机应用, 2016, 36(3): 871-877.
[14]	刘翱, 邓旭东, 李维刚. 基于模拟退火的混合萤火虫Memetic算法[J]. 计算机应用, 2016, 36(11): 3055-3061.
[15]	程毕芸, 鲁海燕, 徐向平, 沈莞蔷. 求解旅行商问题的改进局部搜索混沌离散粒子群优化算法[J]. 计算机应用, 2016, 36(1): 138-142.