Paper Title
THE LONGEST PATH ALGORITHM TO ACCELERATE SCHEDULING IMPROVEMENT HEURISTICS

Abstract
Abstract – The goal of this research is to accelerate improvement heuristics which use a graph to model the system and calculates the makespan, i.e., longest path in the graph, during each iteration. These heuristics iteratively perturb the graph and recalculate the makespan in each iteration until a satisfactory schedule is determined. We propose Improved Structural Perturbation Algorithm (ISPA) to accelerate the calculation of the length of the longest path in the graph in each iteration. This will decrease the overall computation time of these scheduling improvement heuristics. Scheduling perturbations are represented by structural perturbations of the graph (edge additions and deletions). ISPA partitions nodes in the graph into two types of sets and applies two different processes to calculate the effects of the perturbations depending on the set the node was in. The major contribution of this study is that ISPA executes once to update the length of the longest path regardless of the number of added and deleted edges. This results in a more efficient algorithm in terms of time complexity than previous algorithms. To show this performance improvement, an experiment was performed applying ISPA to a Simulated Annealing (SA) heuristic and compare it with applying the commonly used Standard Longest Path Algorithm (SLPA) and two other existing methods to the SA heuristic. The experiment shows that ISPA outperforms existing methods in all cases. Moreover, for these SA problems, ISPA saved 9%-65% of the execution time compared to SLPA for the job-shop scheduling problems. The time savings increase with size (number of nodes) of the problem. ISPA is applicable to other iterative heuristics, such as Tabu-search, Genetic Algorithms, and Shifting Bottleneck.