A common way to represent a deterministic job shop is by a graph, where the nodes represent the operations and edges represent the sequence of the operations along with the schedule. Makespan is the popular measurement used to measure the efficiency of a manufacturing system. Previous research has shown that a very computational efficient mechanism to calculate the makespan of such systems is to first perform a topological sort of the operations, and then determine the completion time of the operations using dynamic programming. In the current study, an efficient algorithm is introduced that will efficiently compute the effects of perturbations in the operation times on the makespan.
