Topological order for job-shop scheduling and its application in dynamically generating neighbouring solutions
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 determin-ing 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 topo-logical 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.
NETL
NSTL
万方数据
