Topological order for job-shop scheduling and its application in dynamically generating neighbouring solutions

HUANG Xuewen, WANG Da, WANG Qiang

Systems Engineering - Theory & Practice ›› 2024, Vol. 44 ›› Issue (5) : 1680-1698.

PDF(445 KB)
PDF(445 KB)
Systems Engineering - Theory & Practice ›› 2024, Vol. 44 ›› Issue (5) : 1680-1698. DOI: 10.12011/SETP2022-2817

Topological order for job-shop scheduling and its application in dynamically generating neighbouring solutions

  • HUANG Xuewen, WANG Da, WANG Qiang
Author information +
History +

Abstract

In the local search for solving the job-shop scheduling problem (JSP), the process of generating the neighbouring solution after performing a move plays a crucial role in determining the computational efficiency of the algorithm. In this regard, a partitioning method for the topological order of a schedule solution is proposed, based on the theories related to the topological order and the maximum arc number of an operation. This method is utilized to generate the topological order of a neighbouring solution. Additionally, the proposed method accurately identifies the set of operations whose head or tail is changed in the neighbouring solution, within the resulting topological order. This enables the fast and dynamic generation of neighbouring solutions. Experimental results demonstrate that the proposed dynamic method offers significant advantages in terms of computational efficiency, leading to considerable savings in computational time compared to existing generation methods.

Key words

dynamical generation / neighboring solution / topological order / job-shop scheduling problem / neighborhood structure

Cite this article

Download Citations
HUANG Xuewen , WANG Da , WANG Qiang. Topological order for job-shop scheduling and its application in dynamically generating neighbouring solutions. Systems Engineering - Theory & Practice, 2024, 44(5): 1680-1698 https://doi.org/10.12011/SETP2022-2817

References

