关键词: 流水车间, 调度, 多目标优化, 调整时间, 局部搜索, 适应度分配

Abstract: In order to deal with multi-objective flow shop scheduling problems with family setup times, an optimization model was established under the group technology assumption removed. Then, a hybrid genetic algorithm combining evolutionary computation with local search was designed to solve this model. The objective function of the model was to minimize the makespan and the maximum tardiness. Two new neighborhood structures based on the problem characteristics were defined, and a two-stage search strategy was used in the local search procedure to improve efficiency of optimization. The fitness assignment based on the double rank of the individual and its density value was employed to preserve diversity of the solutions, and the elitist strategy was adopted to ensure the convergence of the solutions. The performance of this algorithm was compared to three multi-objective algorithms proposed in the literature on several test problems and a practical problem, the experimental results demonstrated the effectiveness of the scheduling model and the proposed algorithm.

Key words: flow shop, scheduling, multi-objective optimization, setup times, local search, fitness assignment