关键词:
柔性作业车间调度
多目标优化
NSGA-Ⅱ-AEF
NSGA-Ⅲ-AEFP
摘要:
面对竞争日趋激烈的智能制造行业,为了满足顾客多样化的要求,企业对加工的产品质量提出了更高的要求,而且企业需要生产多样化的产品,这导致产品型号增多。客户订购的产品迫切希望缩短交货日期,但企业还需要考虑生产过程中多种不同设备的使用,设备不能超负荷工作以及能耗费用等因素。这些因素很大程度受到生产调度的影响,因此调度系统必须具备更高的灵活性。制定科学高效的生产调度方案迫在眉睫,以满足现今企业亟需的小批量生产、短周期交货、高质量定制化生产的要求。
在这种背景下,智能优化算法对多目标柔性作业车间调度问题(Multi-objective Flexible Job-shop Scheduling Problem,MOFJSP)的求解具有重要的意义。MOFJSP涉及到诸多复杂的因素,如不同产品型号的生产要求、设备的可用性、工序间的相关性等。传统的调度方法往往难以有效解决上述问题,而智能算法则能够通过仿真、优化以及学习等技术,在复杂生产环境下进行智能化调度,降低企业生产费用以及避免机器超负荷工作。
本文对MOFJSP展开研究,主要成果如下:
(1)分析MOFJSP的基本概念,MOFJSP涉及到工件、工序和机器之间的关系优化。工件是指在生产过程中需要加工的物品,而工序则是完成一个工件所需要的步骤或操作,机器则是用来执行这些工序的设备。这三者之间的关系是非常紧密,在考虑到这些复杂的关系的基础上,为了建立MOFJSP的数学模型,需要做出必要假设来量化和优化调度方案。这个模型可以帮助我们更好地理解和优化生产调度过程,以实现多个目标的平衡。
(2)为了求解MOFJSP,在传统非支配排序遗传(Non-dominated Sorting Genetic AlgorithmsⅡ,NSGA-Ⅱ)算法基础上进行改进,设计了一种自适应变异策略,接着对目标函数进行修正和设计了一种基于隶属度函数的模糊决策的手段获取最佳妥协解,形成了NSGA-Ⅱ-AEF算法。自适应变异策略通过计算两个杂交个体染色体的亲缘关系,来确定杂交染色体的密切程度和个体的变异率。抗支配解在某些目标上接近最优,但在其他目标上却很差,由于它们具有部分非常好的目标值,因此它们几乎不会被其他解主导。为了尽可能的消除这些抗支配解,需要对目标函数进行修正。由于NSGA-Ⅱ-AEF算法采用了一种基于拥挤距离的环境选择机制,但这种方法在多维空间中可能无法准确反映解的分布情况,导致无法为种群提供足够的选择压力,而第三代非支配排序遗传算法(Non-dominated Sorting Genetic AlgorithmsⅢ,NSGA-Ⅲ)算法则采用了一种基于参考点的环境选择机制,能够有效克服这种困难。在求解三个及三个以上目标的FJSP时,由于其优化目标数量较多,导致在NSGA-Ⅲ算法中,种群中非优势解的数量呈指数增长,进而影响了环境选择的计算效率。设计一种基于PBI距离的自适应淘汰机制来保存个体,有效提高了NSGA-Ⅲ在环境选择时的计算效率,加上改进NSGA-Ⅱ算法的创新点,形成了NSGA-Ⅲ-AEFP算法。最后,利用ZDT、DTLZ和WTG系列测试函数验证了NSGA-Ⅱ-AEF和NSGA-Ⅲ-AEFP算法求解MOFJSP能力。仿真结果表明,与NSGAIIARSBX、NSGA-Ⅱ等先进优化算法相比,所提出的两种改进算法均能获得更好的优化搜索结果,但NSGA-Ⅲ-AEFP求得解的收敛性和分布性优于NSGA-Ⅱ-AEF。
(3)最后利用NSGA-Ⅱ-AEF和NSGA-Ⅲ-AEFP两种改进算法来解决MOFJSP,首先根据MOFJSP的数学模型和约束条件,设计了具体的染色体编码方案,提出了贪婪解码算法来进行解码操作,并利用概率选择的方式来改进的种群初始化策略,分别设计对工序和机器的交叉、变异方式。在国际通用的标准算例Kacem01、Kacem03、MK01、MK02来进行算法性能分析,通过与TSNSGAⅡ、g NSGAⅡ、NSGA-Ⅲ以及NSGA-Ⅱ-AEF算法的对比来证明NSGA-Ⅲ-AEFP算法在处理MOFJSP时的高效性,同时FJSP解的分布性更好,能够取得更多的方案给决策者更多的选择。
将NSGA-Ⅲ-AEFP算法用于处理一个钢水炼钢工艺的生产案例,NSGA-Ⅲ-AEFP对于钢水炼钢工艺过程(工件个数为12,机器个数为10)的调度解个数为16个,使用TSNSGAⅡ、g NSGAⅡ和NSGA-Ⅲ算法解决MOFJSP问题,对应的MOFJSP解决方案与NSGA-Ⅱ-AEF和NSGA-Ⅲ-AEFP进行对比,NSGA-Ⅲ-AEFP算法的最大完工时间最小,机器最大负荷最小,NSGA-Ⅲ-AEFP比TSNSGAⅡ算法增加了7个Pareto解,NSGA-Ⅲ-AEFP比NSGA-Ⅱ-AEF算法增加了5个Pareto解,说明在处理