A hybrid algorithm with diversification and intensification for permutation 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.