Journal Home > Volume 1 , Issue 3
Complex System Modeling and Simulation 2021, 1(3): 176-197 https://doi.org/10.23919/CSMS.2021.0017
Open Access | Issue | Published: 29 October 2021

Multidirection Update-Based Multiobjective Particle Swarm Optimization for Mixed No-Idle Flow-Shop Scheduling Problem

Show Author's Information Wenqiang Zhang1( ),  Wenlin Hou1,  Chen Li1,  Weidong Yang1,  Mitsuo Gen2
College of Information Science and Engineering, Henan University of Technology, and also with Henan Key Laboratory of Grain Photoelectric Detection and Control, Zhengzhou 450001, China
Fuzzy Logic Systems Institute, Fukuoka 820-0067, Japan, and also with Tokyo University of Science, Tokyo 162-8601, Japan
Keywords:
Particle Swarm Optimization (PSO), multiobjective optimization, Mixed No-Idle Flow-shop Scheduling Problem (MNLFSP), multidirection update
Cite this article:
Zhang W, Hou W, Li C, et al. Multidirection Update-Based Multiobjective Particle Swarm Optimization for Mixed No-Idle Flow-Shop Scheduling Problem. Complex System Modeling and Simulation, 2021, 1(3): 176-197. https://doi.org/10.23919/CSMS.2021.0017
Download citation
EndNote(RIS)
BibTeX

5676

Views

58

Downloads

Citations

32

Crossref

N/A

WoS

31

Scopus

N/A

CSCD

Abstract Full text About this article

The Mixed No-Idle Flow-shop Scheduling Problem (MNIFSP) is an extension of flow-shop scheduling, which has practical significance and application prospects in production scheduling. To improve the efficacy of solving the complicated multiobjective MNIFSP, a MultiDirection Update (MDU) based Multiobjective Particle Swarm Optimization (MDU-MoPSO) is proposed in this study. For the biobjective optimization problem of the MNIFSP with minimization of makespan and total processing time, the MDU strategy divides particles into three subgroups according to a hybrid selection mechanism. Each subgroup prefers one convergence direction. Two subgroups are individually close to the two edge areas of the Pareto Front (PF) and serve two objectives, whereas the other one approaches the central area of the PF, preferring the two objectives at the same time. The MDU-MoPSO adopts a job sequence representation method and an exchange sequence-based particle update operation, which can better reflect the characteristics of sequence differences among particles. The MDU-MoPSO updates the particle in multiple directions and interacts in each direction, which speeds up the convergence while maintaining a good distribution performance. The experimental results and comparison of six classical evolutionary algorithms for various benchmark problems demonstrate the effectiveness of the proposed algorithm.


menu
Abstract
Full text
Outline
About this article

Multidirection Update-Based Multiobjective Particle Swarm Optimization for Mixed No-Idle Flow-Shop Scheduling Problem

Show Author's information Wenqiang Zhang1( ), Wenlin Hou1, Chen Li1, Weidong Yang1, Mitsuo Gen2
College of Information Science and Engineering, Henan University of Technology, and also with Henan Key Laboratory of Grain Photoelectric Detection and Control, Zhengzhou 450001, China
Fuzzy Logic Systems Institute, Fukuoka 820-0067, Japan, and also with Tokyo University of Science, Tokyo 162-8601, Japan

Abstract

The Mixed No-Idle Flow-shop Scheduling Problem (MNIFSP) is an extension of flow-shop scheduling, which has practical significance and application prospects in production scheduling. To improve the efficacy of solving the complicated multiobjective MNIFSP, a MultiDirection Update (MDU) based Multiobjective Particle Swarm Optimization (MDU-MoPSO) is proposed in this study. For the biobjective optimization problem of the MNIFSP with minimization of makespan and total processing time, the MDU strategy divides particles into three subgroups according to a hybrid selection mechanism. Each subgroup prefers one convergence direction. Two subgroups are individually close to the two edge areas of the Pareto Front (PF) and serve two objectives, whereas the other one approaches the central area of the PF, preferring the two objectives at the same time. The MDU-MoPSO adopts a job sequence representation method and an exchange sequence-based particle update operation, which can better reflect the characteristics of sequence differences among particles. The MDU-MoPSO updates the particle in multiple directions and interacts in each direction, which speeds up the convergence while maintaining a good distribution performance. The experimental results and comparison of six classical evolutionary algorithms for various benchmark problems demonstrate the effectiveness of the proposed algorithm.

Keywords: Particle Swarm Optimization (PSO), multiobjective optimization, Mixed No-Idle Flow-shop Scheduling Problem (MNLFSP), multidirection update

References(37)

[1]

S. M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Logist. Quart., vol. 1, no. 1, pp. 61–68, 1954.
DOI Google Scholar
[2]

Q. K. Pan and R. Ruiz, An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem, Omega, vol. 44, pp. 41–50, 2014.
DOI Google Scholar
[3]

