Job-shop scheduling: Computational study of local search and large-step optimization methods

We present a computational study of different local search and large-step optimization methods to solve the job-shop scheduling problem. We review local optimization methods and propose a two-phase optimization method, known as large-step optimization, which has recently been introduced for the traveling salesman problem. The first phase of this new method consists of a large optimized transition in the current solution, while the second phase is basically a local search method. We present extensive computational results obtained from various combinations of local search and large-step optimization techniques. From the computational results we can conclude that the large-step optimization methods outperform the simulated annealing method and find more frequently an optimal schedule than the other studied methods.