一种基于U-NSGA-III算法的多目标作业车间节能优化方法

摘要

本发明公开了一种基于U‑NSGA‑III算法的多目标作业车间节能优化方法，该方法包括步骤：1)设定初始迭代次数和最大迭代次数；2)生成初始种群，作为父代；3)在父代种群中选择优秀染色体进行染色体交叉和变异处理；4)迭代次数+1；5)将父代染色体与交叉和变异处理生成的子代染色体种群合并；6)排序合并后的染色体生成新的解集，若步骤6)能确定解集则执行步骤8)，若步骤6)不能确定解集则执行步骤7)；7)计算得到解集中未在步骤6)中确定的染色体，最终确定解集；8)判断循环条件，满足循环条件则跳出算法循环输出结果；不满足循环条件则继续循环；9)输出最优解集。本发明可实现显著的节能效果，其中非处理能耗最多可节省69％。

说明书

技术领域

本发明属于车间调度和深度学习领域，涉及一种基于U-NSGA-III算法的多目标作业车间节能优化方法。

背景技术

制造业的发展水平直接反映了一个国家的生产力水平，也是衡量国家综合国力的重要指标。但近年来，随着经济和社会的发展，人类面临的能源问题日益凸显。当前环境恶化和能源短缺问题严重制约中国制造业的发展，必须依靠科学技术降低能源消耗，提高能源利用率。为了增强我国综合国力和国际竞争力，在《中国制造2025》的指导下，明确以“创新驱动、质量为先、绿色发展、结构优化、人才为本”的战略方针并把可持续发展作为制造强国的重要着力点，走生态文明、环境友好的发展道路。同时全面推行绿色制造，努力构建高效、清洁、低碳的绿色制造体系。发达国家也纷纷提出绿色发展战略，美国提出的《先进制造业的国家战略计划》，欧盟第7框架计划设立的“未来工厂”重大项目，德国的“工业4.0”，日本的《绿色革命和社会变革》等法案或政策中均有提到制造业节能环保的生产理念。在国家政策的大力支持和推动下，制造企业应积极面对“制造全球化”发展的挑战，大力整改创新，加快产业转型升级，实现制造过程的绿色化和智能化。因此，如何提高制造业能源与资源利用效率，降低能源消耗，实现制造业的绿色发展成为产业界和学术界研究的热点。

车间调度指的是在车间生产中为一批待处理的工件安排加工设备等生产资源，通过调整待加工工件的加工顺序、车间加工设备的合理配置等，达到车间生产特定的指标，如完工时间最小、成本最低、能耗最低等，实现车间资源的合理利用和生产计划的最佳安排。车间生产在制造业中广泛存在且占有重要地位，针对车间开展调度与优化研究具有重要的工程应用意义。通过生产调度优化获得的最优生产计划来指导车间生产，能够为企业缩短生产时间，提高的资源利用率，促进车间节能减排。因此，节能优化调度是当前制造业领域提高业务效率，提高能源效率和增强竞争力的关键技术和研究重点。本发明旨在面向流水车间、混合流水车间、作业车间进行调度优化问题研究，通过资源合理配置，在提高生产效率的同时减少车间能耗，促进制造业节能减排及绿色制造的实现。

当前大多数与能源和迟滞相关的车间调度研究都没有考虑早期成本。作业车间调度的常用目标之一是提前和拖延。在给定的工作计划中，如果任何工作在到期日之前完成，将产生不良影响，例如产品过多导致仓库空间不足，存货搬运成本，仓储和保险成本以及产品变质。在实际生产中，尤其是在即时制造环境中，早期性和延误性是非常重要的标准。第二个常用的优化目标是工期，这是在车间环境中另一个非常适用的标准。但是，到目前为止，还没有关于在车间调度中同时优化三个目标(制造时间，能耗，迟到性和早期性)的报告。根据以前的研究，与开发更节能的机器相比，在系统级存在更大的节能余量，在该级别，车间调度优化和机床操作策略可以用作节能方法。这尤其适用于大规模生产环境，以提高效率和能源利用率，从而提高制造企业的盈利能力。

发明内容

本发明要解决的技术问题是：提供一种基于U-NSGA-III算法的多目标作业车间节能优化方法，旨在解决车间调度中无法同时优化制造时间、能耗、迟到性和早期性三个目标的问题，并有效解决车间作业调度问题的多目标调度方法，最终减少总能耗和延误/早期成本。

