A Local Search Algorithm with a New Acceptance Rule: Application to the Flow-Shop Scheduling Problem

N. Nahas and T.-M. Dao (Canada)


Metaheuristics, local search, threshold acceptance, RC filters, flow-shop scheduling problem.


Local search algorithms are a wide class of improvement algorithms where at each iteration an improving solution is found by searching the neighborhood of the current solution. Stochastic hill climbing algorithms (simulated an nealing, Threshold acceptance algorithm,..) are optimization techniques which belong to the family of local search. In this paper, we propose a new variant of local search algorithm. The main difference compared to the existent algorithms resides in its mechanism of accepting or rejecting the candidate solution from the neighborhood. In the proposed version, the acceptance criteria is inspired from the RC filter which is a low-pass filter used in electronic to reduce the amplitude of signals with higher frequencies. The performance of the algorithm is illustrated with the flow shop scheduling problem.

Important Links:

Go Back