A Hybrid Algorithm with Diversification and Intensification for Permutation Flow Shop Scheduling

N. Azizi, S. Zolfaghari, and M. Liang (Canada)


Evolutionbased diversification, Memory, Simulated annealing, Genetic algorithm, Tabu search, Flow shop scheduling.


This study presents a metaheuristic (SAMED) that integrates several ingredients including a simulated annealing module, three types of memory, an evolutionary operator, and a blockage removal feature in a generic framework. The SA component of the SAMED utilizes two short-term memories to intensify the search around good solutions. While the first memory is a tabu list, the second one is a seed memory list that keeps track of good solutions visited during the last iteration. Under certain condition, a long-term memory is setup by adding the best solution in the seed memory to a population list. Once the entire population is assembled, individuals are combined via an evolutionary operator to generate a new population from which an offspring might be selected as an initial solution for the subsequent iteration. The blockage removal feature is used to solve possible deadlock situations that may occur during the search procedure. The performance of the SAMED is evaluated using the well known flow shop scheduling benchmark problems of Taillard. The computational results clearly show the efficiency of the SAMED algorithm.

Important Links:

Go Back