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

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

0.00 Avg rating0 Votes
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: , , ,
Keywords: heuristics: tabu search, optimization: simulated annealing
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.