Journal Home > Volume 29 , Issue 5
Tsinghua Science and Technology 2024, 29(5): 1283-1299 https://doi.org/10.26599/TST.2023.9010098
Open Access | Issue | Published: 02 May 2024

Cooperative-Guided Ant Colony Optimization with Knowledge Learning for Job Shop Scheduling Problem

Show Author's Information Wei Li1,  Xiangfang Yan1,  Ying Huang2( )
School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China
School of Mathematics and Computer Science, Gannan Normal University, Ganzhou 341000, China
Keywords:
Ant Colony Optimization (ACO), Job shop Scheduling Problem (JSP), knowledge learning, co-operative guidance
Cite this article:
Li W, Yan X, Huang Y. Cooperative-Guided Ant Colony Optimization with Knowledge Learning for Job Shop Scheduling Problem. Tsinghua Science and Technology, 2024, 29(5): 1283-1299. https://doi.org/10.26599/TST.2023.9010098
Download citation
EndNote(RIS)
BibTeX

81

Views

26

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

0

CSCD

Abstract Full text About this article

With the advancement of the manufacturing industry, the investigation of the shop floor scheduling problem has gained increasing importance. The Job shop Scheduling Problem (JSP), as a fundamental scheduling problem, holds considerable theoretical research value. However, finding a satisfactory solution within a given time is difficult due to the NP-hard nature of the JSP. A co-operative-guided ant colony optimization algorithm with knowledge learning (namely KLCACO) is proposed to address this difficulty. This algorithm integrates a data-based swarm intelligence optimization algorithm with model-based JSP schedule knowledge. A solution construction scheme based on scheduling knowledge learning is proposed for KLCACO. The problem model and algorithm data are fused by merging scheduling and planning knowledge with individual scheme construction to enhance the quality of the generated individual solutions. A pheromone guidance mechanism, which is based on a collaborative machine strategy, is used to simplify information learning and the problem space by collaborating with different machine processing orders. Additionally, the KLCACO algorithm utilizes the classical neighborhood structure to optimize the solution, expanding the search space of the algorithm and accelerating its convergence. The KLCACO algorithm is compared with other high-performance intelligent optimization algorithms on four public benchmark datasets, comprising 48 benchmark test cases in total. The effectiveness of the proposed algorithm in addressing JSPs is validated, demonstrating the feasibility of the KLCACO algorithm for knowledge and data fusion in complex combinatorial optimization problems.


menu
Abstract
Full text
Outline
About this article

Cooperative-Guided Ant Colony Optimization with Knowledge Learning for Job Shop Scheduling Problem

Show Author's information Wei Li1, Xiangfang Yan1, Ying Huang2( )
School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou 341000, China
School of Mathematics and Computer Science, Gannan Normal University, Ganzhou 341000, China

Abstract

With the advancement of the manufacturing industry, the investigation of the shop floor scheduling problem has gained increasing importance. The Job shop Scheduling Problem (JSP), as a fundamental scheduling problem, holds considerable theoretical research value. However, finding a satisfactory solution within a given time is difficult due to the NP-hard nature of the JSP. A co-operative-guided ant colony optimization algorithm with knowledge learning (namely KLCACO) is proposed to address this difficulty. This algorithm integrates a data-based swarm intelligence optimization algorithm with model-based JSP schedule knowledge. A solution construction scheme based on scheduling knowledge learning is proposed for KLCACO. The problem model and algorithm data are fused by merging scheduling and planning knowledge with individual scheme construction to enhance the quality of the generated individual solutions. A pheromone guidance mechanism, which is based on a collaborative machine strategy, is used to simplify information learning and the problem space by collaborating with different machine processing orders. Additionally, the KLCACO algorithm utilizes the classical neighborhood structure to optimize the solution, expanding the search space of the algorithm and accelerating its convergence. The KLCACO algorithm is compared with other high-performance intelligent optimization algorithms on four public benchmark datasets, comprising 48 benchmark test cases in total. The effectiveness of the proposed algorithm in addressing JSPs is validated, demonstrating the feasibility of the KLCACO algorithm for knowledge and data fusion in complex combinatorial optimization problems.

Keywords: Ant Colony Optimization (ACO), Job shop Scheduling Problem (JSP), knowledge learning, co-operative guidance

References(43)

[1]

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

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
[3]

Y. Fu, Y. Hou, Z. Wang, X. Wu, K. Gao, and L. Wang, Distributed scheduling problems in intelligent manufacturing systems, Tsinghua Science and Technology, vol. 26, no. 5, pp. 625–645, 2021.
DOI Google Scholar
[4]

C. Destouet, H. Tlahig, B. Bettayeb, and B. Mazari, Flexible job shop scheduling problem under Industry 5.0: A survey on human reintegration, environmental consideration and resilience improvement, J. Manuf. Syst., vol. 67, pp. 155–173, 2023.
DOI Google Scholar
[5]

