Minimizing L max for large-scale, job-shop scheduling problems

The academic literature in 2000 presented a procedure for solving the job-shop-scheduling problem of minimizing L max. The iterative-adaptive simulation-based procedure is shown here to perform well on large-scale problems. However, there is potential for improvement in closing the gap between best-known solutions and the lower bound. In the present paper, a simulated annealing post-processing procedure is presented and evaluated on large-scale problems. A new neighbourhood structure for local searches in the job-shop scheduling problem is developed. The procedure is also evaluated using benchmark problems and new upper bounds are established.