An Improved Jaya Algorithm for Permutation Flow Shop Scheduling Problem

doi:10.3969/j.issn.1007-7375.2022.03.017

Abstract

Abstract: Permutation flow shop scheduling problem is widely applied in process and discrete manufacturing enterprises. An improved Jaya algorithm is proposed to solve the PFSP with the minimum makespan. In the improved Jaya algorithm, four individual updating schemes based on the best and the worst individuals are proposed, and local search for individuals is carried out through four neighborhood structures. Diversity control strategy is applied to ensure the diversity of population. The improved Jaya algorithm is used to solve the Car, Rec and Taillard benchmark instances, and the experimental results validate the effectiveness of the proposed algorithm.

Key words: permutation flow shop scheduling problem, Jaya algorithm, local search, benchmark problem

CLC Number:

TP18

LIU Mengyi, XUE Yanshe, MA Siyi, ZHANG Chaoyong. An Improved Jaya Algorithm for Permutation Flow Shop Scheduling Problem[J]. Industrial Engineering Journal, 2022, 25(3): 141-150.

References

[1] RUIZ R, STUTZLE T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem[J]. European Journal of Operational Research, 2007, 177: 2033-2049
[2] GOVINDAN K, BALASUNDARAM R, BASKAR N, et al. A hybrid approach for minimizing makespan in permutation flowshop scheduling[J]. Journal of Systems Science and Systems Engineering, 2017, 26(1): 50-76
[3] 汤可宗, 詹堂森, 李佐勇, 等. 一种求解置换流水车间调度问题的多策略粒子群优化[J]. 南京理工大学学报, 2019, 43(1): 48-53
TANG Kezong, ZHAN Tangsen, LI Zuoyong, et al. Multi-strategy particle swarm optimization for solving permutation flow-shop scheduling problem[J]. Journal of Nanjing University of Science and Technology, 2019, 43(1): 48-53
[4] CHEN C L, HUANG S Y, TZENG Y R, et al. A revised discrete particle swarm optimization algorithm for permutation flow-shop scheduling problem[J]. Soft Computing, 2014, 18(11): 2271-2282
[5] 张敏, 汪洋, 方侃. 基于改进区块进化算法求解置换流水车间问题[J]. 计算机集成制造系统, 2018, 24(5): 1207-1216
ZHANG Min, WANG Yang, FANG Kan. Improved block-based evolutionary algorithm for solving permutation flowshop problem[J]. Computer Integrated Manufacturing System, 2018, 24(5): 1207-1216
[6] FERNANDO L R, MARCELO S N, JULIANA K S. An effective constructive heuristic for permutation flow shop scheduling problem with total flow time criterion[J]. The International Journal of Advanced Manufacturing Technology, 2017, 90: 1-4
[7] KARABULUT K. A hybrid iterated greedy algorithm for total tardiness minimization in permutation flowshops[J]. Computers & Industrial Engineering, 2016, 98: 300-307
[8] RAO V R. Jaya: a simple and new optimization algorithm for solving constrained and unconstrained optimization problems[J]. International Journal of Industrial Engineering Computations., 2016, 7(1): 19-34
[9] 潘全科, 高亮, 李新宇. 流水车间调度及其优化算法[M]. 武汉: 华中科技大学出版, 2014.
[10] TASGETIREN M F, LIANG Y C, SEVKLI M, et al. A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem[J]. European Journal of Operational Research, 2007, 177(3): 1930-1947
[11] LIU B, WANG L, JIN Y H. An effective PSO-based memetic algorithm for flow shop scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2007, 37(1): 18-27
[12] LIU Y, YIN M H, GU W X. An effective differential evolution algorithm for permutation flow shop scheduling problem[J]. Applied Mathematics and Computation, 2014, 248: 143-159
[13] MARICHELVAM M K, TOSUN Ö, GEETHA M. Hybrid monkey search algorithm for flow shop scheduling problem under makespan and total flow time[J]. Applied Soft Computing, 2017, 55: 82-92
[14] LAHA D, CHAKRABORTY U K. An efficient hybrid heuristic for makespan minimization in permutation flow shop scheduling[J]. International Journal of Advanced Manufacturing Technology, 2009, 44(5-6): 559-569
[15] MARINAKIS Y, MARINAKI M. Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem[J]. Soft Computing, 2013, 17(7): 1159-1173