F. Zhao, Z. Xu, L. Wang, N. Zhu, T. Xu, and J. Jonrinaldi, A population-based iterated greedy algorithm for distributed assembly No-wait flow-shop scheduling problem, IEEE Trans. Ind. Inform., vol. 19, no. 5, pp. 6692–6705, 2023.
DOI Google Scholar
[6]

G. G. Wang, D. Gao, and W. Pedrycz, Solving multiobjective fuzzy job-shop scheduling problem by a hybrid adaptive differential evolution algorithm, IEEE Trans. Ind. Inform., vol. 18, no. 12, pp. 8519–8528, 2022.
DOI Google Scholar
[7]

B. Yan, M. A. Bragin, and P. B. Luh, An innovative formulation tightening approach for job-shop scheduling, IEEE Trans. Autom. Sci. Eng., vol. 19, no. 3, pp. 2526–2539, 2022.
DOI Google Scholar
[8]

Y. J. Yao, Q. H. Liu, X. Y. Li, and L. Gao, A novel MILP model for job shop scheduling problem with mobile robots, Robot. Comput. Integr. Manuf., vol. 81, p. 102506, 2023.
DOI Google Scholar
[9]

M. A. Şahman and S. Korkmaz, Discrete artificial algae algorithm for solving job-shop scheduling problems, Knowl. Based Syst., vol. 256, p. 109711, 2022.
DOI Google Scholar
[10]

S. Mahmud, A. Abbasi, R. K. Chakrabortty, and M. J. Ryan, Multi-operator communication based differential evolution with sequential Tabu Search approach for job shop scheduling problems, Appl. Soft Comput., vol. 108, p. 107470, 2021.
DOI Google Scholar
[11]

J. Xie, X. Li, L. Gao, and L. Gui, A hybrid algorithm with a new neighborhood structure for job shop scheduling problems, Comput. Ind. Eng., vol. 169, p. 108205, 2022.
DOI Google Scholar
[12]

L. N. Xing, Y. W. Chen, P. Wang, Q. S. Zhao, and J. Xiong, A knowledge-based ant colony optimization for flexible job shop scheduling problems, Appl. Soft Comput., vol. 10, no. 3, pp. 888–896, 2010.
DOI Google Scholar
[13]

W. Zhang, W. Hou, C. Li, W. Yang, and M. Gen, Multidirection update-based multiobjective particle swarm optimization for mixed No-idle flow-shop scheduling problem, Complex Syst. Model. Simul., vol. 1, no. 3, pp. 176–197, 2021.
DOI Google Scholar
[14]

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.
DOI Google Scholar
[15]

X. Han, Y. Han, Q. Chen, J. Li, H. Sang, Y. Liu, Q. Pan, and Y. Nojima, Distributed flow shop scheduling with sequence-dependent setup times using an improved iterated greedy algorithm, Complex Syst. Model. Simul., vol. 1, no. 3, pp. 198–217, 2021.
DOI Google Scholar
[16]

X. Zhang, B. Zhang, L. Meng, Y. Ren, R. Meng, and J. Li, An evolutionary algorithm for a hybrid flowshop scheduling problem with consistent sublots, Int. J. Autom. Contr., vol. 16, no. 1, p. 19, 2022.
DOI Google Scholar
[17]

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.
DOI Google Scholar
[18]

B. Xi and D. Lei, Q-learning-based teaching-learning optimization for distributed two-stage hybrid flow shop scheduling with fuzzy processing time, Complex Syst. Model. Simul., vol. 2, no. 2, pp. 113–129, 2022.
DOI Google Scholar
[19]

F. Zhao, T. Jiang, and L. Wang, A reinforcement learning driven cooperative meta-heuristic algorithm for energy-efficient distributed No-wait flow-shop scheduling with sequence-dependent setup time, IEEE Trans. Ind. Inform., vol. 19, no. 7, pp. 8427–8440, 2023.
DOI Google Scholar
[20]

X. Wu, Z. Cao, and S. Wu, Real-time hybrid flow shop scheduling approach in smart manufacturing environment, Complex Syst. Model. Simul., vol. 1, no. 4, pp. 335–350, 2021.
DOI Google Scholar
[21]

J. J. Wang and L. Wang, A cooperative memetic algorithm with feedback for the energy-aware distributed flow-shops with flexible assembly scheduling, Comput. Ind. Eng., vol. 168, p. 108126, 2022.
DOI Google Scholar
[22]

Z. Pan, D. Lei, and L. Wang, A Bi-population evolutionary algorithm with feedback for energy-efficient fuzzy flexible job shop scheduling, IEEE Trans. Syst. Man Cybern. Syst., vol. 52, no. 8, pp. 5295–5307, 2022.
DOI Google Scholar
[23]

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.
DOI Google Scholar
[24]

