作业车间调度的拓扑排序及其在邻域解动态构造中的应用

黄学文, 王达, 王强

系统工程理论与实践 ›› 2024, Vol. 44 ›› Issue (5) : 1680-1698.

PDF(445 KB)
中国科学院数学与系统科学研究院期刊网
PDF(445 KB)
系统工程理论与实践 ›› 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 +
文章历史 +

摘要

在求解作业车间调度问题(job-shop scheduling problem, JSP)的局部搜索算法中,构造移动执行后的邻域解严重影响了局部搜索算法的计算效率.为此,基于拓扑排序和工序最大弧数的相关理论,提出了调度解拓扑排序的划分方法,实现了邻域解拓扑排序的构造;并在邻域解的拓扑排序中,准确地识别了邻域解中头和尾时间发生改变的工序集合,从而实现了邻域解的快速、 动态构造.实验结果表明: 相比于目前的邻域解构造方法,所提出的邻域解的动态构造方法,在计算速度上有着明显优势,且能够显著地节省计算时间.

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

引用本文

EndNote

Ris (Procite)

Bibtex

导出引用
黄学文 , 王达 , 王强. 作业车间调度的拓扑排序及其在邻域解动态构造中的应用. 系统工程理论与实践, 2024, 44(5): 1680-1698 https://doi.org/10.12011/SETP2022-2817
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
中图分类号： TP18    TH165   

参考文献

[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.

基金

国家自然科学基金(72073018)
PDF(445 KB)

545

Accesses

0

Citation

Detail
段落导航
相关文章

/

〈 〉