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
View PDF
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

A Hybrid Algorithm Based on Comprehensive Search Mechanisms for Job Shop Scheduling Problem

School of Mechanical Engineering, University of Jinan, Jinan 250022, China
Show Author Information

Abstract

The research on complex workshop scheduling methods has important academic significance and has wide applications in industrial manufacturing. Aiming at the job shop scheduling problem, a hybrid algorithm based on comprehensive search mechanisms (HACSM) is proposed to optimize the maximum completion time. HACSM combines three search methods with different optimization scales, including fireworks algorithm (FW), extended Akers graphical method (LS1+_AKERS_EXT), and tabu search algorithm (TS). FW realizes global search through information interaction and resource allocation, ensuring the diversity of the population. LS1+_AKERS_EXT realizes compound movement with Akers graphical method, so it has advanced global and local search capabilities. In LS1+_AKERS_EXT, the shortest path is the core of the algorithm, which directly affects the encoding and decoding of scheduling. In order to find the shortest path, an effective node expansion method is designed to improve the node expansion efficiency. In the part of centralized search, TS based on the neighborhood structure is used. Finally, the effectiveness and superiority of HACSM are verified by testing the relevant instances in the literature.

Keywords

tabu searchfireworks algorithmjob shop schedulingAkers graphicalhybrid scheduling algorithms

References

[1]

P. Brucker, B. Jurisch, and B. Sievers, A branch and bound algorithm for the job-shop scheduling problem, Discrete Appl. Math., vol. 49, no. 1, pp. 107–127, 1994.
DOI Google Scholar
[2]

W. Y. Ku and J. C. Beck, Mixed Integer Programming models for job shop scheduling: A computational analysis, Comput. Oper. Res., vol. 73, pp. 165–173, 2016.
DOI Google Scholar
[3]

S. Dauzere-Peres and J. B. Lasserre, A modified shifting bottleneck procedure for job-shop scheduling, Int. J. Prod. Res., vol. 31, no. 4, pp. 923–932, 1993.
DOI Google Scholar
[4]

F. D. Croce, R. Tadei, and G. Volta, A genetic algorithm for the job shop problem, Comput. Oper. Res., vol. 22, no. 1, pp. 15–24, 1995.
DOI Google Scholar
[5]

R. Qing-dao-er-ji and Y. Wang, A new hybrid genetic algorithm for job shop scheduling problem, Comput. Oper. Res., vol. 39, no. 10, pp. 2291–2299, 2012.
DOI Google Scholar
[6]

L. Asadzadeh, A parallel artificial bee colony algorithm for the job shop scheduling problem with a dynamic migration strategy, Comput. Ind. Eng., vol. 102, no. C, pp. 359–367, 2016.
DOI Google Scholar
[7]

N. Sharma, H. Sharma, and A. Sharma, Beer froth artificial bee colony algorithm for job-shop scheduling problem, Appl. Soft Comput., vol. 68, no. C, pp. 507–524, 2018.
DOI Google Scholar
[8]

L. Gao, X. Li, X. Wen, C. Lu, and F. Wen, A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem, Comput. Ind. Eng., vol. 88, pp. 417–429, 2015.
DOI Google Scholar
[9]

M. M. Nasiri and F. Kianfar, A guided tabu search/path relinking algorithm for the job shop problem, Int. J. Adv. Manuf. Technol., vol. 58, no. 9, pp. 1105–1113, 2012.
DOI Google Scholar
[10]

M. M. Nasiri and F. Kianfar, A GES/TS algorithm for the job shop scheduling, Comput. Ind. Eng., vol. 62, no. 4, pp. 946–952, 2012.
DOI Google Scholar
[11]

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

Q. Pan, L. Wang, L. Gao, and H. Sang, Differential evolution algorithm based on blocks on critical path for job shop scheduling problems, J. Mech. Eng., vol. 46, no. 22, pp. 182–188, 2010.
DOI Google Scholar
[13]

B. Z. Yao, C. Y. Yang, J. J. Hu, G. D. Yin, and B. Yu, An improved artificial bee colony algorithm for job shop problem, Appl. Mech. Mater., vols. 26–28, pp. 657–660, 2010.
DOI Google Scholar
[14]

R. Yusof, M. Khalid, G. T. Hui, S. M. Yusof, and M. F. Othman, Solving job shop scheduling problem using a hybrid parallel micro genetic algorithm, Appl. Soft Comput., vol. 11, no. 8, pp. 5782–5792, 2011.
DOI Google Scholar
[15]

