AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Complex System Modeling and Simulation Article
PDF (1.1 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Distributed Flexible Job-Shop Scheduling Problem Based on Hybrid Chemical Reaction Optimization Algorithm

Jialei Li1, Xingsheng Gu1( ), Yaya Zhang1, Xin Zhou1
Laboratory of Smart Manufacturing in Energy Chemical Process, Ministry of Education, East China University of Science and Technology, Shanghai 200237, China
Show Author Information

Abstract

Economic globalization has transformed many manufacturing enterprises from a single-plant production mode to a multi-plant cooperative production mode. The distributed flexible job-shop scheduling problem (DFJSP) has become a research hot topic in the field of scheduling because its production is closer to reality. The research of DFJSP is of great significance to the organization and management of actual production process. To solve the heterogeneous DFJSP with minimal completion time, a hybrid chemical reaction optimization (HCRO) algorithm is proposed in this paper. Firstly, a novel encoding-decoding method for flexible manufacturing unit (FMU) is designed. Secondly, half of initial populations are generated by scheduling rule. Combined with the new solution acceptance method of simulated annealing (SA) algorithm, an improved method of critical-FMU is designed to improve the global and local search ability of the algorithm. Finally, the elitist selection strategy and the orthogonal experimental method are introduced to the algorithm to improve the convergence speed and optimize the algorithm parameters. In the experimental part, the effectiveness of the simulated annealing algorithm and the critical-FMU refinement methods is firstly verified. Secondly, in the comparison with other existing algorithms, the proposed optimal scheduling algorithm is not only effective in homogeneous FMUs examples, but also superior to existing algorithms in heterogeneous FMUs arithmetic cases.

Keywords

simulated annealing algorithmscheduling problemdistributed flexible job-shopchemical reaction optimization algorithmheterogeneous factory

References

1

H. J. Ding and X. S. Gu, Improved particle swarm optimization algorithm based novel encoding and decoding schemes for flexible job shop scheduling problem, Computers&Operations Research, vol. 121, p. 104951, 2020.
Crossref Google Scholar
2

K. Z. Gao, Z. G. Cao, L. Zhang, Z. H. Chen, Y. Y. Han, and Q. K. Pan, A review on swarm intelligence and evolutionary algorithms for solving flexible job shop scheduling problems, IEEE/CAA Journal of Automatica Sinica, vol. 6, no. 4, pp. 904–916, 2019.
Crossref Google Scholar
3

K. Z. Gao, F. J. Yang, M. C. Zhou, Q. K. Pan, and P. N. Suganthan, Flexible job-shop rescheduling for new job insertion by using discrete jaya algorithm, IEEE Transactions on Cybernetics, vol. 49, no. 5, pp. 1944–1955, 2019.
Crossref Google Scholar
4

R. L. Burdett, P. Corry, P. K. D. V. Yarlagadda, C. Eustace, and S. Smith, A flexible job shop scheduling approach with operators for coal export terminals, Computers&Operations Research, vol. 104, pp. 15–36, 2019.
Crossref Google Scholar
5

D. Deliktas, O. Torkul, and O. Ustun, A flexible job shop cell scheduling with sequence-dependent family setup times and intercellular transportation times using conic scalarization method, International Transactions in Operational Research, vol. 26, no. 6, pp. 2410–2431, 2019.
Crossref Google Scholar
6

Q. W. Deng, G. L. Gong, X. R. Gong, L. K. Zhang, W. Liu, and Q. H. Ren, A bee evolutionary guiding nondominated sorting genetic algorithm II for multiobjective flexible job-shop scheduling, Computational Intelligence&Neuroscience, vol. 2017, p. 5232518, 2017.
Crossref Google Scholar
7

G. L. Gong, Q. W. Deng, R. Chiong, X. Gong, and H. Z. Y. Huang, An effective memetic algorithm for multi-objective job-shop scheduling, Knowledge-Based Systems, vol. 182, p. 104840, 2019.
Crossref Google Scholar
8

I. Chaouch, O. B. Driss, and K. Ghedira, A novel dynamic assignment rule for the distributed job shop scheduling problem using a hybrid ant-based algorithm, Applied Intelligence, vol. 49, no. 5, pp. 1903–1924, 2019.
Crossref Google Scholar
9

Q. K. Pan, L. Gao, L. Wang, J. Liang, and X. Y. Li, Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem, Expert Systems with Applications, vol. 124, pp. 309–324, 2019.
Crossref Google Scholar
10

J. Q. Li, M. X. Song, L. Wang, P. Y. Duan, Y. Y. Han, H. Y. Sang, and Q. K. Pan, Hybrid artificial bee colony algorithm for a parallel batching distributed flow-shop problem with deteriorating jobs, IEEE Transactions on Cybernetics, vol. 50, no. 6, pp. 2425–2439, 2020.
Crossref Google Scholar
11
S. C. Zhang, X. Li, B. W. Zhang, and S. Y. Wang, Multi-objective optimisation in flexible assembly job shop scheduling using a distributed ant colony system, European Journal of Operational Research, vol. 283, no. 2, pp. 441–460, 2020.https://doi.org/10.1016/j.ejor.2019.11.016
Crossref
12

J. Zheng, L. Wang, and J. J. Wang, A cooperative coevolution algorithm for multi-objective fuzzy distributed hybrid flow shop, Knowledge-Based Systems, vol. 194, p. 105536, 2020.
Crossref Google Scholar
13

J. Q. Li, P. Y. Duan, J. D. Cao, X. P. Lin, and Y. Y. Han, A hybrid Pareto-based tabu search for the distributed flexible job shop scheduling problem with E/T criteria, IEEE Access, vol. 6, no. 99, pp. 58883–58897, 2018.
Crossref Google Scholar
14

F. T. S. Chan, S. H. Chung, and P. L. Y. Chan, Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems, International Journal of Production Research, vol. 44, no. 3, pp. 523–543, 2006.
Crossref Google Scholar
15
L. D. Giovanni and F. Pezzella, An improved genetic algorithm for the distributed and flexible job-shop scheduling problem, European Journal of Operational Research, vol. 200, no. 2, pp. 395–408, 2010.https://doi.org/10.1016/j.ejor.2009.01.008
Crossref
16
M. Ziaee, A heuristic algorithm for the distributed and flexible job-shop scheduling problem, Journal of Supercomputing, vol. 67, no. 1, pp. 69–83, 2014.https://doi.org/10.1007/s11227-013-0986-8
Crossref
17
P. H. Lu, M. C. Wu, H. Tan, Y. H. Peng, and C. F. Chen, A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems, Journal of Intelligent Manufacturing, vol. 29, no. 1, pp. 19–34, 2018.https://doi.org/10.1007/s10845-015-1083-z
Crossref
18

H. C. Chang and T. K. Liu, Optimisation of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms, Journal of Intelligent Manufacturing, vol. 28, no. 8, pp. 1973–1986, 2017.
Crossref Google Scholar
19

M. C. Wu, C. S. Lin, C. H. Lin, and C. F. Chen, Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems, Computers&Operations Research, vol. 80, pp. 101–112, 2017.
Crossref Google Scholar
20
B. Marzouki, O. B. Driss, and K. Ghédira, Solving distributed and flexible job shop scheduling problem using a chemical reaction optimization metaheuristic, Procedia Computer Science, vol. 126, no. 1, pp. 1424–1433, 2018.https://doi.org/10.1016/j.procs.2018.08.114
Crossref
21

F. T. S. Chan, S. H. Chung, L. Y. Chan, G. Finke, and M. K. Tiwari, Solving distributed FMS scheduling problems subject to maintenance: Genetic algorithms approach, Robotics and Computer-Integrated Manufacturing, vol. 22, nos. 5&6, pp. 493–504, 2006.
Crossref Google Scholar
22

S. H. Chung, F. T. S. Chan, and H. K. Chan, A modified genetic algorithm approach for scheduling of perfect maintenance in distributed production scheduling, Engineering Applications of Artificial Intelligence, vol. 22, no. 7, pp. 1005–1014, 2009.
Crossref Google Scholar
23
C. S. Lin, I. L. Lee, and M. C. Wu, Merits of using chromosome representations and shadow chromosomes in genetic algorithms for solving scheduling problems, Robotics and Computer-Integrated Manufacturing, vol. 58, no. 1, pp. 196–207, 2019.https://doi.org/10.1016/j.rcim.2019.01.005
Crossref
24

F. T. S. Chan, A. Prakash, H. L. Ma, and C. S. Wong, A hybrid tabu sample-sort simulated annealing approach for solving distributed scheduling problem, International Journal of Production Research, vol. 51, no. 9, pp. 2602–2619, 2013.
Crossref Google Scholar
25
M. Ziaee, Modeling and solving the distributed and flexible job shop scheduling problem with WIPs supply planning and bounded processing times, International Journal of Supply and Operations Management, vol. 4, no. 1, pp. 78–89, 2017.
26

Q. Luo, Q. W. Deng, G. L. Gong, L. K. Zhang, W. W. Han, and K. X. Li, An efficient memetic algorithm for distributed flexible job shop scheduling problem with transfers, Expert Systems with Applications, vol. 160, p. 113721, 2020.
Crossref Google Scholar
27

W. X. Xu, Y. W. Hu, W. Luo, L. Wang, and R. Wu, A multi-objective scheduling method for distributed and flexible job shop based on hybrid genetic algorithm and tabu search considering operation outsourcing and carbon emission, Computers&Industrial Engineering, vol. 157, p. 107318, 2021.
Crossref Google Scholar
28

Y. Du, J. Q. Li, C. Luo, and L. L. Meng, A hybrid estimation of distribution algorithm for distributed flexible job shop scheduling with crane transportations, Swarm and Evolutionary Computation, vol. 62, p. 100861, 2021.
Crossref Google Scholar
29

F. Q. Zhao, L. X. Zhao, L. Wang, and H. B. Song, An ensemble discrete differential evolution for the distributed blocking flowshop scheduling with minimizing makespan criterion, Expert Systems with Applications, vol. 160, p. 113678, 2020.
Crossref Google Scholar
30

F. Q. Zhao, X. He, and L. Wang, A two-stage cooperative evolutionary algorithm with problem-specific knowledge for energy-efficient scheduling of no-wait flow-shop problem, IEEE Transactions on Cybernetics, vol. 51, no. 11, pp. 5291–5303, 2020.
Crossref Google Scholar
31
F. Q. Zhao, R. Ma, and L. Wang, A self-learning discrete jaya algorithm for multiobjective energy-efficient distributed no-idle flow-shop scheduling problem in heterogeneous factory system, IEEE Transactions on Cybernetics, doi: 10.1109/TCYB.2021.3086181.https://doi.org/10.1109/TCYB.2021.3086181
Crossref
32

G. C. Wang, X. Y. Li, L. Gao, and P. G. Li, A multi-objective whale swarm algorithm for energy-efficient distributed permutation flow shop scheduling problem with sequence dependent setup times, IFAC-PapersOnLine, vol. 52, no. 13, pp. 235–240, 2019.
Crossref Google Scholar
33
D. M. Lei, Y. Yuan, J. C. Cai, and D. Y. Bai, An imperialist competitive algorithm with memory for distributed unrelated parallel machines scheduling, International Journal of Production Research, vol. 58, no. 2, pp. 597–614, 2020.https://doi.org/10.1080/00207543.2019.1598596
Crossref
34

D. M. Lei, Y. Yuan, and J. C. Cai, An improved artificial bee colony for multi-objective distributed unrelated parallel machine scheduling, International Journal of Production Research, vol. 59, no. 17, pp. 5259–5271, 2021.
Crossref Google Scholar
35

M. A. Şahman, A discrete spotted hyena optimizer for solving distributed job shop scheduling problems, Applied Soft Computing, vol. 106, p. 107349, 2021.
Crossref Google Scholar
36

A. Y. S. Lam and V. O. K. Li, Chemical-reaction-inspired metaheuristic for optimization, IEEE Transactions on Evolutionary Computation, vol. 14, no. 3, pp. 381–399, 2010.
Crossref Google Scholar
37

Y. M. Xu, K. L. Li, L. G. He, and T. K. Truong, A DAG scheduling scheme on heterogeneous computing systems using double molecular structure-based chemical reaction optimization, Journal of Parallel and Distributed Computing, vol. 73, no. 9, pp. 1306–1322, 2013.
Crossref Google Scholar
38

T. K. Truong, K. L. Li, and Y. M. Xu, Chemical reaction optimization with greedy strategy for the 0–1 knapsack problem, Applied Soft Computing, vol. 13, no. 4, pp. 1774–1780, 2013.
Crossref Google Scholar
39
J. Q. Li and Q. K. Pan, Chemical-reaction optimization for solving fuzzy job-shop scheduling problem with flexible maintenance activities, International Journal of Production Economics, vol. 145, no. 1, pp. 4–17, 2013.https://doi.org/10.1016/j.ijpe.2012.11.005
Crossref
40

B. Marzouki, O. B. Driss, and K. Ghédira, Multi agent model based on chemical reaction optimization with greedy algorithm for flexible job shop scheduling problem, Procedia Computer Science, vol. 112, no. C, pp. 81–90, 2017.
Crossref Google Scholar
41

H. Bargaoui, O. B. Driss, and K. Ghédira, A novel chemical reaction optimization for the distributed permutation flowshop scheduling problem with makespan criterion, Computers&Industrial Engineering, vol. 111, no. C, pp. 239–250, 2017.
Crossref Google Scholar
42

H. Bargaoui, O. B. Driss, and K. Ghédira, Towards a distributed implementation of chemical reaction optimization for the multi-factory permutation flowshop scheduling problem, Procedia Computer Science, vol. 112, pp. 1531–1541, 2017.
Crossref Google Scholar
43

R. Wu, S. S. Guo, Y. B. Li, L. Wang, and W. X. Xu, Improved artificial bee colony algorithm for distributed and flexible job-shop scheduling problem, (in Chinese), Control and Decision, vol. 34, no. 12, pp. 2527–2536, 2019.
Google Scholar
44

H. J. Xiao, Z. L. Chai, C. Y. Zhang, L. L. Meng, Y. P. Ren, and H. W. Mei, Hybrid chemical-reaction optimization and tabu search for flexible job shop scheduling problem, (in Chinese), Computer Integrated Manufacturing Systems, vol. 24, no. 9, pp. 2234–2245, 2018.
Google Scholar
45

C. Bierwirth, A generalized permutation approach to job shop scheduling with genetic algorithms, OR Spectrum, vol. 17, pp. 87–92, 1995.
Crossref Google Scholar
46

X. Han, Y. Y. Han, Q. D. Chen, J. Q. Li, H. Y. Sang, Y. P. Liu, Q. K. Pan, and Y. S. Nojima, Distributed flow shop scheduling with sequence-dependent setup times using an improved iterated greedy algorithm, Complex System Modeling and Simulation, vol. 1, no. 3, pp. 198–217, 2021.
Crossref Google Scholar
47

S. P. Brooks and B. J. T. Morgan, Optimization using simulated annealing, Journal of the Royal Statistical Society: Series D (The Statistician), vol. 44, no. 2, pp. 241–257, 1995.
Crossref Google Scholar
48
L. Hernández-Ramírez, J. Frausto-Solis, G. Castilla-Valdez, J. J. Gonzalez-Barbosa, D. Teran-Villanueva, and M. L. Morales-Rodriguez, A hybrid simulated annealing for job shop scheduling problem, International Journal of Combinatorial Optimization Problems & Informatics, vol. 10, no. 1, pp. 6–15, 2019.
49

C. Ramesh, R. Kamalakannan, R. Karthik, C. Pavin, and S. Dhivaharan, A lot streaming based flow shop scheduling problem using simulated annealing algorithm, Materials Today:Proceedings, vol. 37, pp. 241–244, 2021.
Crossref Google Scholar
50

M. Wang, L. M. Liu, and K. Y. Song, Analysis of flexible shop scheduling problem based on a genetic simulated annealing algorithm, AIP Conference Proceedings, vol. 2258, no. 1, p. 020016, 2020.
Crossref Google Scholar
Complex System Modeling and Simulation
Volume 2 Issue 2,
June 2022
Pages 156-173
DOI: 10.23919/CSMS.2022.0010
Cite this article:
Li J, Gu X, Zhang Y, et al. Distributed Flexible Job-Shop Scheduling Problem Based on Hybrid Chemical Reaction Optimization Algorithm. Complex System Modeling and Simulation, 2022, 2(2): 156-173. https://doi.org/10.23919/CSMS.2022.0010

967

Views

41

Downloads

9

Crossref

10

Scopus

Altmetrics
Received: 29 March 2022
Revised: 08 June 2022
Accepted: 20 June 2022
Published: 30 June 2022
© The author(s) 2022

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