C. Zhang, P. Li, Z. Guan, and Y. Rao, A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem, Comput. Oper. Res., vol. 34, no. 11, pp. 3229–3242, 2007.
DOI Google Scholar
[25]
M. Dorigo and T. Stützle, Ant colony optimization: Overview and recent advances. M. Gendreau and J. Y. Potvin, eds. Cham, Switzerland: Springer, 2019, pp. 311−351.
DOI
[26]

M. Dorigo, V. Maniezzo, and A. Colorni, Ant system: Optimization by a colony of cooperating agents, IEEE Trans. Syst. Man Cybern. Part B Cybern., vol. 26, no. 1, pp. 29–41, 1996.
DOI Google Scholar
[27]

M. Dorigo and L. M. Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Trans. EComput., vol. 1, no. 1, pp. 53–66, 1997.
DOI Google Scholar
[28]
T. Stutzle and H. Hoos, MAX-MIN ant system and local search for the traveling salesman problem, in Proc. 1997 IEEE Int. Conf. Evolutionary Computation, Indianapolis, IN, USA, 1997, pp. 309–314.
[29]

P. Korytkowski, S. Rymaszewski, and T. Wiśniewski, Ant colony optimization for job shop scheduling using multi-attribute dispatching rules, Int. J. Adv. Manuf. Technol., vol. 67, no. 1, pp. 231–241, 2013.
DOI Google Scholar
[30]

E. Florez, W. Gomez, and M. Lola Bautista, An ant colony optimization algorithm for job shop scheduling problem, Int. J. Artif. Intell. Appl., vol. 4, no. 4, pp. 53–66, 2013.
DOI Google Scholar
[31]
E. Falkenauer and S. Bouffouix, A genetic algorithm for job shop, in Proc. 1991 IEEE Int. Conf. Robotics and Automation, Sacramento, CA, USA, 2002, pp. 824–829.
[32]

K. Sun, D. Zheng, H. Song, Z. Cheng, X. Lang, W. Yuan, and J. Wang, Hybrid genetic algorithm with variable neighborhood search for flexible job shop scheduling problem in a machining system, Expert Syst. Appl., vol. 215, p. 119359, 2023.
DOI Google Scholar
[33]
M. L. Pinedo, Job shops (deterministic), in Scheduling, Cham, Switzerland: Springer, 2016. pp. 183–220,
DOI
[34]

W. Zhang, X. Chen, and J. Jiang, A multi-objective optimization method of initial virtual machine fault-tolerant placement for star topological data centers of cloud systems, Tsinghua Science and Technology, vol. 26, no. 1, pp. 95–111, 2021.
DOI Google Scholar
[35]

J. Liu, S. Anavatti, M. Garratt, and H. A. Abbass, Modified continuous ant colony optimisation for multiple unmanned ground vehicle path planning, Expert Syst. Appl., vol. 196, p. 116605, 2022.
DOI Google Scholar
[36]

W. Li, C. Wang, Y. Huang, and Y. M. Cheung, Heuristic smoothing ant colony optimization with differential information for the traveling salesman problem, Appl. Soft Comput., vol. 133, p. 109943, 2023.
DOI Google Scholar
[37]

Y. H. Jia, Y. Mei, and M. Zhang, A bilevel ant colony optimization algorithm for capacitated electric vehicle routing problem, IEEE Trans. Cybern., vol. 52, no. 10, pp. 10855–10868, 2022.
DOI Google Scholar
[38]
T. Stützle and H. H. Hoos, Max-min ant system, Future Gener. Comput. Syst., vol. 16, no. 8, pp. 889–914, 2000.
DOI
[39]

J. Adams, E. Balas, and D. Zawack, The shifting bottleneck procedure for job shop scheduling, Manag. Sci., vol. 34, no. 3, pp. 391–401, 1988.
DOI Google Scholar
[40]
H. Fisher, Probabilistic learning combinations of local jobshopscheduling rules, Industrial scheduling, https://cir.nii.ac.jp/crid/1573950398887935360, 2023.
[41]
S. Lawrence, Resouce constrained project scheduling: Anexperimental investigation of heuristic schedulingtechniques (supplement), http://refhub.elsevier.com/S0950-7051(22)00866-8/sb73, 2023.
[42]

D. Applegate and W. Cook, A computational study of the job-shop scheduling problem, ORSA J. Comput., vol. 3, no. 2, pp. 149–156, 1991.
DOI Google Scholar
[43]

J. Yu, X. You, and S. Liu, A heterogeneous guided ant colony algorithm based on space explosion and long–short memory, Appl. Soft Comput., vol. 113, p. 107991, 2021.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 06 June 2023
Revised: 16 August 2023
Accepted: 07 September 2023
Published: 02 May 2024
Issue date: October 2024

Copyright

© The Author(s) 2024.

Acknowledgements

Acknowledgment

This work was supported by the National Natural Science Foundation of China (Nos. 62366003 and 62066019), the Natural Science Foundation of Jiangxi Province (No. 20232BAB202046), and the Graduate Innovation Foundation of Jiangxi University of Science and Technology (No. XY2022-S040).

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