基于INSGA-Ⅱ高维目标柔性作业车间调度的优化

Many-objective flexible job shop scheduling optimization based on INSGA-Ⅱ

高维目标柔性作业车间调度问题(many-objective flexible job shop scheduling problem, MaOFJSP)是指在实际生产中根据企业不同部门的要求,对车间生产寄予不同的期望,使各个部门利益最大化的调度决策。针对完工时间、拖期时长、机器负荷、能耗4个优化目标,提出了改进非支配解遗传算法(improved non-dominated sorting genetic algorithm, INSGA-Ⅱ)来求解MaOFJSP,同时对算法的编码解码、Pareto排序、选择策略、交叉变异操作进行了研究。采用工序排序和机器选择的双层个体编码方式,在精英选择过程中计算个体的斜率,斜率小的进入到父代,使得优秀个体得以保存;在变异环节中基于关键工序块邻域结构,采用插入法让工序小的工件优先加工,使得最大完工时间明显变小。通过该算法对不同算例进行的Matlab模拟仿真,验证了该模型的可行性和算法的优越性。

An improved non-dominated sorting genetic algorithm(INSGA-Ⅱ) is proposed in this paper in order to solve many-objective flexible job shop scheduling problem(MaOFJSP), which refers to the scheduling decision that maximizes the benefits of each department with placing different expectations on the workshop production according to the requirements of different departments of the enterprise in actual production. Besides, this paper constructs a many-objective flexible job shop scheduling model to research encoding and decoding, Pareto sorting, selection strategy, and cross mutation operation of the INSGA-Ⅱ, where completion time, tardiness, machine load, and energy consumption are all concerned. The algorithm introduces the double-layer individual coding method of machine selection and process sorting strategy. In the process of elite selection, the individuals with the small slope are selected to join the parent for preserving outstanding individuals. In the process of mutation, in consideration of the neighborhood structure of the key process block, the insertion method is adopted to give priority to the processing of workpieces with small process number, which makes the maximum completion time significantly shorter. Finally, the results of Matlab simulation based on different examples using INSGA-Ⅱ algorithm show that the proposed algorithm has good convergence, and it can solve many-objective flexible job-shop scheduling problem effectively.