A new exact algorithm for no-wait job shop problem to minimize makespan

In this paper, the no-wait job shop scheduling problem with a makespan objective is considered. A new exact algorithm, which is based on the dynamic programming (DP), is proposed. We introduce a dominance relation between two timetables. Several theorems are provided showing the application of the dominance. Despite the theoretical interest, experimental results prove that the proposed algorithm is able to optimally solve moderate benchmark instances within a reasonable time limit. Moreover, we have shown that the use of the dominance effectively reduces the state space of the algorithm. As an extension of the DP algorithm, we also present its heuristic version. It is shown that good quality upper bounds for large-size benchmark instances can be obtained. A comparison among several algorithms presented in the literature shows that the DP algorithm is quite competitive in terms of the computational time and the quality of obtained solutions.