Article ID: | iaor20084370 |
Country: | United Kingdom |
Volume: | 35 |
Issue: | 1 |
Start Page Number: | 282 |
End Page Number: | 294 |
Publication Date: | Jan 2008 |
Journal: | Computers and Operations Research |
Authors: | Li PeiGen, Guan ZaiLin, Rao YunQing, Zhang Chao Yong |
Keywords: | heuristics: tabu search, optimization: simulated annealing |
The job shop scheduling problem (JSP) is one of the most notoriously intractable NP-complete optimization problems. Over the last 10–15 years, tabu search (TS) has emerged as an effective algorithmic approach for the JSP. However, the quality of solutions found by tabu search approach depends on the initial solution. To overcome this problem and provide a robust and efficient methodology for the JSP, the heuristics search approach combining simulated annealing (SA) and TS strategy is developed. The main principle of this approach is that SA is used to find the elite solutions inside big valley (BV) so that TS can re-intensify search from the promising solutions. This hybrid algorithm is tested on the standard benchmark sets and compared with the other approaches. The computational results show that the proposed algorithm could obtain the high-quality solutions within reasonable computing times. For example, 17 new upper bounds among the unsolved problems are found in a short time.