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

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

作　　者：黄学文[1] 王达[1] 王强[1] HUANG Xuewen;WANG Da;WANG Qiang(School of Economics and Management,Dalian University of Technology,Dalian 116024,China)

机构地区：[1]大连理工大学经济管理学院,大连116024

出　　处：《系统工程理论与实践》2024年第5期1680-1698,共19页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(72073018)。

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

关 键 词：动态构造 邻域解 拓扑排序 作业车间调度 邻域结构 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TH165[自动化与计算机技术—控制科学与工程]