基于混合NSGA-Ⅲ的多目标柔性作业车间调度问题研究

发布时间：2020-11-19 07:41

　　 制造业是推动国民经济发展的重要力量。随着全球性市场竞争的加剧和需求的多样化,制造企业不仅需要通过先进的生产加工技术来提高产品质量,还需要引进先进的管理技术以寻求最佳的生产方式来进一步提高企业的生产效率。采用合理且有效的生产调度策略可以最大限度发挥资源的能力以实现企业效益最大化,是提高制造企业管理水平的关键技术之一。在生产调度领域,柔性作业车间调度问题(Flexible Job-Shop Scheduling Problem,FJSP)是经典作业车间调度问题的拓展,体现了工件加工路线的柔性化,即一道工序可以在多台机器上进行加工,一台机器也可以加工多种不同类型的工序。实际生产往往需要同时优化多个目标,例如不仅需要缩短产品的完工时间以满足交货期的要求,还需要提高机器利用率以降低生产成本。因此近年来,多目标柔性作业车间调度问题(Multi-Objective FJSP,MO-FJSP)越来越受到学者的关注。本文针对MO-FJSP,首先研究该问题的相关约束和目标函数,建立了数学模型;然后利用求解多目标优化问题最为先进的算法之一—第三代非支配排序遗传算法(Reference-point Based Non-dominated Sorting Genetic Algorithm,NSGA-Ⅲ)对其进行求解,引入一种有效的邻域搜索对NSGA-Ⅲ算法进行改进,并通过多个标准实例对其有效性进行验证;最后在混合NSGA-Ⅲ的基础上,设计开发了调度原型系统,为基于元启发式算法生产调度技术的基础研究开展了积极的探索。论文的主要研究内容和成果如下:(1)给出了 MO-FJSP的相关概念和定义,对机器生产能力、工序的工艺路线和生产日历等约束条件进行梳理,确定了最小化最小完工时间、总机器负荷和机器最大负荷三个优化目标,建立了 MO-FJSP的数学模型。(2)针对传统的优化算法在求解多目标柔性作业车间调度问题时,具有容易陷入局部最优和收敛速度慢等缺陷,研究对其进行求解的混合第三代非支配排序遗传算法。该混合算法由具有全局搜索能力的NSGA-Ⅲ和具有局部搜索能力的邻域搜索算法组成。为了提高初始种群的质量,提出一种针对优化多目标的组合启发式方法进行种群初始化;为增加种群多样性,提出四种有效的变异算子;利用NSGA-Ⅲ独特的基于参考点的选择机制从种群中保留优秀的个体;采用基于关键路径的邻域搜索方法对子代种群进行进一步精炼;为了从Pareto最优解集中选取最终方案,提出了基于改进NSGA-Ⅲ归一化过程的多目标调度策略。最后通过国际通用的基准算例进行测试,验证了所提方法的有效性。(3)对车间调度涉及的机器、工件和工序三个要素的时空和属性关系进行深入分析,设计了合理的数据库结构;在混合NSGA-Ⅲ为系统核心算法的基础上,开发了调度原型系统,该系统主要包括三个模块:调度数据的输入和处理模块、关键参数和约束设置模块以及甘特图、机器负荷图和派工单组成的输出模块。该调度系统具有较快的计算速度、简洁的操作界面和一定的工程应用价值。
【学位单位】：中国工程物理研究院
【学位级别】：硕士
【学位年份】：2019
【中图分类】：TH165;TP18
【部分图文】：

１．２．１求解多目标柔性作业车间调度问题的元启发式算法??１．２．１．１遗传算法??遗传算法是一种模拟生物进化过程的元启发式算法，其流程图如图１．２所示。??初始化种群??配对选择??Ｉ??变化算子??否?＋??计算适应值??Ｉ??环境选择??是???否终＾＞＞??最优群体??Ｇ结束）??图１．２遗传算法流程图??在遗传算法中，首先要对染色体进行编码，然后采用随机或启发式的方法产生预设??数目的染色体，这些染色体组成了初始种群，初始种群进入迭代过程。在每代中，首先??需要选择种群中的个体进行配对以产生新的染色体，这个过程称之为配对选择；然后选??择种群中的某些个体来经过变化算子后产生新的子代个体，常用的变化算子包括交叉和??变异算子；接着计算子代每个个体的目标值；最后在选择种群中合适的个体进入下一轮??迭代中，即环境选择。综上所述，遗传算法有三个显著的特点［１４］：??（１）

１．２．１．３人工蜂群算法??人工蜂群算法是Ｋａｒｅｂｏｇａ等提出的，该算法受蜂群寻找食物源的过程启发ｔＷ，其??流程图如图１．４所示。??在人工蜂群算法中，蜂群归为三种类型：引领蜂、跟随蜂和侦查蜂，问题的每个解??都用相应食物源表示，整个蜂群的目标是寻找花蜜量最多的食物源，即最优解。人工蜂??群算法首先随机产生一个初始化种群，即食物源，将这些食物源随机安排给引领蜂，并??对引领蜂对应的食物源进行邻域搜索：然后计算引领蜂对应食物源的适应值，与跟随蜂??共享；最后，评定跟随蜂食物源的适应值，对其进行一次邻域搜索，计算其适应值，并??保留两者中的较优解；若某个食物源多次更新没有改进，则对应引领蜂变为侦查蜂，随??机搜索新食物源。??７??

