A theoretical framework to accelerate scheduling improvement heuristics using a new longest path algorithm in perturbed DAGs

Job-shop scheduling problems are complex and still well-studied manufacturing problems. Improvement heuristic algorithms have been proposed to solve the scheduling problems using makespan as their performance measure. All these heuristics iteratively perturb trial schedules by selecting a new schedule from a set of nearby schedules (neighbourhood); then, recalculate and compare the makespan until a sufficient schedule is determined. Unlike previous studies, we did not generate a new heuristic or a novel neighbourhood calculation. Instead, we proposed a theoretical framework, Algorithm to Visit Affected Node (AVAN), which can be incorporated in qualified heuristics while using their current neighbourhood structure to accelerate the recalculation of the makespan in each iteration. We modelled the system by Directed Acyclic Graph (DAG) where the length of the longest path equals the makespan. The scheduling perturbations are represented by adding and deleting edges. AVAN investigates the configuration of scheduling perturbations (added/deleted edges) to find an appropriate starting point to traverse the graph. AVAN is mathematically more efficient than previous longest path algorithms for perturbed DAG. Its time complexity is $ \textrm{O}({\Delta + \vert {\Delta } \vert \log ({\vert \Delta \vert } )} ) $ O(Δ+|Δ|log⁡(|Δ|)), where $ \vert {\Delta } \vert $ |Δ| is the number of affected nodes and $ \Delta $ Δ is the number of incoming and outgoing edges of the affected nodes.