A very fast TS/SA algorithm for the job shop scheduling problem

作者：Zhang Chao Yong^*; Li PeiGen; Rao YunQing; Guan ZaiLin

来源：Computers & Operations Research, 2008, 35(1): 282-294.

DOI：10.1016/j.cor.2006.02.024

• job shop scheduling problem
• tabu search
• simulated annealing
• makespan

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.

• 出版日期2008-1
• 单位华中科技大学