Heuristics and metaheuristics for the bi-criterion optimization of the flexible flow shop scheduling problem with two stages

摘要

We present in this paper a bi-criterion minimization model of the problem solving of two-stage flexible flow scheduling with identical parallel machines and the sequence dependent setup time. The goal is the minimization of the makespan and the weighted average completion time of each job. The objective function is a combination of two criteria with a weighting coefficient for each criterion allowing flexibility in decision-making. We propose a set of heuristics and two metaheuristics, in this case the greedy randomized adaptive search procedure and the local search iterative algorithm to minimize the bi-objective function. A numerical simulation study is conducted on a set of instances generated randomly with n jobs and m machines per stage. We find that the iterative local search algorithm gives good results in terms of quality and convergence time to the optimal solution.