求解零等待流水线调度问题的离散磷虾群算法

doi:10.16182/j.issn1004731x.joss.18-0762

系统仿真学报 ›› 2020, Vol. 32 ›› Issue (6): 1051-1059.doi: 10.16182/j.issn1004731x.joss.18-0762

求解零等待流水线调度问题的离散磷虾群算法

刘长平^1,2,3, 简祯富², 傅文翰²

1. 淮阴工学院管理工程学院，江苏淮安 223200;
2. 清华大学工业工程与工程管理系，台湾新竹 30013;
3. 江苏省智能工厂工程研究中心，江苏淮安 223003

收稿日期:2018-11-16 修回日期:2019-05-18 发布日期:2020-06-25
作者简介:刘长平(1974-)，男，河南洛阳，博士，副教授，研究方向为智能优化算法；简祯富(1966-)，男，台湾新竹，博士，教授，博导，研究方向为智能制造，数据挖掘。
基金资助:
国家自然科学基金(71761027)，教育部人文社会科学规划基金(16YJA630032)

A Discrete Krill Herd Algorithm for the No-wait Flow Shop Scheduling Problem

Liu Changping^1,2,3, Jian Zhenfu², Fu Wenhan²

1. Faculty of Management Engineering, Huaiyin Institute of Technology, Huaian 223200, China;
2. Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu 30013, China;
3. Jiangsu Smart Factory Engineering Research Center, Huaian 223003, China

Received:2018-11-16 Revised:2019-05-18 Published:2020-06-25

摘要/Abstract

摘要： 针对最小化最大完工时间零等待流水车间调度问题，设计了一种离散磷虾群优化算法进行求解。根据优化问题特性，定义了算法中虚拟食物的计算方法，规定了虚拟食物影响下磷虾个体之间的交叉规则；提出了个体间的距离计算方式，从而可以界定邻域范围实现个体信息交流；进一步采用交换、逆序、插入等策略来提高算法的局部搜索能力，同时借助多种初始化策略来提高初始种群的质量和多样性。通过典型算例的仿真测试和对比，验证了所设计算法的有效性和鲁棒性。

关键词: 离散磷虾群优化算法, 优化机理, 零等待流水车间调度, 最小化完工时间

Abstract: A discrete krill herd algorithm (DKH) is proposed to solve the no-wait flow shop scheduling problem (NWFSP) with the makespan criterion. Based on the characteristics of the optimization mechanism, the notion of “virtual food” in krill herd algorithm and the influenced crossover rules between krill individuals are defined. The concept and calculation method of the individual distance are redefined to measure the neighborhood range to realize the information exchange. The local search strategies of random swap, inverse and insert operator are employed to enhance the local search ability of DKH, and the multiple initialization strategies are redesigned to promote the qualities and diversities of the initial populations. Simulation results on the benchmark instances shows the effectiveness and robustness of the DKH.

Key words: discrete krill herd optimization, optimization mechanism, no-wait flow shop scheduling, makespan

中图分类号:

TP301.6
N945

刘长平, 简祯富, 傅文翰. 求解零等待流水线调度问题的离散磷虾群算法[J]. 系统仿真学报, 2020, 32(6): 1051-1059.

Liu Changping, Jian Zhenfu, Fu Wenhan. A Discrete Krill Herd Algorithm for the No-wait Flow Shop Scheduling Problem[J]. Journal of System Simulation, 2020, 32(6): 1051-1059.

参考文献