?Ｃ结束）??图１．３粒子群算法流程图??在求解ＭＯ－ＦＪＳＰ方面：１＾１１等［３（）］考虑最大完工时间和平均流通时间两个目标，提出??一种改进粒子群算法，采用一种新的编码方式，种群的每个粒子都附带工序排序和机器??选择信息：Ｇｒｏｂｌｅｒ［３１＾ｈ对最大完工时间和最大延迟时间两个目标，在粒子群算法中融入??优先级的概念，提高了该算法的搜索性能；１＾６１〇＾等［３２］以最大完工时间、机器最大负荷??和总机器负荷为优化目标，采用一种自适应参数的粒子群算法对其进行求解；Ｓａｄｒｚａｄｅｈ??等［３３］考虑最大完工时间和平均流经过时间两个目标，利用一种分阶段的粒子群算法；仲??于江等［３４］选取最大完工时间、机器最大负荷和总机器负荷三个目标，将小生境技术融入??到粒子群算法中
【相似文献】

相关期刊论文 前10条

1 袁良照;翟华;张兰军;高广权;王玉山;;基于NSGA-Ⅱ算法的八连杆机械压力机杆系设计[J];重型机械;2017年02期

2 谢峰;;基于改进NSGA-Ⅱ算法的路网养护决策优化研究[J];中外公路;2017年03期

3 杨桂芝;王广泽;胡楠楠;赵丽华;;NSGAⅡ在供应商选择中的应用[J];哈尔滨理工大学学报;2017年05期

4 周保民;张建国;;基于粒子融合NSGA-Ⅱ的永磁无刷直流电机多目标优化[J];电子世界;2013年07期

5 魏武;邓高燕;;NSGA-Ⅱ在蛇形机器人中的优化与控制[J];计算机工程;2012年08期

6 李凯斌;卢建刚;吴燕玲;孙优贤;;基于NSGA-Ⅱ考虑性能的烧结矿配料优化[J];江南大学学报(自然科学版);2009年01期

7 顾春华;刘鑫平;罗飞;丁炜超;;基于同步更新外部归档集的NSGA-Ⅱ改进算法[J];计算机工程与应用;2018年20期

8 罗柏文;杨华科;周知进;王朝辉;;基于改进型NSGA-Ⅱ算法的深海高频变压器优化研究[J];中国海洋平台;2016年05期

9 刘洪娟;高寒冰;姜大立;甘明;;基于NSGA-Ⅱ算法的复杂供应链网络库存协同控制[J];物流技术;2015年03期

10 刘书明;李明明;王欢欢;王琦;孟凡琳;陈晋端;;基于NSGA-Ⅱ算法的给水管网多目标优化设计[J];中国给水排水;2015年05期

相关博士学位论文 前10条

1 王杜娟;生产调度中应对干扰的重调度模型和算法研究[D];大连理工大学;2015年

2 申瑞珉;高维多目标进化算法及其软件平台研究[D];湘潭大学;2015年

3 袁源;基于分解的多目标进化算法及其应用[D];清华大学;2015年

4 戴春妮;高光谱显微图像的特征提取与分类方法及其应用研究[D];华东师范大学;2009年

5 Okafor Ekene Gabriel;复杂系统失效率评估与多目标优化方法研究[D];南京航空航天大学;2012年

6 张福坤;油田中后期开发优化与决策研究[D];中国地质大学;2014年

7 柯鹏;基于多目标进化算法的车辆路径问题的研究[D];武汉大学;2013年

8 常辉;卫星星座协同优化设计研究[D];华中科技大学;2012年

9 何善君;自动小车存取系统的建模及其若干关键技术研究[D];厦门大学;2008年

10 刘鎏;多目标优化进化算法及应用研究[D];天津大学;2010年

相关硕士学位论文 前10条

1 阮礽恩;基于混合NSGA-Ⅲ的多目标柔性作业车间调度问题研究[D];中国工程物理研究院;2019年

2 魏冰;NSGA-Ⅱ算法的改进及在机组组合优化中的应用[D];华北电力大学;2019年

3 谭智雄;基于NSGA-Ⅱ算法及机器学习的压水堆组件装载方案优化研究[D];华南理工大学;2019年

4 汪文文;基于改进NSGA-Ⅱ算法的应急配送中心选址模型研究[D];武汉理工大学;2018年

5 曹海涛;基于改进NSGA-Ⅱ的多目标柔性作业车间调度问题研究[D];浙江工业大学;2019年

6 张艺;基于改进NSGA-Ⅱ算法的含分布式电源的配电网无功优化[D];兰州理工大学;2019年

7 王祥;基于改进NSGA-Ⅱ算法的应急物资模块化调度问题建模与求解[D];合肥工业大学;2018年

8 杨世君;基于混合NSGA2的混流装配线设施规划与布局应用研究[D];苏州大学;2018年

9 洪健;基于NSGA-Ⅱ的精冲工艺参数优化的仿真研究[D];南华大学;2018年

10 李帅;基于NSGA-Ⅱ的蒸汽动力系统经济性与环境影响优化[D];大连理工大学;2018年

本文编号：2889908