基于约束模型的多目标柔性作业车间调度问题求解

罗 雄,钱 谦,伏云发,冯 勇

(1.昆明理工大学信息工程与自动化学院,云南 昆明 650500;2.昆明理工大学云南省计算机技术应用重点实验室,云南 昆明 650500)

0 引言

柔性作业车间调度问题( flexible job-shop scheduling problem,FJSP)是作业车间调度问题(jobshop scheduling problem,JSP)的扩展,是计算复杂度更高的NP 难问题。 多目标柔性作业车间调度问题

(multi-objective flexible job-shop scheduling problem,MOFJSP)是FJSP 的子问题。 由于该问题更贴近实际的生产活动,对其进行研究可以更好地为企业经营者决策提供支持。 在实际生产活动中,MOFJSP 各个优化目标的相互冲突,导致MOFJSP 与单目标的FJSP、JSP 有着本质的区别,即一般情况下,多目标优化的最优解不是唯一的[1]。

在现阶段使用遗传算法求解MOFJSP 的研究中,朱伟[2]基于基础模型,考虑了工件移动时间的约束,建立了包括最小化最大完工时间、最小化总加工成本在内的多目标组合优化模型,并改进遗传算法中的变异算子自适应变异规则,求解MOFJSP。 王雷[3]等建立以完工时间、机器能耗和工人操作机器的舒适度为优化目标的优化模型,并使用改进的遗传算法进行求解。Fattahi[4]考虑了机器与工件的动态插入调度,建立了多目标优化的动态调度模型,并使用遗传算法进行求解。 张国辉[5]等构建了低碳多目标调度模型,使用改进的遗传算法对有低碳需求的车间进行求解。 以上研究均使用加权求和法将多个优化目标进行加权求和,从而转化为单目标进行求解。 虽然该方法易操作、易实现,但每次只能获得一个解,且权重设置的不同会导致输出结果的严重差异。 因此,如何保证产生多个调度方案供选以及尽可能地靠近最优解,是使用遗传算法求解MOFJSP 所需解决的问题之一。……