[1] Röck H. The Three-machine No-wait Flow Shop is NP-complete[J]. Journal of the Association for Computing Machinery (S0004-5411), 1984, 31(2): 336-345.
[2] 齐学梅. 无等待流水调度问题迭代启发式算法[J]. 安徽师范大学学报(自然科学版), 2009, 32(1): 4-8.
Qi Xuemei. Iterative Heuristic Algorithms for No-Wait Flowshop Scheduling Problems[J]. Journal of Anhui Normal University (Natural Science), 2009, 32(1): 4-8.
[3] 孙强强, 高开周, 董斌. 一种求解无等待流水车间调度优化的启发式算法[J]. 计算机应用研究, 2012, 29(6): 2072-2073, 2101.
Sun Qiangqiang, Gao Kaizhou, Dong Bin. Heuristic for No-wait Flow Shop Scheduling Optimization[J]. Application Research of Computers, 2012, 29(6): 2072-2073, 2101.
[4] 李亚志, 朱夏. 基于插入-分段的无等待流水作业调度复合启发式算法[J]. 东南大学学报(自然科学版), 2013, 43(3): 483-488.
Li Yazhi, Zhu Xia. Insertion-segment Based Composite Heuristic Algorithm for No-wait Flow Shop Scheduling Problems[J]. Journal of Southeast University (Natural Science Edition), 2013, 43(3): 483-488.
[5] Rani D S, Subrahmanyam N, Sydulu M. A Hybrid Particle Swarm Optimization Algorithm for a No-wait Flow Shop Scheduling Problem with the Total Flow Time[J]. International Journal of Advanced Manufacturing Technology (S0268-3768), 2014, 70(5/8): 1181-1188.
[6] Gao K Z, Suganthan P N, Pan Q K. Discrete Harmony Search Algorithm for Flexible Job Shop Scheduling Problem with Multiple Objectives[J]. Journal of Intelligent Manufacturing (S0956-5515), 2016, 27(2): 363-374.
[7] Sundar S, Suganthan P N, Jin C T, et al. A Hybrid Artificial Bee Colony Algorithm for the Job-shop Scheduling Problem with No-wait Constraint[J]. Soft Computing (S1432-7643), 2017, 21(5): 1193-1202.
[8] 齐学梅, 王宏涛, 杨洁, 等. 量子萤火虫算法及在无等待流水调度上的应用[J]. 信息与控制, 2017, 45(2): 211-217.
Qi Xuemei, Wang Hongtong, Yang Jie, et al. Quantum Glowworm Swarm Algorithm and Its Application to No-wait Flowshop Scheduling[J]. Information and Control, 2017, 45(2): 211-217.
[9] 张其亮, 俞祚明. 基于优势种群的离散果蝇优化算法求解无等待流水车间调度问题[J]. 计算机集成制造系统, 2017, 23(3): 609-615.
Zhang Qiliang, Yu Zuoming. Discrete Fruit Fly Optimization Algorithm Based on Dominant Population for Solving No-wait Flow Shop Scheduling Problem[J]. Computer Integrated Manufacturing Systems, 2017, 23(3): 609-615.
[10] Gandomi A H, Alavi A H. Krill Herd: A New Bio-inspired Optimization Algorithm[J]. Communications in Nonlinear Science and Numerical Simulation (S1007-5704), 2012, 17(12): 4831-4845.
[11] Wang G, Guo L, Wang H, et al. Incorporating Mutation Scheme into Krill Herd Algorithm for Global Numerical Optimization[J]. Neural Computing and Applications (S0941-0643), 2014, 24(3/4): 853-871.
[12] Wang G G, Gandomi A H, Alavi A H. Stud Krill Herd Algorithm[J]. Neurocomputing (S0925-2312), 2014, 128(5): 363-370.
[13] Wang G G, Gandomi A H, Alavi A H, et al. A Hybrid Method Based on Krill Herd and Quantum-behaved Particle Swarm Optimization[J]. Neural Computing & Applications (S0941-0643), 2016, 27(4): 989-1006.
[14] Bolaji A L, Al-Betar M A, Awadallah M A, et al. A Comprehensive Review: Krill Herd Algorithm (KH) and its Applications[J]. Applied Soft Computing (S1568-4946), 2016, 49: 437-446.
[15] Nawaz M, Enscore J, Ham I. A Heuristic Algorithm for the M-machine, N-job Flow-shop Sequencing Problem[J]. Omega(S0305-0483), 1983, 11(1): 91-95.
[16] Campbell H G, Dudek R A, Smith M L. A Heuristic Algorithm for the n Job, m Machine Sequencing Problem[J]. Management Science (S0025-1909), 1970, 16(10): 630-637.
[17] Rajendran C. A No-wait Flowshop Scheduling Heuristic to Minimize Makespan[J]. Journal of the Operational Research Society (S0160-5682), 1994, 45(4): 472-478.
[18] Carlier J. Scheduling with Disjunctive Constraints[J]. Operations Research (S0030-364X), 1978, 12(4): 333-350.
[19] Reeves C R. A Genetic Algorithm for Flowshop Sequencing[J]. Computers and Operations Research (S0305-0548), 1995, 22(1): 5-13.
[20] Heller J. Some Numerical Experiments for an M×J Flow Shop and its Decision-theoretical Aspects[J]. Operations Research (S0030-364X), 1960, 8(2): 178-184.
[21] Schuster C J, Framinan J M. Approximative Procedures for No-wait Job Shop Scheduling[J]. Operations Research Letters (S0167-6377), 2003, 31(4): 308-318.
[22] Tasgetiren M F, Sevkli M, Liang Y C, et al. Particle Swarm Optimization Algorithm for Permutation Flowshop Sequencing Problem[J]. Lecture Notes in Computer Science (S0302-9743), 2004, 3172(14): 382-389.
[23] Pan Q K, Fatih Tasgetiren M, Liang Y C. A Discrete Particle Swarm Optimization Algorithm for the No-wait Flowshop Scheduling Problem[J]. Computers and Operations Research (S0305-0548), 2008, 35(9): 2807-2839.

