A Hybrid Discrete Harmony Search Algorithm for blocking flow shop Scheduling

This paper presents a hybrid discrete harmony search (DUS) algorithm for solving the blocking flow shop scheduling problem with the objective to minimize makespan. The proposed hybrid DUS algorithm utilizes discrete job permutations to represent harmonies and applies a job-permutation-based improvisation scheme to generate new harmonies. An initialization scheme based on a variant of the Minimum Blocking Tardiness (MBT) heuristic is presented to construct the initial harmony memory with a certain level of quality and diversity. The DUS algorithm is employed to evolve harmony vectors in the harmony memory to perform exploration, whereas a local search algorithm based on the insert neighborhood is embedded to enhance the local exploitation ability. Computational simulations and comparisons demonstrate that the proposed algorithm (DUS) is effective and efficient for the blocking flow shop scheduling problems with makes pan criterion.