本发明采取的技术方案为：一种基于U-NSGA-III算法的多目标作业车间节能优化方法，该方法包括以下步骤：

在从P

(1)初始迭代次数为0，设定最大迭代次数；

(2)基于操作表示的作业计划编码方式，使用结合MME算法和随机生成的方式生成初始种群，作为父代P

(3)基于小生境比赛选择算子，在父代种群中选择优秀染色体进行染色体交叉和变异处理，生成染色体数量为N的子代种群Q

(4)迭代次数+1；

(5)将生成的数量为N的父代染色体P

(6)使用非支配排序算法计算合并后的2N条染色体，利用排序结果生成新的解集S

(7)利用最短垂直距离计算得到解集S

(8)判断循环条件，满足循环条件则跳出算法循环输出结果；不满足循环条件则继续循环；

(9)输出Pareto最优解集。

步骤(2)中MME算法步骤如下：(1)分别计算n个工件加工所有工序所需要的总加工时间，将总加工时间最少的工件放在工件排序的第一个位置，将加工时间第二少的工件放在工件排序的倒数第一个位置，并设置i＝2，i是工件的序号，i∈[1,n]；

(2)其余n-2个工件按照公式(1)的标签函数的函数值大小升序排列，将取得值为A

式(1)中，r为[0,1]之间的随机数，t

(3)使i＝i+1，如果i

(4)交换π0中的前两个工件，加入加工序列π1中；分别计算交换顺序前后的最大完工时间，取时间最少的序列，并将这两个工件的顺序固定，记为π1，设置k＝2；

(5)随机选取未加工序列中的一个工件加入到π1的所有可能位置，计算该工件加入后的完工时间，选择能使完工时间最小的位置；令k＝k+1；从π0中取出第k个工件，插入π1中所有可能的位置，找到能够使完工时间最小的位置，将工件固定在该位置，并将排序固定下来，重复步骤(5)直至k＝n；

(6)每确定一个工件位置后将其从未加工序列中删除，继续执行步骤 (5)，直至所有工件位置全部确定，形成新的染色体；

重复执行上述(1)～(6)步操作p次，生成规模为p的初始种群。

步骤(3)中在小生境比赛选择算子环境下进行交叉和变异，处理生成第一代数量为N的子代种群Q

步骤(3)中小生境比赛选择算子的选择步骤：其中两个可行的父解P1 和p2被比较以选择获胜者ps，如果其中至少有一个不可行，则使用NSGA-III 算法进行选择，通过使用亲本群体Pt的两个连续群体成员来选择N/2亲本，重复该操作N/2次，该过程通过改组群体Pt以获得另一组N/2亲本来重复一次，在基于小生境的选择(Pt)过程中，这两个选择的亲本结合形成大小为N的完全交配池P’t，然后，交配池P’t可以通过使用常用的重组和突变算子来创建后代群体Q

NSGA-III算法采用边界交叉构造权重的方法产生确定性的参考点，对于等分数为P的M个目标获得H个参考点，H的大小通过公式

步骤(3)中的染色体交叉处理方法为：如果在0和1之间生成的均匀分布的随机数小于交叉概率Pc，则对随机选择的父本应用交叉操作，选择两点交叉运算，操作步骤如下：

(1)随机选择两个交叉点，在两个交叉点之间交换基因；

(2)通过删除多余的基因并添加数量不足的基因来检查和修复染色体。

例如，两个亲本染色体P1和P2的遗传代码是“213112323”和“131233122”。随机生成两个交叉位置3和6，并在相交处交换线段，以获得“211233323”和“133112122”。通过修复出现次数不等于3的基因位置，可以获得两个可行的基因序列“211233123”和“133112322”。

步骤(3)中的变异操作处理方法为：生成一组矩阵，该矩阵由介于0和 1之间的均匀分布的数字组成，并且维数与父本相同，当随机数矩阵中的某个值小于突变概率时，则需要对父群体矩阵中的相应位置进行变异，变异步骤如下：

(1)将基因从该位置移至该染色体的最后一个位置；

(2)将该位置后面的所有基因向前移动一个位置。

步骤(6)中使用非支配排序算法计算合并后的2N条染色体，利用排序结果将R

步骤(8)中利用迭代次数与最大迭代次数的关系实现算法循环，若迭代次数小于最大迭代次数则转步骤(3)，此时将生成的解集S

步骤(9)中输出的Pareto最优解集包括三个优化目标：非处理能耗NEC，制造期Cmax和总加权延误与提前期TWET的数值结果组成，即算法的最终输出结果。