V. Sels, K. Craeymeersch, and M. Vanhoucke, A hybrid single and dual population search procedure for the job shop scheduling problem, Eur. J. Oper. Res., vol. 215, no. 3, pp. 512–523, 2011.
DOI Google Scholar
[16]

L. Gao, G. Zhang, L. Zhang, and X. Li, An efficient memetic algorithm for solving the job shop scheduling problem, Comput. Ind. Eng., vol. 60, no. 4, pp. 699–705, 2011.
DOI Google Scholar
[17]

X. Zuo, C. Wang, and W. Tan, Two heads are better than one: An AIS- and TS-based hybrid strategy for job shop scheduling problems, Int. J. Adv. Manuf. Technol., vol. 63, no. 1, pp. 155–168, 2012.
DOI Google Scholar
[18]

W. Wisittipanich and V. Kachitvichyanukul, Two enhanced differential evolution algorithms for job shop scheduling problems, Int. J. Prod. Res., vol. 50, no. 10, pp. 2757–2773, 2012.
DOI Google Scholar
[19]

A. Banharnsakun, B. Sirinaovakul, and T. Achalakul, Job shop scheduling with the best-so-far ABC, Eng. Appl. Artif. Intell., vol. 25, no. 3, pp. 583–593, 2012.
DOI Google Scholar
[20]

A. Ponsich and C. A. C. Coello, A hybrid differential evolution—Tabu search algorithm for the solution of job-shop scheduling problems, Appl. Soft Comput., vol. 13, no. 1, pp. 462–474, 2013.
DOI Google Scholar
[21]

R. Zhang, S. Song, and C. Wu, A hybrid artificial bee colony algorithm for the job shop scheduling problem, Int. J. Prod. Econ., vol. 141, no. 1, pp. 167–178, 2013.
DOI Google Scholar
[22]

A. C. Spanos, S. T. Ponis, I. P. Tatsiopoulos, I. T. Christou, and E. Rokou, A new hybrid parallel genetic algorithm for the job-shop scheduling problem, Int. Trans. Oper. Res., vol. 21, no. 3, pp. 479–499, 2014.
DOI Google Scholar
[23]

J. F. Gonçalves and M. G. C. Resende, An extended Akers graphical method with a biased random-key genetic algorithm for job-shop scheduling, Int. Trans. Oper. Res., vol. 21, no. 2, pp. 215–246, 2014.
DOI Google Scholar
[24]

X. Wang and H. Duan, A hybrid biogeography-based optimization algorithm for job shop scheduling problem, Comput. Ind. Eng., vol. 73, pp. 96–114, 2014.
DOI Google Scholar
[25]

S. Meeran and M. S. Morshed, Evaluation of a hybrid genetic tabu search framework on job shop scheduling benchmark problems, Int. J. Prod. Res., vol. 52, no. 19, pp. 5780–5798, 2014.
DOI Google Scholar
[26]

F. Zhao, X. Jiang, C. Zhang, and J. Wang, A chemotaxis-enhanced bacterial foraging algorithm and its application in job shop scheduling problem, Int. J. Comput. Integr. Manuf., vol. 28, no. 10, pp. 1106–1121, 2014.
Google Scholar
[27]

B. Peng, Z. Lü, and T. C. E. Cheng, A tabu search/path relinking algorithm to solve the job shop scheduling problem, Comput. Oper. Res., vol. 53, pp. 154–164, 2015.
DOI Google Scholar
[28]

L. Asadzadeh, A local search genetic algorithm for the job shop scheduling problem with intelligent agents, Comput. Ind. Eng., vol. 85, no. C, pp. 376–383, 2015.
DOI Google Scholar
[29]

M. Kurdi, A new hybrid island model genetic algorithm for job shop scheduling problem, Comput. Ind. Eng., vol. 88, no. C, pp. 273–283, 2015.
DOI Google Scholar
[30]

F. Zhao, Z. Shao, J. Wang, and C. Zhang, A hybrid differential evolution and estimation of distribution algorithm based on neighbourhood search for job shop scheduling problems, Int. J. Prod. Res., vol. 54, no. 4, pp. 1039–1060, 2015.
DOI Google Scholar
[31]

F. A. Toader, A hybrid algorithm for job shop scheduling problem, Stud. Inform. Contr., vol. 24, no. 2, pp. 171–180, 2015.
DOI Google Scholar
[32]

T. C. E. Cheng, B. Peng, and Z. Lü, A hybrid evolutionary algorithm to solve the job shop scheduling problem, Ann. Oper. Res., vol. 242, no. 2, pp. 223–237, 2016.
DOI Google Scholar
[33]

