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

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. (C) 2003 Elsevier Ltd. All rights reserved.