Optimization method with large leap steps for job shop scheduling

Local search methods have the characteristic of obtaining decent solution with short or acceptable time for job shop scheduling problems. They improve solution by searching iteratively neighbors of initial solution. But, they tend to get trapped in local optimal solutions, usually far away from the global optimal solution. Simulated annealing methods try to improve on this by accepting uphill moves depending on a decreasing probability controlled by the temperature parameter. But, at small temperatures, they also tend to get stuck in valleys of the cost function. In this paper, we proposed an optimization method with large leap steps. The large leap steps of the optimization method allow one to leave these valleys even at small temperatures. Experiments on some job shop scheduling benchmark problems demonstrated the effectiveness and efficiency of the optimization method with large leap steps.