S. Zhao, A hybrid algorithm with a new neighborhood structure for the job shop scheduling problem, J. Mech. Eng., vol. 52, no. 9, pp. 141–150, 2016.
DOI Google Scholar
[34]

Y. Nagata and I. Ono, A guided local search with iterative ejections of bottleneck operations for the job shop scheduling problem, Comput. Oper. Res., vol. 90, no. C, pp. 60–71, 2018.
DOI Google Scholar
[35]

C. Peng, G. Wu, T. W. Liao, and H. Wang, Research on multi-agent genetic algorithm based on tabu search for the job shop scheduling problem, PLoS One, vol. 14, no. 9, p. e0223182, 2019.
DOI Google Scholar
[36]

G. Zhou, Y. Zhou, and R. Zhao, Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem, J. Ind. Manag. Optim., vol. 17, no. 2, pp. 533–548, 2021.
DOI Google Scholar
[37]

M. Liu, X. Yao, and Y. Li, Hybrid whale optimization algorithm enhanced with Lévy flight and differential evolution for job shop scheduling problems, Appl. Soft Comput., vol. 87, p. 105954, 2020.
DOI Google Scholar
[38]

S. K. Zhao, Research on path relinking based on non-delay scheduling and backtracking tabu search algorithm of job shop scheduling problem, J. Mech. Eng., vol. 57, no. 14, pp. 291–303, 2021.
DOI Google Scholar
[39]

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

L. Huang, S. K. Zhao, and S. Huang, Hybrid algorithm based on obstacle graph model and tabu search for job shop scheduling problem, J. Mech. Eng., vol. 59, no. 16, pp. 435–444, 2023.
DOI Google Scholar
[41]

C. Y. Zhang, P. Li, Y. Rao, and Z. Guan, A very fast TS/SA algorithm for the job shop scheduling problem, Comput. Oper. Res., vol. 35, no. 1, pp. 282–294, 2008.
DOI Google Scholar
[42]

E. Yuan, L. Wang, S. Cheng, S. Song, W. Fan, and Y. Li, Solving flexible job shop scheduling problems via deep reinforcement learning, Expert Syst. Appl., vol. 245, p. 123019, 2024.
DOI Google Scholar
[43]

L. Gui, X. Li, L. Gao, and C. Wang, Necessary and sufficient conditions for feasible neighbourhood solutions in the local search of the job-shop scheduling problem, Chin. J. Mech. Eng., vol. 36, no. 1, p. 87, 2023.
DOI Google Scholar
[44]

Y. Zhang, H. Zhu, D. Tang, T. Zhou, and Y. Gui, Dynamic job shop scheduling based on deep reinforcement learning for multi-agent manufacturing systems, Robot. Comput. Integr. Manuf., vol. 78, p. 102412, 2022.
DOI Google Scholar
[45]

L. He, W. Li, Y. Zhang, and Y. Cao, A discrete multi-objective fireworks algorithm for flowshop scheduling with sequence-dependent setup times, Swarm and Evolutionary Computation, vol. 51, p. 100575, 2019.
DOI Google Scholar
[46]

X. Pang, H. Xue, M. L. Tseng, M. K. Lim, and K. Liu, Hybrid flow shop scheduling problems using improved fireworks algorithm for permutation, Appl. Sci., vol. 10, no. 3, p. 1174, 2020.
DOI Google Scholar
[47]

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

S. B. Akers, A graphical approach to production scheduling problems, Oper. Res., vol. 4, no. 2, pp. 244–245, 1956.
DOI Google Scholar
[49]

P. Brucker, An efficient algorithm for the job-shop problem with two jobs, Computing, vol. 40, no. 4, pp. 353–359, 1988.
DOI Google Scholar
[50]

P. E. Hart, N. J. Nilsson, and B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cybern., vol. 4, no. 2, pp. 100–107, 1968.
DOI Google Scholar
[51]

E. Balas and A. Vazacopoulos, Guided local search with shifting bottleneck for job shop scheduling, Manag. Sci., vol. 44, no. 2, pp. 262–275, 1998.
DOI Google Scholar
Complex System Modeling and Simulation
Volume 4 Issue 1,
March 2024
Pages 50-66
DOI: 10.23919/CSMS.2024.0001
Cite this article:
Huang L, Zhao S, Xiong Y. A Hybrid Algorithm Based on Comprehensive Search Mechanisms for Job Shop Scheduling Problem. Complex System Modeling and Simulation, 2024, 4(1): 50-66. https://doi.org/10.23919/CSMS.2024.0001

107

Views

25

Downloads

0

Crossref

0

Scopus

Altmetrics
Received: 07 December 2023
Revised: 20 February 2024
Accepted: 12 March 2024
Published: 30 March 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