本发明提出了一种用于节能作业调度的将调度与机器状态切换相结合的多目标遗传算法，该算法包括三个目标：非处理能耗(NEC)，制造期(Cmax) 和总加权延误与提前期(TWET)。

本发明的有益效果：与现有技术相比，本发明使用多目标遗传算法 U-NSGA-III，使用MME算法和随机生成方法对种群进行高质量初始化。与其他两种算法(NSGA-II和NSGA-III)相比，在扩展的TAILLARD作业车间基准中测试了U-NSGA-III的性能。结果表明，U-NSGA-III可以获得针对这三个目标的大多数最佳值。本发明面向能源效率的多目标作业调度算法可实现显著的节能效果，其中非处理能耗最多可节省69％。本发明的方法也可以轻松扩展，以解决其他种类的制造车间调度问题以节省能源，例如流水车间调度和灵活的车间调度。

附图说明

图1为本发明的U-NSGA-III算法流程图；

图2为基于操作表示的作业计划编码方式示例图；

图3为NSGA-III算法产生确定性的参考点所采用的边界交叉构造权重方法图。

具体实施方式

下面结合附图及具体的实施例对本发明进行进一步介绍。

实施例1：U-NSGA-III首先定义一组参考点，参考点个数为N。然后随机生成含有N个个体的初始种群，使其个体数目与参考点个数相同，其中N是种群大小。接下来，算法进行迭代直至终止条件满足。

一种基于U-NSGA-III方法的多目标作业车间节能优化算法，如图1所示，具体步骤为：

在从P

1.初始迭代次数为0，设定最大迭代次数；目的在于确定循环次数即算法结束条件；

2.基于操作表示的作业计划编码方式，使用结合MME算法和随机生成的方式生成初始种群，作为父代P

3.基于小生境比赛选择算子，在父代种群中选择优秀染色体进行染色体交叉和变异处理，生成染色体数量为N的子代种群Q

4.迭代次数+1；目的在于使算法循环向结束条件逼近；

5.将生成的数量为N的父代染色体P

6.使用非支配排序算法计算合并后的2N条染色体，利用排序结果生成新的解集S

7.利用最短垂直距离计算得到解集S

8.判断循环条件，满足循环条件则跳出算法循环输出结果；不满足循环条件则继续循环；目的在于判断是否达到目标解，若不是未达到则继续算法循环；

9.输出Pareto最优解集。

步骤1中的迭代次数初始为0，是算法的循环计数器。最大迭代次数是算法开始和停止的评判标准，当迭代次数小于最大迭代次数时算法继续循环以寻找更优的解；当迭代次数等于最大迭代次数时算法停止循环，此时的解集即算法最终要寻找的Pareto最优解集。

步骤2中生成初始种群P

步骤2中生成初始种群Pt，采用的种群生成方法是结合MME算法和随机生成的方式。MME算法基本流程如下：

(1)分别计算n个工件加工所有工序所需要的总加工时间，将总加工时间最少的工件放在工件排序的第一个位置，将加工时间第二少的工件放在工件排序的倒数第一个位置，并设置i＝2，i是工件的序号，i∈[1,n]；

(2)其余n-2个工件按照公式(1)的标签函数的函数值大小升序排列，将取得值为A

式(1)中，r为[0,1]之间的随机数。t

(3)使i＝i+1。如果i

(4)交换π0中的前两个工件，加入加工序列π1中。分别计算交换顺序前后的最大完工时间，取时间最少的序列，并将这两个工件的顺序固定，记为π1，设置k＝2；

(5)随机选取未加工序列中的一个工件加入到π1的所有可能位置，计算该工件加入后的完工时间，选择能使完工时间最小的位置。令k＝k+1。从π 0中取出第k个工件，插入π1中所有可能的位置，找到可以使完工时间最小的位置，将工件固定在该位置，并将排序固定下来，重复步骤(5)直至k＝n；

(6)每确定一个工件位置后将其从未加工序列中删除，继续执行步骤 (5)，直至所有工件位置全部确定，形成新的染色体；

重复执行上述(1)～(6)步操作p次，生成规模为p的初始种群。

步骤3中在小生境选择算子环境下进行交叉和变异，处理生成第一代数量为N的子代种群Q