[1] Kurdi M. An effective new island model genetic algorithm for job shop scheduling problem[J]. Computers & Operations Research, 2016, 67: 132-142.
[2] 黄学文, 陈绍芬, 周阗玉, 等. 求解柔性作业车间调度问题的一种新邻域结构[J]. 系统工程理论与实践, 2021, 41(9): 2367-2378.Huang X W, Chen S F, Zhou T Y, et al. A new neighborhood structure for solving the flexible job-shop scheduling problem[J]. Systems Engineering—Theory & Practice, 2021, 41(9): 2367-2378.
[3] Rossit D A, Vásquez ó C, Tohmé F, et al. A combinatorial analysis of the permutation and non-permutation flow shop scheduling problems[J]. European Journal of Operational Research, 2021, 289(3): 841-854.
[4] Xie J, Li X, Gao L, et al. A hybrid algorithm with a new neighborhood structure for job shop scheduling problems[J]. Computers & Industrial Engineering, 2022, 169: 108205.
[5] Blazewicz J, Domschke W, Pesch E. The job shop scheduling problem: Conventional and new solution techniques[J]. European Journal of Operational Research, 1996, 93(1): 1-33.
[6] Asadzadeh L. A local search genetic algorithm for the job shop scheduling problem with intelligent agents[J]. Computers & Industrial Engineering, 2015, 85: 376-383.
[7] Murovec B. Job-shop local-search move evaluation without direct consideration of the criterion's value[J]. European Journal of Operational Research, 2015, 241(2): 320-329.
[8] van Laarhoven P J M, Aarts E H L, Lenstra J K. Job shop scheduling by simulated annealing[J]. Operations Research, 1992, 40(1): 113-125.
[9] Matsuo H, Juck Suh C, Sullivan R S. A controlled search simulated annealing method for the single machine weighted tardiness problem[J]. Annals of Operations Research, 1989, 21(1): 85-108.
[10] Nowicki E, Smutnicki C. A fast taboo search algorithm for the job shop problem[J]. Management Science, 1996, 42(6): 797-813.
[11] Dell'Amico M, Trubian M. Applying tabu search to the job-shop scheduling problem[J]. Annals of Operations Research, 1993, 41(1-4): 231-252.
[12] Balas E, Vazacopoulos A. Guided local search with shifting bottleneck for job shop scheduling[J]. Management Science, 1998, 44(2): 262-275.
[13] Zhang C Y, Li P G, Guan Z L, et al. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem[J]. Computers & Operations Research, 2007, 34(11): 3229-3242.
[14] Ten Eikelder H M M, Aarts B J M, Verhoeven M G A, et al. Sequential and parallel local search algorithms for job shop scheduling[M]. Massachusetts: Kluwer Academic Publishers, 1999: 359-371.
[15] Taillard E D. Parallel taboo search techniques for the job shop scheduling problem[J]. ORSA Journal on Computing, 1994, 6(2): 108-117.
[16] Bellman R. On a routing problem[J]. Quarterly of Applied Mathematics, 1958, 16(1): 87-90.
[17] Nowicki E, Smutnicki C. An advanced tabu search algorithm for the job shop problem[J]. Journal of Scheduling, 2005, 8(2): 145-159.
[18] Nasiri M M, Kianfar F. A guided tabu search/path relinking algorithm for the job shop problem[J]. International Journal of Advanced Manufacturing Technology, 2012, 58(9-12): 1105-1113.
[19] Braune R, Zaepfel G, Affenzeller M. Enhancing local search algorithms for job shops with min-sum objectives by approximate move evaluation[J]. Journal of Scheduling, 2013, 16(5): 495-518.
[20] Zeng C K, Tang J F, Yan C J. Job-shop cell-scheduling problem with inter-cell moves and automated guided vehicles[J]. Journal of Intelligent Manufacturing, 2015, 26(5): 845-859.
[21] 赵诗奎. 作业车间调度问题的多工序联动邻域结构研究[J]. 机械工程学报, 2020, 56(13): 192-206. Zhao S K. Research on multi-operation joint movement neighborhood structure of job shop scheduling problem[J]. Journal of Mechanical Engineering, 2020, 56(13): 192-206.
[22] Zeng C, Qi G, Liu Z, et al. Auction-based approach with improved disjunctive graph model for job shop scheduling problem with parallel batch processing[J]. Engineering Applications of Artificial Intelligence, 2022, 110: 104735.
[23] Balas E. Machine sequencing via disjunctive graphs: An implicit enumeration algorithm[J]. Operations Research, 1969, 17(6): 941-957.
[24] Bierwirth C, Kuhpfahl J. Extended GRASP for the job shop scheduling problem with total weighted tardiness objective[J]. European Journal of Operational Research, 2017, 261(3): 835-848.
[25] 孙在省, 钱斌, 胡蓉, 等. 基于块结构性质的花粉算法求解可重入作业车间调度问题[J]. 机械工程学报, 2019, 55(16): 220-232. Sun Z X, Qian B, Hu R. Flower pollination algorithm based on block structure properties for reentrant job shop scheduling problem[J]. Journal of Mechanical Engineering, 2019, 55(16): 220-232.
[26] 巴智勇, 袁逸萍, 裴国庆, 等. 作业车间调度的多工序精确联动邻域结构混合进化算法[J/OL]. 计算机集成制造系统, 1-29 [2024-02-05]. http://kns.cnki.net/kcms/detail/11.5946.tp.20230104.1157.008.html. Ba Z Y, Yuan Y P, Pei G Q, et al. Hybrid evolutionary algorithm with multi-operation precise joint movement neighborhood structure for the job shop scheduling problem[J/OL]. Computer Integrated Manufacturing System, 1-29 [2024-02-05]. http://kns.cnki.net/kcms/detail/11.5946.tp.20230104.1157.008.html.
[27] Kuhpfahl J, Bierwirth C. A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective[J]. Computers & Operations Research, 2016, 66: 44-57.
[28] Xie J, Li X, Gao L, et al. A new neighbourhood structure for job shop scheduling problems[J]. International Journal of Production Research, 2023, 61(7): 2147-2161.
[29] Murovec B, Auhel P. A repairing technique for the local search of the job-shop problem[J]. European Journal of Operational Research, 2004, 153(1): 220-238.
[30] Marchetti-Spaccamela A, Nanni U, Rohnert H. Maintaining a topological order under edge insertions[J]. Information Processing Letters, 1996, 59(1): 53-58.
[31] Zhou J, Müller M. Depth-first discovery algorithm for incremental topological sorting of directed acyclic graphs[J]. Information Processing Letters, 2003, 88(4): 195-200.
[32] Pearce D J, Kelly P H. A dynamic topological sort algorithm for directed acyclic graphs[J]. Journal of Experimental Algorithmics (JEA), 2007, 11: 1-7.
[33] Fisher H, Thompson G L. Probabilistic learning combinations of local job-shop scheduling rules[M]. Englewood Cliffs, New Jersey: Prentice Hall, 1963: 225-251.
[34] Taillard E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2): 278-285.

Funding

National Natural Science Foundation of China (72073018)
PDF(445 KB)

506

Accesses

0

Citation

Detail

Sections
Recommended

/