关键词:
Memetic算法
柔性作业车间调度
多模态优化
摘要:
在制造生产中,需要花费数天为企业提供一个可行的调度方案。然而,生产环境复杂,提供的调度方案可能因一些不可控因素导致不可执行。这都将使企业花费大量的时间成本去寻找另一解决方案,那么在一开始提供多个可行的调度方案显得尤为重要,企业可以从中选择最适合可变制造环境的调度方案。一次寻找多个可行方案的问题称为多解优化问题,旨在寻找全局范围内的多个较优解,但经典算法难以解决离散型的多解优化问题。本文基于Memetic算法,探究柔性作业车间调度的多解问题(Flexible Job-Shop Scheduling Multi-Solution Problem,FJSM-SP),主要研究工作如下。
首先,构建FJSM-SP数学模型。基于柔性作业车间调度对FJSM-SP进行分析、描述,建立以最小化最大完工时间为目标的FJSM-SP数学模型。分析柔性作业车间调度解的表示方法,结合甘特图提出区分多解的相似度计算公式。
其次,提出基于簇群的Memetic算法(Clustering Memetic Algorithm,CMA)。使用双层染色体编码结构对问题进行映射,并采用混合方法生成初始解。在选择算子使用的锦标赛方法中,同时考虑个体适应度和相似度来提高优秀个体被选中的概率;交叉算子采用POX交叉产生可行解;对关键路径上的关键块进行变异操作,提高变异效率。分析甘特图上的关键路径,提出公共关键路径块的局部搜索操作进行强化搜索。分析种群数量和个体数量对算法性能的影响,提出种群自融合-分解方法和三种算法评价指标。结合簇聚类和相似度来自融合种群;使用Canopy算法和K-means算法来划分种群,使个体能够利用种群信息来探索不同区域的最优解。基于Memetic算法,结合种群自融合-分解方法和局部搜索操作,提出CMA来解决FJSM-SP。
最后,对CMA性能进行研究。在标准测试算例4×5上分析算法参数(如初始种群数量、初始种群个体数量、交叉概率、变异概率和局部搜索次数等)对算法性能的影响。在25个标准测试算例上使用MATLAB进行仿真实验,并与七种算法进行比较,通过三种算法评价指标来验证CMA的有效性。将算法应用在实际采集的生产数据中来验证CMA的可行性。
研究结果表明,结合甘特图的相似度计算方法能够有效区分多解;通过种群自融合-分解方法能够探索更多邻域解。在25个标准测试算例和6个实证数据上,CMA能找到22个标准测试算例的最优解和6个实证数据的最优生产调度时间,且在多解的数量和解集重复率上都要优于其余七种算法。CMA可以有效的一次为企业提供多个调度方案,减少时间和经济成本。