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 Tsinghua Science and Technology Article
PDF (11.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

Flexible Job Shop Composite Dispatching Rule Mining Approach Based on an Improved Genetic Programming Algorithm

Hubei Key Laboratory of Modern Manufacturing and Quality Engineering, School of Mechanical Engineering, Hubei University of Technology, Wuhan 430068, China
Hubei Digital Manufacturing Key Laboratory, School of Mechanical and Electronic Engineering, Wuhan University of Technology, Wuhan 430070, China
Department of Production Engineering, KTH Royal Institute of Technology Stockholm SE-10044, Sweden
Show Author Information

Abstract

To obtain a suitable scheduling scheme in an effective time range, the minimum completion time is taken as the objective of Flexible Job Shop scheduling Problems (FJSP) with different scales, and Composite Dispatching Rules (CDRs) are applied to generate feasible solutions. Firstly, the binary tree coding method is adopted, and the constructed function set is normalized. Secondly, a CDR mining approach based on an Improved Genetic Programming Algorithm (IGPA) is designed. Two population initialization methods are introduced to enrich the initial population, and a superior and inferior population separation strategy is designed to improve the global search ability of the algorithm. At the same time, two individual mutation methods are introduced to improve the algorithm’s local search ability, to achieve the balance between global search and local search. In addition, the effectiveness of the IGPA and the superiority of CDRs are verified through comparative analysis. Finally, Deep Reinforcement Learning (DRL) is employed to solve the FJSP by incorporating the CDRs as the action set, the selection times are counted to further verify the superiority of CDRs.

Keywords

deep reinforcement learningflexible job shop schedulingcomposite dispatching ruleimproved genetic programming algorithm

References

[1]

R. Li, W. Gong, L. Wang, C. Lu, and X. Zhuang, Surprisingly popular-based adaptive memetic algorithm for energy-efficient distributed flexible job shop scheduling, IEEE Trans. Cybern., vol. 53, no. 12, pp. 8013–8023, 2023.
Crossref Google Scholar
[2]

E. Jiang, L. Wang, and J. Wang, Decomposition-based multi-objective optimization for energy-aware distributed hybrid flow shop scheduling with multiprocessor tasks, Tsinghua Sci. Technol., vol. 26, no. 5, pp. 646–663, 2021.
Crossref Google Scholar
[3]

Z. Chen, L. Zhang, X. Wang, and P. Gu, Optimal design of flexible job shop scheduling under resource preemption based on deep reinforcement learning, Complex Syst. Model. Simul., vol. 2, no. 2, pp. 174–185, 2022.
Crossref Google Scholar
[4]

H. Zhang, J. Xie, J. Ge, J. Shi, and Z. Zhang, Hybrid particle swarm optimization algorithm based on entropy theory for solving DAR scheduling problem, Tsinghua Sci. Technol., vol. 24, no. 3, pp. 282–290, 2019.
Crossref Google Scholar
[5]

X. Li, X. Guo, H. Tang, R. Wu, L. Wang, S. Pang, Z. Liu, W. Xu, and X. Li, Survey of integrated flexible job shop scheduling problems, Comput. Ind. Eng., vol. 174, p. 108786, 2022.
Crossref Google Scholar
[6]

L. Meng, W. Cheng, B. Zhang, W. Zou, W. Fang, and P. Duan, An improved genetic algorithm for solving the multi-AGV flexible job shop scheduling problem, Sensors, vol. 23, no. 8, p. 3815, 2023.
Crossref Google Scholar
[7]

X. Long, J. Zhang, K. Zhou, and T. Jin, Dynamic self-learning artificial bee colony optimization algorithm for flexible job-shop scheduling problem with job insertion, Processes, vol. 10, no. 3, p. 571, 2022.
Crossref Google Scholar
[8]

J. Li, X. Gu, Y. Zhang, and X. Zhou, Distributed flexible job-shop scheduling problem based on hybrid chemical reaction optimization algorithm, Complex Syst. Model. Simul., vol. 2, no. 2, pp. 156–173, 2022.
Crossref Google Scholar
[9]

J. Duan and J. Wang, Robust scheduling for flexible machining job shop subject to machine breakdowns and new job arrivals considering system reusability and task recurrence, Expert Syst. Appl., vol. 203, p. 117489, 2022.
Crossref Google Scholar
[10]

D. Lei, M. Li, and L. Wang, A two-phase meta-heuristic for multiobjective flexible job shop scheduling problem with total energy consumption threshold, IEEE Trans. Cybern., vol. 49, no. 3, pp. 1097–1109, 2019.
Crossref Google Scholar
[11]

Z. Zhuang, Y. Li, Y. Sun, W. Qin, and Z.-H. Sun, Network-based dynamic dispatching rule generation mechanism for real-time production scheduling problems with dynamic job arrivals, Robot. Comput. Integr. Manuf., vol. 73, p. 102261, 2022.
Crossref Google Scholar
[12]

H. Zhang and U. Roy, A semantics-based dispatching rule selection approach for job shop scheduling, J. Intell. Manuf., vol. 30, no. 7, pp. 2759–2779, 2019.
Crossref Google Scholar
[13]
C.-H. Lee A dispatching rule and a random iterated greedy metaheuristic for identical parallel machine scheduling to minimize total tardiness, Int. J. Prod. Res., vol. 56, no. 6, pp. 2292–2308, 2018.
Crossref
[14]

J. Branke, S. Nguyen, C. W. Pickardt, and M. Zhang, Automated design of production scheduling heuristics: A review, IEEE Trans. Evol. Comput., vol. 20, no. 1, pp. 110–124, 2016.
Crossref Google Scholar
[15]

M. Thenarasu, K. Rameshkumar, J. Rousseau, and S. P. Anbuudayasankar, Development and analysis of priority decision rules using MCDM approach for a flexible job shop scheduling: A simulation study, Simul. Model. Pract. Theory, vol. 114, p. 102416, 2022.
Crossref Google Scholar
[16]

C. Ferreira, G. Figueira, and P. Amorim, Effective and interpretable dispatching rules for dynamic job shops via guided empirical learning, Omega, vol. 111, p. 102643, 2022.
Crossref Google Scholar
[17]

D. Wu, G. Zeng, D. He, Z. Qian, and Q. Zhang, Task coordination organization model and the task allocation algorithm for resource contention of the syncretic system, Tsinghua Sci. Technol., vol. 21, no. 4, pp. 459–470, 2016.
Crossref Google Scholar
[18]

S. Jun, S. Lee, and H. Chun, Learning dispatching rules using random forest in flexible job shop scheduling problems, Int. J. Prod. Res., vol. 57, no. 10, pp. 3290–3310, 2019.
Crossref Google Scholar
[19]

B. Chen and T. I. Matis, A flexible dispatching rule for minimizing tardiness in job shop scheduling, Int. J. Prod. Econ., vol. 141, no. 1, pp. 360–365, 2013.
Crossref Google Scholar
[20]

B. Mihoubi, B. Bouzouia, and M. Gaham, Reactive scheduling approach for solving a realistic flexible job shop scheduling problem, Int. J. Prod. Res., vol. 59, no. 19, pp. 5790–5808, 2021.
Crossref Google Scholar
[21]

J. Heger and T. Voss, Reducing mean tardiness in a flexible job shop containing AGVs with optimized combinations of sequencing and routing rules, Procedia CIRP, vol. 81, pp. 1136–1141, 2019.
Crossref Google Scholar
[22]

A. Teymourifar and G. Ozturk, New dispatching rules and due date assignment models for dynamic job shop scheduling problems, Int. J. Manuf. Res., vol. 13, no. 4, p. 302, 2018.
Crossref Google Scholar
[23]

M. Đurasević and D. Jakobović, Selection of dispatching rules evolved by genetic programming in dynamic unrelated machines scheduling based on problem characteristics, J. Comput. Sci., vol. 61, pp. 101649, 2022.
Crossref Google Scholar
[24]

L. Wang, Z. Pan, and J. Wang, A review of reinforcement learning based intelligent optimization for manufacturing scheduling, Complex Syst. Model. Simul., vol. 1, no. 4, pp. 257–270, 2021.
Crossref Google Scholar
[25]
K. Chang, S. H. Park, and J.-G. Baek, AGV dispatching algorithm based on deep Q-network in CNC machines environment, Int. J. Comput. Integr. Manuf., vol. 35, no. 6, pp. 662–677, 2022.
Crossref
[26]

W. Song, X. Chen, Q. Li, and Z. Cao, Flexible job-shop scheduling via graph neural network and deep reinforcement learning, IEEE Trans. Ind. Inform., vol. 19, no. 2, pp. 1600–1610, 2023.
Crossref Google Scholar
[27]

C.-L. Liu, C.-J. Tseng, T.-H. Huang, and J.-W. Wang, Dynamic parallel machine scheduling with deep Q-network, IEEE Trans. Syst. Man Cybern. Syst., vol. 53, pp. 6792–6804, 2023.
Crossref Google Scholar
[28]

Y. Gui, D. Tang, H. Zhu, Y. Zhang, and Z. Zhang, Dynamic scheduling for flexible job shop using a deep reinforcement learning approach, Comput. Ind. Eng., vol. 180, p. 109255, 2023.
Crossref Google Scholar
[29]

B. Min and C. O. Kim, State-dependent parameter tuning of the apparent tardiness cost dispatching rule using deep reinforcement learning, IEEE Access, vol. 10, pp. 20187–20198, 2022.
Crossref Google Scholar
[30]

M. M. Nasiri, R. Yazdanparast, and F. Jolai, A simulation optimisation approach for real-time scheduling in an open shop environment using a composite dispatching rule, Int. J. Comput. Integr. Manuf., vol. 30, no. 12, pp. 1239–1252, 2017.
Crossref Google Scholar
[31]

A. Yadav and S. C. Jayswal, Modelling of flexible manufacturing system: a review, Int. J. Prod. Res., vol. 56, no. 7, pp. 2464–2487, 2018.
Crossref Google Scholar
[32]

R. Li, W. Gong, and C. Lu, Self-adaptive multi-objective evolutionary algorithm for flexible job shop scheduling with fuzzy processing time, Comput. Ind. Eng., vol. 168, p. 108099, 2022.
Crossref Google Scholar
[33]

E.-D. Jiang and L. Wang, Multi-objective optimization based on decomposition for flexible job shop scheduling under time-of-use electricity prices, Knowl. Based Syst., vol. 204, p. 106177, 2020.
Crossref Google Scholar
[34]

M. Ɖurasević and D. Jakobović, Evolving dispatching rules for optimising many-objective criteria in the unrelated machines environment, Genet. Program. Evolvable Mach., vol. 19, no. 1, pp. 9–51, 2018.
Crossref Google Scholar
[35]

S. Shady, T. Kaihara, N. Fujii, and D. Kokuryo, Feature selection approach for evolving reactive scheduling policies for dynamic job shop scheduling problem using gene expression programming, Int. J. Prod. Res., vol. 61, no. 15, pp. 5029–5052, 2023.
Crossref Google Scholar
[36]

S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan, Automatic programming via iterated local search for dynamic job shop scheduling, IEEE Trans. Cybern., vol. 45, no. 1, pp. 1–14, 2015.
Crossref Google Scholar
[37]

B. Xu, Y. Mei, Y. Wang, Z. Ji, and M. Zhang, Genetic programming with delayed routing for multiobjective dynamic flexible job shop scheduling, Evol. Comput., vol. 29, no. 1, pp. 75–105, 2021.
Crossref Google Scholar
[38]

L. Zhang, Y. Hu, C. Wang, Q. Tang, and X. Li, Effective dispatching rules mining based on near-optimal schedules in intelligent job shop environment, J. Manuf. Syst., vol. 63, pp. 424–438, 2022.
Crossref Google Scholar
[39]

S. Jun and S. Lee, Learning dispatching rules for single machine scheduling with dynamic arrivals based on decision trees and feature construction, Int. J. Prod. Res., vol. 59, no. 9, pp. 2838–2856, 2021.
Crossref Google Scholar
[40]

S. Wang, H. Su, G. Wan, and L. Zhong, Surgery scheduling in the presence of operating room eligibility and dedicated surgeon: An adaptive composite dispatching method, Int. J. Prod. Res., vol. 61, no. 6, pp. 1866–1881, 2023.
Crossref Google Scholar
[41]

S. Nguyen, M. Zhang, and K. C. Tan, Surrogate-assisted genetic programming with simplified models for automated design of dispatching rules, IEEE Trans. Cybern., vol. 47, no. 9, pp. 2951–2965, 2017.
Crossref Google Scholar
[42]

Y. Mei, S. Nguyen, B. Xue, and M. Zhang, An efficient feature selection algorithm for evolving job shop scheduling rules with genetic programming, IEEE Trans. Emerg. Top. Comput. Intell., vol. 1, no. 5, pp. 339–353, 2017.
Crossref Google Scholar
[43]
J. R. Koza Genetic programming as a means for programming computers by natural selection, Stat. Comput., vol. 4, no. 2, pp. 87–112, 1994.
Crossref
[44]

L. Zhang, N. R. Alharbe, G. Luo, Z. Yao, and Y. Li, A hybrid forecasting framework based on support vector regression with a modified genetic algorithm and a random forest for traffic flow prediction, Tsinghua Sci. Technol., vol. 23, no. 4, pp. 479–492, 2018.
Crossref Google Scholar
[45]

Y. Zeiträg, J. R. Figueira, N. Horta, and R. Neves, Surrogate-assisted automatic evolving of dispatching rules for multi-objective dynamic job shop scheduling using genetic programming, Expert Syst. Appl., vol. 209, p. 118194, 2022.
Crossref Google Scholar
[46]

M. Abedi, R. Chiong, N. Noman, and R. Zhang, A multi-population, multi-objective memetic algorithm for energy-efficient job-shop scheduling with deteriorating machines, Expert Syst. Appl., vol. 157, p. 113348, 2020.
Crossref Google Scholar
[47]

C.-C. Wu, S.-C. Liu, C. Zhao, S.-Z. Wang, and W.-C. Lin, A multi-machine order scheduling with learning using the genetic algorithm and particle swarm optimization, Comput. J., vol. 61, no. 1, pp. 14–31, 2018.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 29 Issue 5,
October 2024
Pages 1390-1408
DOI: 10.26599/TST.2023.9010141
Cite this article:
Li X, Zhao Q, Tang H, et al. Flexible Job Shop Composite Dispatching Rule Mining Approach Based on an Improved Genetic Programming Algorithm. Tsinghua Science and Technology, 2024, 29(5): 1390-1408. https://doi.org/10.26599/TST.2023.9010141

192

Views

22

Downloads

1

Crossref

0

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 19 July 2023
Revised: 11 November 2023
Accepted: 14 November 2023
Published: 02 May 2024
© The Author(s) 2024.

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