如下所示小生境比赛选择过程伪代码，以伪代码的形式给出了小生境锦标赛选择过程，其中两个可行的父解(P1和p2)被比较以选择获胜者(ps)。如果其中至少有一个不可行，则使用NSGA-III进行选择。通过使用亲本群体Pt 的两个连续群体成员来选择N/2亲本，可以系统地重复该操作N/2次。该过程可以通过改组群体Pt以获得另一组N/2亲本来重复一次。在基于小生境的选择(Pt)过程中，这两个选择的亲本可以结合形成大小为N的完全交配池P’t。然后，交配池P’t可以通过使用常用的重组和突变算子来创建后代群体Qt。

其中，NSGA-III是使用基于参考点的非支配排序方法的进化多目标优化算法，采用基于参考点的选择操作来保证非支配解的多样性，提出了一种基于参考点和欧氏距离的选择方法。首先对个体的目标函数值和参考点标准化，让所有个体和参考点位于同一个超平面上。

如图3所示。NSGA-III算法采用边界交叉构造权重的方法产生确定性的参考点，对于等分数为P的M个目标可以获得H个参考点，H的大小可通过公式

步骤3中的交叉操作是遗传算法中产生新个体的主要方法之一。如果在0 和1之间生成的均匀分布的随机数小于交叉概率(Pc)，则可以对随机选择的父本应用交叉操作。在这项研究中，选择两点交叉运算。操作步骤如下：

(1)随机选择两个交叉点，在两个交叉点之间交换基因；

(2)通过删除多余的基因并添加数量不足的基因来检查和修复染色体。

例如，两个亲本染色体P1和P2的遗传代码是“213112323”和“131233122”。随机生成两个交叉位置3和6，并在相交处交换线段，以获得“211233323”和“133112122”。通过修复出现次数不等于3的基因位置，可以获得两个可行的基因序列“211233123”和“133112322”。

步骤3中的变异操作具体操作是：生成一组矩阵，该矩阵由介于0和1之间的均匀分布的数字组成，并且维数与父本相同。当随机数矩阵中的某个值小于突变概率时，则需要对父群体矩阵中的相应位置进行变异。变异步骤如下：

(1)将基因从该位置移至该染色体的最后一个位置；

(2)将该位置后面的所有基因向前移动一个位置。

步骤4中在成功生成子代Q

步骤5中，将生成的数量为N的父代染色体与数量为N的子代染色体种群合并为数量为2N的新种群。

步骤6中，使用非支配排序算法计算合并后的2N条染色体，利用排序结果将R

步骤7中，标准化目标函数，关联S

步骤8中，利用迭代次数与最大迭代次数的关系实现算法循环。若迭代次数小于最大迭代次数则转步骤3，此时将生成的解集S

步骤9中，输出的Pareto最优解集由三个优化目标：非处理能耗(NEC)，制造期(Cmax)和总加权延误与提前期(TWET)的数值结果组成，即算法的最终输出结果。

为了评估算法的性能，考虑了三个不同的比较指标，包括分散指标，平均理想距离和平均归一化目标函数，这些性能标准如下所述。

(1)多样性指标(DM)：由公式(2)计算的DM用于评估每种算法的解集的分布。较高的DM值表示更好的算法。

其中fj是第jth个目标函数的值，m是函数的数量，在算法中值为3.

(2)平均理想距离(MID)：MID是评估帕累托解(f

其中f

(3)平均标准化目标函数(MNOF)：算法的MNOF值计算如下：

其中A是一组优化算法,

本发明使用多目标遗传算法U-NSGA-III，使用MME算法和随机生成方法对种群进行高质量初始化。与其他两种算法(NSGA-II和NSGA-III)相比，在扩展的TAILLARD作业车间基准中测试了U-NSGA-III的性能。结果表明， U-NSGA-III可以获得针对这三个目标的大多数最佳值。此外，分别从生成的非支配进度表(DM)中的边界扩展，帕累托解决方案之间的紧密度，理想点 (MID)的角度，评估通过U-NSGA-III获得的帕累托解决方案的质量，以及通过比较指标得出的可靠性(MNOF)。此外，通过进行节能策略的双目标实验和比较实验，说明了同时优化三个目标的必要性和节能策略的效果。同时，这也是优化三个目标(包括能效目标)的首次尝试。结果表明，本发明面向能源效率的多目标作业调度算法可实现显著的节能效果，其中非处理能耗最多可节省69％。本发明的方法也可以轻松扩展，以解决其他种类的制造车间调度问题以节省能源，例如流水车间调度和灵活的车间调度。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本发明的保护范围之内，因此，本发明的保护范围应以所述权利要求的保护范围为准。