A novel threshold accepting meta-heuristic for the job-shop scheduling problem

A novel threshold accepting meta-heuristic for the job-shop scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor2005510
Country: United Kingdom
Volume: 31
Issue: 13
Start Page Number: 2199
End Page Number: 2213
Publication Date: Nov 2004
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics
Abstract:

A novel list based threshold accepting (LBTA) algorithm is proposed for solving the job-shop scheduling problem. The LBTA algorithm belongs to the class of threshold accepting algorithms but the acceptance probability decreases based on a list that is rejuvenated and adapted according to the topology of the solution space of the problem. A probabilistic steepest optimization strategy was adapted to search the solution space effectively. The most prominent advantage of the LBTA algorithm over other local search methods is that it is simple and easy to implement, needs less problem specific knowledge, and is effectively tuning free. Computational experiments on a set of benchmark problems show that the proposed method gives optimal and very near-optimal solution results within a short computation time.

Reviews

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