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

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

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

CLC Number:

TP301.6
N945

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.

References

[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.