Multi-objective scheduling in hybrid flow shop: Evolutionary algorithms using multi-decoding framework

Hybrid flow shops are common manufacturing environments applied in many industrial fields. This paper tackles the scheduling problem in hybrid flow shop with unrelated machines, machine eligibility and sequence-dependent setup times (SDST) to minimize the bi-criteria of total tardiness and total setup time. Evolutionary algorithms (EAs) are adopted to solve the problem. Firstly, four efficient decoding algorithms using different machine selection rules are developed for constructing a schedule from a job permutation. These decoding algorithms are able to map the job permutation space to distinct regions in the objective space. Then, we propose a multi-decoding framework (MDF) for taking advantage of multiple decoding algorithms along one evolution path. The hybridization of MDF and EAs leads to a hyper-heuristic approach. The proposed MDF is coupled with a genetic algorithm to solve the problem in “a priori” approach, that is, to optimize a convex combination of the objectives given user preference information. The framework is also embedded to a multi-objective genetic algorithm, known as NSGA-II, to solve the problem in “a posteriori” approach, which aims at approximating the Pareto-optimal set for the user to make posterior decisions. The efficiency of the proposed methods is validated by numerical results. More specifically, when “a priori” approach is used, the proposed MDF helps EAs adjusting the adopted decoding scheme and generating solution aligned to the user preference; when “a posteriori” approach is applied, the MDF extends the search space and improves the solution quality.