Finding All Optimal Solutions for the Job Shop Scheduling Problem

In [1] we described a dynamic programming algorithm to solve the job shop scheduling problem. We improved this algorithm by adding bounds. We will shortly present these results. We create an algorithm based on this dynamic programming algorithm to find all optimal solutions. For almost all small benchmark instances we were able to find all optimal instances. We will see that the number of optimal instances over differs quite a lot over the different instances. 

[1] Gromicho, J., van Hoorn, J., Saldanha da Gama, F., Timmer, G.; Solving the job-shop scheduling problem optimally by dynamic programming; Computers and Operations Research (2012); doi:10.1016/j.cor.2012.02.024.1

Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.