Hybrid simulated annealing with memory: an evolution-based diversification approach

Abstract

This study presents an efficient metaheuristic approach for combinatorial optimisation and scheduling problems. The hybrid algorithm proposed in this paper integrates different features of several well-known heuristics. The core component of the proposed algorithm is a simulated annealing module. This component utilises three types of memories, one long-term memory and two short-term memories. The main characteristics of the proposed metaheuristic are the use of positive (reinforcement) and negative (inhibitory) memories as well as an evolution-based diversification approach. Job shop scheduling is selected to evaluate the performance of the proposed method. Given the benchmark problem, an extended version of the proposed method is also developed and presented. The extended version has two distinct features, specifically designed for the job shop scheduling problem, that enhance the performance of the search. The first feature is a local search that partially explores alternative solutions on a critical path of any current solution. The second feature is a mechanism to resolve possible deadlocks that may occur during the search as a result of shortage in acceptable solutions. For the case of job shop scheduling, the computational results and comparison with other techniques demonstrate the superior performance of the proposed methods in the majority of cases.

Keywords:

• simulated annealing
• tabu search
• evolution-based diversification
• genetic algorithm
• job shop scheduling