A discrete group search optimizer for blocking flow shop multi-objective scheduling

Abstract

This article presents a multi-objective discrete group search optimizer for blocking flow shop multi-objective scheduling problem. The algorithm is designed to search the Pareto-optimal solutions minimizing the makespan and total flow time for the flow shop scheduling with blocking constraint. In the proposed algorithm, a diversified initial population is constructed based on the Nawaz–Enscore–Ham heuristic and its variants. Unlike the original group search optimizer in which continuous solution representation is used, the proposed algorithm employs discrete job permutation representation to adapt to the considered scheduling problem. Accordingly, operations of producer, scrounger, and ranger are newly designed. An insertion-based Pareto local search is put forward in producer procedure, a crossover operation is introduced in scrounger procedure, and a local search based on the insert neighborhood is designed in ranger procedure. A bunch of computational experiments and results show that the proposed algorithm is superior to two existing powerful meta-heuristics in terms of both inverted generational distance and set coverage.