Bounded dynamic programming algorithm for the job shop problem with sequence dependent setup times

In this paper, the job shop scheduling problem (JSP) with a makespan minimization criterion is investigated. Various approximate algorithms exist that can solve moderate JSP instances within a reasonable time limit. However, only a few exact algorithms are known in the literature. We have developed an exact algorithm by means of a bounded dynamic programming (BDP) approach. This approach combines elements of a dynamic programming with elements of a branch and bound method. In addition, a generalization is investigated: the JSP with sequence dependent setup times (SDST-JSP). The BDP algorithm is adapted for this problem. To the best of our knowledge, the dynamic programming approach has never been applied to the SDST-JSP before. The BDP algorithm can directly be used as a heuristic. Computational results show that the proposed algorithm can solve benchmark instances up to 20 jobs and 15 machines for the JSP. For the SDST-JSP, the proposed algorithm outperforms all the state-of-the-art exact algorithms and the best-known lower bounds are improved for 5 benchmark instances.