M. R. Garey, D. S. Johnson, and R. Sethi, The complexity of flowshop and jobshop scheduling, Math. Oper. Res., vol. 1, no. 2, pp. 117–129, 1976.
DOI Google Scholar
[4]

C. Y. Cheng, K. C. Ying, H. H. Chen, and H. S. Lu, Minimising makespan in distributed mixed no-idle flowshops, Int.J. Product. Res., vol. 57, no. 1, pp. 48–60, 2019.
DOI Google Scholar
[5]
R. Eberhart and J. Kennedy, A new optimizer using particle swarm theory, in Proc. of MHS’95. 6th Int. Symp. Micro Machine and Human Science, Nagoya, Japan, 1995, pp. 39–43.
[6]

Y. D. Valle, G. K. Venayagamoorthy, S. Mohagheghi, J. C. Hernandez, and R. G. Harley, Particle swarm optimization: Basic concepts, variants and applications in power systems, IEEE Trans. Evol. Comput., vol. 12, no. 2, pp. 171–195, 2008.
DOI Google Scholar
[7]
C. A. C. Coello and M. S. Lechuga, MOPSO: A proposal for multiple objective particle swarm optimization, in Proc. 2002 Congress on Evolutionary Computation, CEC’02 (Cat. No.02TH8600), Honolulu, HI, USA, 2002, pp. 1051–1056.
[8]

C. A. C. Coello, G. T. Pulido, and M. S. Lechuga, Handling multiple objectives with particle swarm optimization, IEEE Trans. Evol. Computat., vol. 8, no. 3, pp. 256–279, 2004.
DOI Google Scholar
[9]

Z. H. Zhan, J. J. Li, J. N. Cao, J. Zhang, H. S. H. Chung, and Y. H. Shi, Multiple populations for multiple objectives: A coevolutionary technique for solving multiobjective optimization problems, IEEE Trans. Cybern., vol. 43, no. 2, pp. 445–463, 2013.
DOI Google Scholar
[10]

N. Al Moubayed, A. Petrovski, and J. McCall, D2MOPSO: MOPSO based on decomposition and dominance with archiving using crowding distance in objective and solution spaces, Evol. Comput., vol. 22, no. 1, pp. 47–77, 2014.
DOI Google Scholar
[11]
J. D. Schaffer, Multiple objective optimization with vector evaluated genetic algorithms, in Proc. 1st Int. Conf. Genetic Algorithms, Pittsburgh, PA, USA, 1985, pp. 93–100.
[12]

W. Q. Zhang, M. Gen, and J. Jo, Hybrid sampling strategybased multiobjective evolutionary algorithm for process planning and scheduling problem, J. Intell. Manuf., vol. 25, no. 5, pp. 881–897, 2014.
DOI Google Scholar
[13]

T. Bektaş, A. Hamzadayi, and R. Ruiz, Benders decomposition for the mixed no-idle permutation flowshop scheduling problem, J. Sched., vol. 23, no. 4, pp. 513–523, 2020.
DOI Google Scholar
[14]

F. L. Rossi and M. S. Nagano, Heuristics for the mixed no-idle flowshop with sequence-dependent setup times and total flowtime criterion, Expert Syst. Appl., vol. 125, pp. 40–54, 2019.
DOI Google Scholar
[15]

F. L. Rossi and M. S. Nagano, Heuristics for the mixed no-idle flowshop with sequence-dependent setup times, J. Oper. Res. Soc., vol. 72, no. 2, pp. 417–443, 2021.
DOI Google Scholar
[16]

F. L. Rossi and M. S. Nagano, Heuristics and metaheuristics for the mixed no-idle flowshop with sequence-dependent setup times and total tardiness minimisation, Swarm Evol. Comput., vol. 55, p. 100689, 2020.
DOI Google Scholar
[17]

M. S. Nagano, F. L. Rossi, and N. J. Martarelli, Highperforming heuristics to minimize flowtime in no-idle permutation flowshop, Eng. Optimiz., vol. 51, no. 2, pp. 185–198, 2019.
DOI Google Scholar
[18]

K. C. Ying, S. W. Lin, C. Y. Cheng, and C. D. He, Iterated reference greedy algorithm for solving distributed no-idle permutation flowshop scheduling problems, Comput. Ind. Eng., vol. 110, pp. 413–423, 2017.
DOI Google Scholar
[19]

V. Riahi, R. Chiong, and Y. L. Zhang, A new iterated greedy algorithm for no-idle permutation flowshop scheduling with the total tardiness criterion, Comput. Oper. Res., vol. 117, p. 104839, 2020.
DOI Google Scholar
[20]

G. L. Deng and X. S. Gu, A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion, Comput. Oper. Res., vol. 39, no. 9, pp. 2152–2160, 2012.
DOI Google Scholar
[21]

