A Memetic Algorithm for the Multi-Objective Flexible Job Shop Scheduling Problem

摘要

In this paper, a new memetic algorithm (MA) is proposed for the muti-objective flexible job shop scheduling problem (MO-FJSP) with the objectives to minimize the makespan, total workload and critical workload. By using well-designed chromosome encoding/decoding scheme and genetic operators, the non-dominated sorting genetic algorithm II (NSGA-II) is first adapted for the MO-FJSP. Then the MA is developed by incorporating a novel local search algorithm into the adapted NSGA-II, where several mechanisms to balance the genetic search and local search are employed. In the proposed local search, a hierarchical strategy is adopted to handle the three objectives, which mainly considers the minimization of makespan, while the concern of the other two objectives is reflected in the order of trying all the possible actions that could generate the acceptable neighbor. Experimental results on well-known benchmark instances show that the proposed MA outperforms significantly two off-the-shelf multi-objective evolutionary algorithms and four state-of-the-art algorithms specially proposed for the MO-FJSP.

出版物
Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation
袁源
博士

2010年进组,2015年获得博士学位。

徐华
徐华
长聘副教授, Expert Systems with Application 副主编,博士生导师

相关