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 (4.6 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

Domain Knowledge Used in Meta-Heuristic Algorithms for the Job-Shop Scheduling Problem: Review and Analysis

State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
Department of Computer Science, City University of Hong Kong, Hong Kong, China
Show Author Information

Abstract

Meta-heuristic algorithms search the problem solution space to obtain a satisfactory solution within a reasonable timeframe. By combining domain knowledge of the specific optimization problem, the search efficiency and quality of meta-heuristic algorithms can be significantly improved, making it crucial to identify and summarize domain knowledge within the problem. In this paper, we summarize and analyze domain knowledge that can be applied to meta-heuristic algorithms in the job-shop scheduling problem (JSP). Firstly, this paper delves into the importance of domain knowledge in optimization algorithm design. After that, the development of different methods for the JSP are reviewed, and the domain knowledge in it for meta-heuristic algorithms is summarized and classified. Applications of this domain knowledge are analyzed, showing it is indispensable in ensuring the optimization performance of meta-heuristic algorithms. Finally, this paper analyzes the relationship among domain knowledge, optimization problems, and optimization algorithms, and points out the shortcomings of the existing research and puts forward research prospects. This paper comprehensively summarizes the domain knowledge in the JSP, and discusses the relationship between the optimization problems, optimization algorithms and domain knowledge, which provides a research direction for the meta-heuristic algorithm design for solving the JSP in the future.

Keywords

domain knowledgejob-shop scheduling problemmeta-heuristic algorithm

References

[1]

D. H. Wolpert and W. G. Macready, No free lunch theorems for optimization, IEEE Trans. Evol. Comput., vol. 1, no. 1, pp. 67–82, 1997.
Crossref Google Scholar
[2]

Y. An, X. Chen, K. Gao, Y. Li, and L. Zhang, Multiobjective flexible job-shop rescheduling with new job insertion and machine preventive maintenance, IEEE Trans. Cybern., vol. 53, no. 5, pp. 3101–3113, 2023.
Crossref Google Scholar
[3]

Y. Fu, Y. Hou, Z. Wang, X. Wu, K. Gao, and L. Wang, Distributed scheduling problems in intelligent manufacturing systems, Tsing Science and Technology, vol. 26, no. 5, pp. 625–645, 2021.
Crossref Google Scholar
[4]
J. R. Jackson, Notes on some sheduling problems, research report no. 35, Research Report, Management Sciences Research Project, UCLA, 1954.
[5]

Z. Hu and D. Li, Improved heuristic job scheduling method to enhance throughput for big data analytics, Tsing Science and Technology, vol. 27, no. 2, pp. 344–357, 2022.
Crossref Google Scholar
[6]

E. Balas, Machine sequencing via disjunctive graphs: An implicit enumeration algorithm, Oper. Res., vol. 17, no. 6, pp. 941–957, 1969.
Crossref Google Scholar
[7]

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

H. Matsuo, C. Juck SUH, and R. S. Sullivan, A controlled search simulated annealing method for the single machine weighted tardiness problem, Ann. Oper. Res., vol. 21, no. 1, pp. 85–108, 1989.
Crossref Google Scholar
[9]

S. M. Alexander, An expert system for the selection of scheduling rules in a job shop, Comput. Ind. Eng., vol. 12, no. 3, pp. 167–171, 1987.
Crossref Google Scholar
[10]

Z. Liu, Y. Wang, X. Liang, Y. Ma, Y. Feng, G. Cheng, and Z. Liu, A graph neural networks-based deep Q- learning approach for job shop scheduling problems in traffic management, Inf. Sci., vol. 607, pp. 1211–1223, 2022.
Crossref Google Scholar
[11]

L. Wang, Z. Pan, and J. Wang, A review of reinforcement learning based intelligent optimization for manufacturing scheduling, Complex System Modeling and Simulation, vol. 1, no. 4, pp. 257–270, 2021.
Crossref Google Scholar
[12]

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 System Modeling and Simulation, vol. 2, no. 2, pp. 174–185, 2022.
Crossref Google Scholar
[13]
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.
Crossref
[14]
M. Gendreau and J. Y. Potvin, Handbook of metaheuristics, Vol.2 New York: Springer, 2010, p. 9.
Crossref
[15]

P. P. Bonissone, R. Subbu, N. Eklund, and T. R. Kiehl, Evolutionary algorithms+ domain knowledge= real-world evolutionary computation, IEEE Trans. Evol. Comput., vol. 10, no. 3, pp. 256–280, 2006.
Crossref Google Scholar
[16]

S. B. Akers Jr and J. Friedman, A non-numerical approach to production scheduling problems, J. Oper. Res. Soc., vol. 3, no. 4, pp. 429–442, 1955.
Crossref Google Scholar
[17]

R. L. Sisson, Methods of sequencing in job shops—A review, Oper. Res., vol. 7, no. 1, pp. 10–29, 1959.
Crossref Google Scholar
[18]
H. E. Nouri, O. B. Driss, and K. Ghédira, A classification schema for the job shop scheduling problem with transportation resources: state-of-the-art review, in Artificial Intelligence Perspectives in Intelligent Systems: Proceedings of the 5th Computer Science On-line Conference 2016 (CSOC2016), Springer International Publishing, vol. 1, pp. 1−11, 2016.
Crossref
[19]

Q. Li, J. Li, Q. Zhang, P. Duan, and T. Meng, An improved whale optimisation algorithm for distributed assembly flow shop with crane transportation, Int. J. Autom. Control, vol. 15, no. 6, pp. 710–743, 2021.
Crossref Google Scholar
[20]

S. C. Kim and P. M. Bobrowski, Impact of sequence- dependent setup time on job shop scheduling performance, Int. J. Prod. Res., vol. 32, no. 7, pp. 1503–1520, 1994.
Crossref Google Scholar
[21]

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 System Modeling and Simulation, vol. 1, no. 3, pp. 198–217, 2021.
Crossref Google Scholar
[22]

K. Gao, F. Yang, M. Zhou, Q. Pan, and P. N. Suganthan, Flexible job-shop rescheduling for new job insertion by using discrete Jaya algorithm, IEEE Trans. Cybern., vol. 49, no. 5, pp. 1944–1955, 2019.
Crossref Google Scholar
[23]

X. Wu, X. Xiao, and Q. Cui, Multi-objective flexible flow shop batch scheduling problem with renewable energy, Int. J. Autom. Control, vol. 14,nos.5-6, pp. 519–553, 2020.
Crossref Google Scholar
[24]

K. Z. Gao, P. N. Suganthan, T. J. Chua, C. S. Chong, T. X. Cai, and Q. K. Pan, A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion, Expert Syst. Appl., vol. 42, no. 21, pp. 7652–7663, 2015.
Crossref Google Scholar
[25]

Q. Liu, C. Wang, X. Li, and L. Gao, Mathematical modeling and a multiswarm collaborative optimization algorithm for fuzzy integrated process planning and scheduling problem, Tsing Science and Technology, vol. 29, no. 2, pp. 285–304, 2024.
Crossref Google Scholar
[26]

L. Sun, T. Lu, Z. Li, Y. Li, Y. Yu, and J. Liu, Research on steelmaking-continuous casting production scheduling problem with uncertain processing time based on Lagrangian relaxation framework, Int. J. Autom. Control, vol. 16, no. 1, pp. 87–107, 2022.
Crossref Google Scholar
[27]

K. Z. Gao, P. N. Suganthan, Q. K. Pan, T. J. Chua, T. X. Cai, and C. S. Chong, Pareto-based grouping discrete harmony search algorithm for multi-objective flexible job shop scheduling, Inf. Sci, vol. 289, pp. 76–90, 2014.
Crossref Google Scholar
[28]

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 System Modeling and Simulation, vol. 1, no. 3, pp. 176–197, 2021.
Crossref Google Scholar
[29]

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

K. Z. Gao, P. N. Suganthan, Q. K. Pan, M. F. Tasgetiren, and A. Sadollah, Artificial bee colony algorithm for scheduling and rescheduling fuzzy flexible job shop problem with new job insertion, Knowl. Based. Syst., vol. 109, pp. 1–16, 2016.
Crossref Google Scholar
[31]

K. Z. Gao, P. N. Suganthan, Q. K. Pan, T. J. Chua, C. S. Chong, and T. X. Cai, An improved artificial bee colony algorithm for flexible job-shop scheduling problem with fuzzy processing time, Expert Syst. Appl., vol. 65, pp. 52–67, 2016.
Crossref Google Scholar
[32]

H. Xiong, S. Shi, D. Ren, and J. Hu, A survey of job shop scheduling problem: The types and models, Comput. Oper. Res., vol. 142, p. 105731, 2022.
Crossref Google Scholar
[33]

J. Błażewicz, W. Domschke, and E. Pesch, The job shop scheduling problem: Conventional and new solution techniques, Eur. J. Oper. Res., vol. 93, no. 1, pp. 1–33, 1996.
Crossref Google Scholar
[34]

M. Dhiflaoui, H. E. Nouri, and O. B. Driss, Dual- resource constraints in classical and flexible job shop problems: A state-of-the-art review, Procedia Comput. Sci., vol. 126, pp. 1507–1515, 2018.
Crossref Google Scholar
[35]
R. G. Parker, Deterministic Scheduling Theory, CRC Press, 1996.
[36]

S. M. Johnson, An extension of johnson’s results on job lot scheduling, Nav. Res. Logist., vol. 3, pp. 201–203, 1956.
Crossref Google Scholar
[37]

W. E. Smith, Various optimizers for single-stage production, Nav. Res. Logist., vol. 3, pp. 59–66, 1956.
Crossref Google Scholar
[38]

B. Giffler and G. L. Thompson, Algorithms for solving production-scheduling problems, Oper. Res., vol. 8, no. 4, pp. 487–503, 1960.
Crossref Google Scholar
[39]
H. Fisher and G. L. Thompson, Probabilistic learning combinations of local job-shop scheduling rules, In : Muth JF and Thompson GL (eds ). Industrial Scheduling, Prentice-Hall : Englewood Cliffs, NJ, pp. 225– 251, 1963.
[40]
W. B. Crowston, F. Glover, and J. D. Trawick, Probabilistic and parametric learning combinations of local job shop scheduling rules, Research Report Carnegie Inst of Tech Pittsburgh Pa Graduate School of Industrial Administration, 1963.
Crossref
[41]
B. Jeremiah, A. Lalchandani, and L. Schrage, Heuristics Rules Toward Optimal Scheduling, Department of Industrial Engineering, Research Report, Cornell University, New York, USA, 1964.
[42]

G. H. Brooks, An algorithm for finding optimal or near optimal solutions to the production scheduling problem, J. Ind. Eng., vol. 16, no. 1, pp. 34–40, 1969.
Google Scholar
[43]
M. R. Garey and D. S. Johnson, Computers and Intertract-ability : A Guide to the Theory of NP- Completeness, Freeman, San Francisco, CA, 1979.
[44]
E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Recent developments in deterministic sequencing and scheduling: A survey, In Deterministic and Stochastic Scheduling: Proceedings of the NATO Advanced Study and Research Institute on Theoretical Approaches to Scheduling Problems held in Durham, England, pp. 35−73, 1981.
Crossref
[45]

M. Hefetz and I. Adiri, An efficient optimal algorithm for the two-machines unit-time job shop schedule-length problem, Math. Oper. Res., vol. 7, no. 3, pp. 354–360, 1982.
Crossref Google Scholar
[46]
Y. N. Sotskov, Optimal scheduling two jobs with regular criterion, Design Processes Automating, pp. 86–95, 1985.
[47]

P. Brucker, An efficient algorithm for the job-shop problem with two jobs, Computing, vol. 40, no. 4, pp. 353–359, 1988.
Crossref Google Scholar
[48]
N. M. Sadeh, Look-ahead techniques for micro- opportunistic job shop scheduling, Research Report, Carnegie Mellon University, 1991.
[49]

M. Charalambous and K. S. Hindi, A review of artificial intelligence-based job-shop scheduling systems, Information and Decision Technologies, vol. 17, no. 3, pp. 189–202, 1991.
Google Scholar
[50]
D. N. Zhou, V. Cherkassky, T. R. Baldwin, and D. W. Hong, Scaling neural network for job-shop scheduling, In 1990 IJCNN International Joint Conference on Neural Networks, San Diego, CA, USA, 1990, vol.3, pp. 889−894.
Crossref
[51]

D. N. Zhou, V. Cherkassky, T. R. Baldwin and D. E. Olson, A neural network approach to job-shop scheduling, IEEE Trans. Neural Netw., vol. 2, no. 1, pp. 175–179, 1991.
Crossref Google Scholar
[52]

T. A. J. Nicholson, A sequential method for discrete optimization problems and its application to the assignment, travelling salesman, and three machine scheduling problems, IMA J. Appl. Math., vol. 3, no. 4, pp. 362–375, 1967.
Crossref Google Scholar
[53]

S. Kirkpatrick, C. D. Gelatt Jr, and M. P.Vecchi, Optimization by simulated annealing, Science, vol. 220, no. 4598, pp. 671–680, 1983.
Crossref Google Scholar
[54]

F. Glover, Tabu search—part I, ORSA J. Comput., vol. 1, no. 3, pp. 190–206, 1989.
Crossref Google Scholar
[55]

F. Glover, Tabu search—part Ⅱ, ORSA J. Comput., vol. 2, no. 1, pp. 4–32, 1990.
Crossref Google Scholar
[56]

J. Adams, E. Balas, and D. Zawack, The shifting bottleneck procedure for job shop scheduling, Manage. Sci., vol. 34, no. 3, pp. 391–401, 1988.
Crossref Google Scholar
[57]

N. J. Van Laarhoven, E. H. Aarts, and J. K. Lenstra, Job shop scheduling by simulated annealing, Oper. Res., vol. 40, no. 1, pp. 113–125, 1992.
Crossref Google Scholar
[58]
E. H. L. Aarts, P. J. M. Van Laarhooven, and N. L. J. Ulder, Local search based algorithms for job-shop scheduling, Working Paper, Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands, 1991.
[59]
E. Taillard, Parallel taboo search technique for the job- shop scheduling problem, Internal Research Report ORWP89/11, Department de Mathematiques (DMA), Ecole Polytechnique Federale de Lausanne, 1015 Lausanne Switzerland, 1989.
[60]

E. Balas and A. Vazacopoulos, Guided local search with shifting bottleneck for job shop scheduling, Manage. Sci., vol. 44, no. 2, pp. 262–275, 1998.
Crossref Google Scholar
[61]

E. Nowicki and C. Smutnicki, An advanced tabu search algorithm for the job shop problem, J. Scheduling, vol. 8, no. 2, pp. 145–159, 2005.
Crossref Google Scholar
[62]

M. L. Fisher and A. H. Rinnooy Kan, The design, analysis and implementation of heuristics, Manage. Sci., vol. 34, no. 3, pp. 263–265, 1988.
Crossref Google Scholar
[63]

F. Della 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.
Crossref Google Scholar
[64]
H. L. Fang, P. Ross, and D. Corne, A promising genetic algorithm approach to job-shop scheduling, rescheduling, and open-shop scheduling problems, Berlin, Heidelberg: University of Edinburgh, Department of Artificial Intelligence, pp. 375−382, 1993.
[65]

A. Colorni, M. Dorigo, V. Maniezzo, and M. Trubian, Ant system for job-shop scheduling, JORBEL-Belgian Journal of Operations Research, Statistics, and Computer Science, vol. 34, no. 1, pp. 39–53, 1994.
Google Scholar
[66]

Z. Lian, B. Jiao, and X. Gu, A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespan, Appl. Math. Comput., vol. 183, no. 2, pp. 1008–1017, 2006.
Crossref Google Scholar
[67]

O. Niu, B. Jiao, and X. Gu, Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time, Appl. Math. Comput., vol. 205, no. 1, pp. 148–158, 2008.
Crossref Google Scholar
[68]

P. M. Pardalos and O. V. Shylo, An algorithm for the job shop scheduling problem based on global equilibrium search techniques, Comput. Manag. Sci., vol. 3, no. 4, pp. 331–348, 2006.
Crossref Google Scholar
[69]

G. Zhang, X. Shao, P. Li, and L. Gao, An effective hybrid particle swarm optimization algorithm for multi- objective flexible job-shop scheduling problem, Comput. Ind. Eng., vol. 56, no. 4, pp. 1309–1318, 2009.
Crossref Google Scholar
[70]

D. C. Mattfeld, C. Bierwirth, and H. Kopfer, A search space analysis of the job shop scheduling problem, Ann. Oper. Res., vol. 86, pp. 441–453, 1999.
Crossref Google Scholar
[71]
C. Bierwirth, D. C. Mattfeld, and J. P. Watson, Landscape regularity and random walks for the job-shop scheduling problem, In European Conference on Evolutionary Computation in Combinatorial Optimization (pp. 21-30). Springer, Berlin, Heidelberg, 2004.
Crossref
[72]

M. J. Streeter and S. F. Smith, How the landscape of random job shop scheduling instances depends on the ratio of jobs to machines, J. Artif. Intell. Res., vol. 26, pp. 247–287, 2006.
Crossref Google Scholar
[73]

P. M. Pardalos, O. V. Shylo, and A. Vazacopoulos, Solving job shop scheduling problems utilizing the properties of backbone and “big valley”, Comput. Optim. Appl., vol. 47, no. 1, pp. 61–76, 2010.
Crossref Google Scholar
[74]

J. Li, X. Gu, Y. Zhang, and X. Zhou, Distributed flexible job-shop scheduling problem based on hybrid chemical reaction optimization algorithm, Complex System Modeling and Simulation, vol. 2, no. 2, pp. 156–173, 2022.
Crossref Google Scholar
[75]
S. H. Niu, S. K. Ong, and A. Y. C. Nee, An improved intelligent water drops algorithm for achieving optimal job-shop scheduling solutions, Int. J. Prod. Res., vol. 50, no. 15, pp. 4192–4205, 2012.
Crossref
[76]

B. Wu, J. Cheng, and M. Dong, Hybrid fruit fly optimisation algorithm for field service scheduling problem, Int. J. Autom. Control, vol. 14, no. 5-6, pp. 554–570, 2020.
Crossref Google Scholar
[77]

S. Wang, C. Liu, D. Pei, and J. Wang, A novel hybrid election campaign optimisation algorithm for multi- objective flexible job-shop scheduling problem, Int. J. Struct. Integr., vol. 7, no. 3, pp. 160–170, 2013.
Crossref Google Scholar
[78]

S. Wang, G. Liu, and S. Gao, A hybrid discrete imperialist competition algorithm for fuzzy job-shop scheduling problems, IEEE Access, vol. 4, pp. 9320–9331, 2017.
Crossref Google Scholar
[79]

C. Aranha, C. L. Camacho Villaló n, F. Campelo, M. Dorigo, R. Ruiz, M. Sevaux, K. Sörensen, and T. Stü tzle, Metaphor-based metaheuristics, a call for action: the elephant in the room, Swarm Intell., vol. 16, no. 1, pp. 1–6, 2022.
Crossref Google Scholar
[80]

S. Nguyen, M. Zhang, M. Johnston, and K. C. Tan, A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem, IEEE Trans. Evol. Comput., vol. 17, no. 5, pp. 621–639, 2012.
Crossref Google Scholar
[81]
S. Mirshekarian and D. N. Šormaz,Correlation of job- shop scheduling problem features with scheduling efficiency, Expert Syst. Appl., vol. 62, pp. 131–147, 2016.
Crossref
[82]

Z. C. Li, B. Qian, R. Hu, L. L. Chang, and J. B. Yang, An elitist nondominated sorting hybrid algorithm for multi- objective flexible job-shop scheduling problem with sequence-dependent setups, Knowl. Based Syst., vol. 173, pp. 83–112, 2019.
Crossref Google Scholar
[83]

E. R. Marsh, The harmonogram: An overlooked method of scheduling work, Proj. Manage. Q., vol. 7, no. 1, pp. 21–25, 1976.
Google Scholar
[84]
H. L. Gantt, Work, Wages and Profits, Engineering Magazine Co., New York, 1916.
[85]
W. Clark, The Gantt chart : A working tool of management, Ronald Press Company, 1922.
[86]
B. Roy and B. Sussman, Les problem`es d’ ordonnancement avec contraintes disjonctives (in French ). Note DS No. 9 bis, SEMA, Montrouge, 1964.
[87]

K. P. White and R. V. Rogers, Job-shop scheduling: Limits of the binary disjunctive formulation, Int. J. Prod. Res., vol. 28, no. 12, pp. 2187–2200, 1990.
Crossref Google Scholar
[88]

L. Gui, L. Fu, X. Li, W. Zhou, L. Gao, Z. Xiang, and W. Zhu, Optimisation framework and method for solving the serial dual-shop collaborative scheduling problem, Int. J. Prod. Res., vol. 61, pp. 4341–4357, 2022.
Crossref Google Scholar
[89]

J. Bazewicz, W. Domschke, and E. Pesch, The job shop scheduling problem: Conventional and new solution techniques, Eur. J. Oper. Res., vol. 93, no. 1, pp. 1–33, 1996.
Crossref Google Scholar
[90]

E. Nowicki and C. Smutnicki, A fast taboo search algorithm for the job shop problem, Manage. Sci., vol. 42, no. 6, pp. 797–813, 1996.
Crossref Google Scholar
[91]

S. Wright, The roles of mutation, inbreeding, crossbreeding, and selection in evolution, Proceedings of the Sixth international Congress of Genetics, vol. 1, pp. 356–366, 1932.
Google Scholar
[92]
J. E. Kelley Jr and M. R. Walker, Critical-path planning and scheduling. In Papers presented at the December, Eastern Joint IRE-AIEE-ACM Computer Conference pp. 160−173, 1959.
Crossref
[93]
P. W. Conway, W. L. Maxwell and L. W. Miller, Theory of Scheduling, Addison-Wesley : Reading, MA, 1967.
[94]

C. N. Potts, Analysis of a heuristic for one machine sequencing with release dates and delivery times, Oper. Res., vol. 28, no. 6, pp. 1436–1441, 1980.
Crossref Google Scholar
[95]
J. Grabowski, E. Nowicki, and C. Smutnicki, Block algorithm for scheduling of operations in job-shop system (in Polish), Przeglad Statystyczny, vol. 35, pp. 67–80, 1988.
[96]

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, pp. 1–16, 2023.
Crossref Google Scholar
[97]

E. Taillard, Parallel taboo search techniques for the job shop scheduling problem, ORSA J. Comput., vol. 6, no. 2, pp. 108–117, 1994.
Crossref Google Scholar
[98]

L. Gui, X. Li, L. Gao, and J. Xie, An approximate evaluation method for neighbourhood solutions in job shop scheduling problem, IET CIM, vol. 4, no. 3, pp. 157–165, 2022.
Crossref Google Scholar
[99]
C. E. Nugent, On Sampling Approaches to the Solution of the n-by-m Static Sequencing Problem, Ph.D. dissertation, Cornell University, USA, 1964.
[100]

C. Zhang, Y. Rao, and P. Li, An effective hybrid genetic algorithm for the job shop scheduling problem, Int. J. Adv. Manuf. Technol., vol. 39, no. 9, pp. 965–974, 2008.
Crossref Google Scholar
[101]
O. V. Shylo and H. Shams, Boosting binary optimization via binary classification: A case study of job shop scheduling. arXiv preprint arXiv: 1808.10813, 2018. M.
[102]
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.
Crossref
[103]

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.
Crossref Google Scholar
[104]

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, pp. 108205, 2022.
Crossref Google Scholar
[105]
Lawrence, Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques (Relatório técnico), dissertation, Carnegie Mellon University, Pittsburgh, USA, 1984.
[106]

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.
Crossref Google Scholar
[107]

R. H. Storer, S. D. Wu, and R. Vaccari, New search spaces for sequencing problems with application to job shop scheduling, Manage. Sci., vol. 38, no. 10, pp. 1495–1509, 1992.
Crossref Google Scholar
[108]
T. Yamada and R. Nakano, A genetic algorithm applicable to large-scale job-shop problems, In PPSN vol. 2, pp. 281−290, 1992.
[109]

E. Taillard, Benchmarks for basic scheduling problems, Eur. J. Oper. Res., vol. 64, no. 2, pp. 278–285, 1993.
Crossref Google Scholar
[110]

E. Demirkol, S. Mehta, and R. Uzsoy, Benchmarks for shop scheduling problems, Eur. J. Oper. Res., vol. 109, no. 1, pp. 137–141, 1998.
Crossref Google Scholar
[111]

W. Brinkkötter and P. Brucker, Solving open benchmark instances for the job‐shop problem by parallel head–tail adjustments, 3.0.CO;2-Y">J. Scheduling, vol. 4, no. 1, pp. 53–64, 2001.
Crossref Google Scholar
[112]

C. 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.
Crossref Google Scholar
[113]

J. C. Beck, T. K. Feng, and J. P. Watson, Combining constraint programming and local search for job-shop scheduling, INFORMS J. Comput., vol. 23, no. 1, pp. 1–14, 2011.
Crossref Google Scholar
[114]
J. F. Gonçalves and M. G. Resende, A biased random- key genetic algorithm for job-shop scheduling, AT&T Labs Research Technical Report, vol. 46, pp. 253−271, 2011.
[115]

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.
Crossref Google Scholar
[116]

O. H. Constanino and C. Segura, A parallel memetic algorithm with explicit management of diversity for the job shop scheduling problem, Appl. Intell., vol. 52, no. 1, pp. 141–153, 2022.
Crossref Google Scholar
[117]

E. Demirkol, S. Mehta, and R. Uzsoy, A computational study of shifting bottleneck procedures for shop scheduling problems, J. Heuristics, vol. 3, no. 2, pp. 111–137, 1997.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 29 Issue 5,
October 2024
Pages 1368-1389
DOI: 10.26599/TST.2023.9010140
Cite this article:
Gui L, Li X, Zhang Q, et al. Domain Knowledge Used in Meta-Heuristic Algorithms for the Job-Shop Scheduling Problem: Review and Analysis. Tsinghua Science and Technology, 2024, 29(5): 1368-1389. https://doi.org/10.26599/TST.2023.9010140

376

Views

74

Downloads

2

Crossref

2

Web of Science

3

Scopus

0

CSCD

Altmetrics
Received: 18 July 2023
Revised: 11 November 2023
Accepted: 13 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