W. S. Shao, D. C. Pi, and Z. S. Shao, Memetic algorithm with node and edge histogram for no-idle flow shop scheduling problem to minimize the makespan criterion, Appl. Soft Comput., vol. 54, pp. 164–182, 2017.
DOI Google Scholar
[22]

W. S. Shao, D. C. Pi, and Z. S. Shao, A hybrid discrete teaching-learning based meta-heuristic for solving no-idle flow shop scheduling problem with total tardiness criterion, Comput. Oper. Res., vol. 94, pp. 89–105, 2018.
DOI Google Scholar
[23]

J. F. Chen, L. Wang, and Z. P. Peng, A collaborative optimization algorithm for energy-efficient multi-objective distributed no-idle flow-shop scheduling, Swarm Evol. Comput., vol. 50, p. 100557, 2019.
DOI Google Scholar
[24]

F. Q. Zhao, L. X. Zhang, Y. Zhang, W. M. Ma, C. Zhang, and H. B. Song, A hybrid discrete water wave optimization algorithm for the no-idle flowshop scheduling problem with total tardiness criterion, Expert Syst. Appl., vol. 146, p. 113166, 2020.
DOI Google Scholar
[25]

Q. K. Pan and L. Wang, No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm, Int.J. Adv. Manuf. Technol., vol. 39, no. 7, pp. 796–807, 2008.
Google Scholar
[26]

L. A. Bewoor, V. C. Prakash, and S. U. Sapkal, Evolutionary particle swarm optimization algorithm hybrid for solving NP-hard no-wait flow shop scheduling problems, Algorithms, vol. 10, no. 4, p. 121, 2017.
DOI Google Scholar
[27]
N. Nouha and L. Talel, A particle swarm optimization metaheuristic for the blocking flow shop scheduling problem: Total tardiness minimization, in Proc. of 13th European Conf., EUMAS 2015, and Third Int. Conf. Multi-Agent Systems and Agreement Technologies, Athens, Greece, 2015, pp. 145–153.
[28]

M. Eddaly, B. Jarboui, and P. Siarry, Combinatorial particle swarm optimization for solving blocking flowshop scheduling problem, J. Comput. Des. Eng., vol. 3, no. 4, pp. 295–311, 2016.
Google Scholar
[29]

B. Jiao and S. Yan, A niche sharing scheme-based coevolutionary particle swarm optimization algorithm for flow shop scheduling problem, Syst. Cybernet. Informat., vol. 15, no. 3, pp. 46–54, 2017.
Google Scholar
[30]

H. Mokhtari and A. Noroozi, An efficient chaotic based PSO for earliness/tardiness optimization in a batch processing flow shop scheduling problem, J. Intell. Manuf., vol. 29, no. 5, pp. 1063–1081, 2018.
DOI Google Scholar
[31]

Y. X. Su and R. Chi, Multi-objective particle swarmdifferential evolution algorithm, Neural Comput. Appl., vol. 28, no. 2, pp. 407–418, 2017.
DOI Google Scholar
[32]

Z. H. Cui, J. J. Zhang, D. Wu, X. J. Cai, H. Wang, W. S. Zhang, and J. J. Chen, Hybrid many-objective particle swarm optimization algorithm for green coal production problem, Informat. Sci., vol. 518, pp. 256–271, 2020.
DOI Google Scholar
[33]

W. Q. Zhang, D. J. Yang, G. H. Zhang, and M. Gen, Hybrid multiobjective evolutionary algorithm with fast sampling strategy-based global search and route sequence differencebased local search for VRPTW, Expert Syst. Appl., vol. 145, p. 113151, 2020.
DOI Google Scholar
[34]

K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ, IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, 2002.
DOI Google Scholar
[35]
E. Zitzler, M. Laumanns, and L. Thiele, SPEA2: Improving the strength Pareto evolutionary algorithm, Technical Report Gloriastrasse, doi: 10.3929/ethz-a-004284029.
[36]

Q. F. Zhang and H. Li, MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., vol. 11, no. 6, pp. 712–731, 2007.
DOI Google Scholar
[37]

W. Q. Zhang, Y. Wang, Y. Yang, and M. Gen, Hybrid multiobjective evolutionary algorithm based on differential evolution for flow shop scheduling problems, Comput. Ind. Eng., vol. 130, pp. 661–670, 2019.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 09 April 2021
Revised: 01 July 2021
Accepted: 14 August 2021
Published: 29 October 2021
Issue date: September 2021

Copyright

© The author(s) 2021

Acknowledgements

Acknowledgements

This work was partly supported by the National Natural Science Foundation of China (No. 61772173), the Science and Technology Research Project of Henan Province (No. 202102210131), the Innovative Funds Plan of Henan University of Technology (No. 2020ZKCJ02), and the Grant-in-Aid for Scientific Research (C) of Japan Society of Promotion of Science (No. 19K12148).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return