求解零等待流水线调度问题的离散磷虾群算法

A Discrete Krill Herd Algorithm for the No-wait Flow Shop Scheduling Problem

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	邓向阳, 张立民, 方伟, 汤淼. 基于双向汇聚引导蚁群算法的机器人路径规划[J]. 系统仿真学报, 2022, 34(5): 1101-1108.
[2]	李建锋, 卢迪, 李贺香. 一种改进的原子搜索算法[J]. 系统仿真学报, 2022, 34(3): 490-502.
[3]	董君, 叶春明. 半导体晶圆节能分布式制造与预维护联合优化[J]. 系统仿真学报, 2022, 34(3): 584-602.
[4]	王付宇, 汤涛. 双种群鱼群算法在分布式投资组合的应用[J]. 系统仿真学报, 2021, 33(9): 2074-2084.
[5]	刘景森, 袁蒙蒙, 李煜. 基于改进樽海鞘群算法求解工程优化设计问题[J]. 系统仿真学报, 2021, 33(4): 854-866.
[6]	顾菊平, 程天宇, 王建平, 华亮, 赵凤申, 蒋凌. 基于几何特征不变量的快速3D医学图像配准[J]. 系统仿真学报, 2020, 32(11): 2105-2111.
[7]	陆湛文, 程新功, 张永峰. 基于共识粒子群的全局优化求解方法[J]. 系统仿真学报, 2020, 32(10): 1936-1942.
[8]	刘长良, 王梓齐. 基于严格二叉树编码和GA的模糊树结构学习[J]. 系统仿真学报, 2020, 32(8): 1473-1480.
[9]	刘景森, 刘晓珍, 李煜. 具有动态步长和发现概率的布谷鸟搜索算法[J]. 系统仿真学报, 2020, 32(2): 289-298.
[10]	顾菊平, 程天宇, 华亮, 王建平, 赵剑, 曹涌. 面向脊柱生物建模的图像分割与配准研究综述[J]. 系统仿真学报, 2019, 31(2): 167-173.
[11]	陆秋琴, 黄光球. 捕食-被食动力学优化算法[J]. 系统仿真学报, 2018, 30(10): 3975-3984.
[12]	李荣雨, 梁栋, 戚桂洪. 基于自适应反馈机制的精英教学优化算法[J]. 系统仿真学报, 2018, 30(8): 2950-2957.
[13]	李琦, 赵峰. 基于气温与日期类型的改进BP网络热负荷预测[J]. 系统仿真学报, 2018, 30(4): 1464-1472.
[14]	刘长良, 王鹏飞, 刘帅, 罗磊, 回振桥. 一种改进的CS算法及其在微电网优化中的应用[J]. 系统仿真学报, 2018, 30(3): 930-936.
[15]	肖辉辉, 段艳明. 具有入侵杂草策略的花朵授粉算法[J]. 系统仿真学报, 2017, 29(2): 264-272.