基于改进NSGA-Ⅱ混合算法求解多目标柔性作业车间调度问题

Solving multi-objective flexible job shop scheduling problem based on improved NSGA-Ⅱ hybrid algorithm

针对多目标柔性作业车间调度问题(Flexible Job-Shop Scheduling Problem, FJSP),求解算法和多目标处理至关重要,在建立以最小化最大完工时间、最小化生产总能耗、最小化设备总负荷为优化目标的数学模型情况下,提出一种改进的非支配排序遗传算法(INSGA-Ⅱ)与变邻域搜索算法(VNS)求解该问题。结合问题特点设计工序与设备融合并行双链式编码方式,将个体基因分成工序和设备两部分分别编码。根据改进的NSGA-Ⅱ算法进行最优解搜索,将搜索结果作为VNS的初始解,提高初始解的质量。为提高局部搜索能力,设计4种不同的邻域结构,构建邻域结构集以产生邻域解,保证邻域解在搜索过程的可行性,同时提高求解效率。通过在经典数据集上与其它算法进行实验对比,验证了IVNSGA-Ⅱ算法在多目标生产智能优化调度中的可行性和有效性。

For the multi-objective flexible job scheduling problem(FJSP), solving algorithm and multi-objective processing are very important. With the goal of establishing the model which minimize the maximum completion time, total production energy consumption, and minimum(total equipment load), an improved non-dominated sorting genetic algorithm(INSGA-Ⅱ) and variable neighborhood search algorithm(VNS) are propose. Considering the characteristics of the problem and design process and equipment fusion parallel double-stranded coding method, the individual genes are divided into two parts to encode separately. According to the improved NSGA-Ⅱ algorithm, the optimal solution is searched, and the search result is used as the initial solution of VNS to improve the quality of the initial solution. In order to improve the local search ability, four different neighborhood structures are designed, and a neighborhood structure set is constructed to generate neighborhood solutions, which ensures the feasibility of neighborhood solutions in the search process and improved the solution efficiency. The feasibility and effectiveness of the IVNSGA-Ⅱ algorithm in multi-objective production intelligent optimization scheduling are verified by experimental comparison with other algorithms on the classical data set.