一种多目标的能源供应与作业柔性排程方法

摘要

本发明公开了一种多目标的能源供应与作业柔性排程方法，包括：(1)确定柔性排程的能源供应优化指标与能源供应约束，构建多目标能源供应优化模型；所述的多目标能源供应优化模型的目标函数包括最大完工时间最小的目标函数、能耗最大负荷最小的目标函数以及总能耗负荷最小的目标函数；(2)采用改进的遗传算法求解所述的多目标能源供应优化模型，使得各目标函数均达到最小值，获得最优的能源供应与作业柔性排程；所述的改进的遗传算法采用自适应的交叉和变异概率，采用基于NSGA‑Ⅱ的选择操作。本发明以节能增效为优化目标，构建能源优化指标，应用改进的遗传算法，辅助调度人员快速生成排产计划，进而生成能源供应计划。

说明书

技术领域

本发明涉及车间生产排程技术领域，尤其涉及一种多目标的能源供应与作业柔性排程方法。

背景技术

在车间生产排程方面，已有六十多年的研究历史，在早期就有一些解析优化、动态规划、启发式算法等被提出来。随着计算机科学、软硬件技术的发展，一些多学科交叉的复杂算法如遗传算法、人工神经网络、蚁群算法等智能方法逐渐得到了应用，在复杂情况下的作业排程方面也积累了丰富的研究成果。

遗传算法通过模拟自然界中生物的生存竞争过程，利用选择、交叉、变异等算子，能够对复杂工程问题进行全局寻优。例如，公开号为CN111208796A的中国专利文献公开了一种基于聚类小生境遗传算法的车间生产作业排程方法、公开号为CN110069880A公开了一种基于仿真的多目标设备布局和生产排程协调优化方法均将遗传算法应用于情况复杂的作业排程中。但传统的遗传算法的局部搜索能力受到限制，在搜索过程中容易陷入局部最优解。

随着经济全球化的不断深入和市场竞争的加剧，当下企业通常实施多品种、小批量的柔性生产方式，以适应复杂多变的竞争环境，这就要求企业在生产层面采取柔性而稳定的组织方式。而大量的生产活动对能源供应有比较高的要求，例如配电、空调温湿度、空压、蒸汽等，需要实现分钟级的实时动态平衡，在保证能源供应稳定的同时，能源浪费最小。要完成这样的生产要求，不但在车间、工序上要进行排程优化，能源供应上也需要进行排程优化，并且需要具备处理某些突发事件(如设备损坏、紧急订单插入等)的能力。

部分作业排程，指的是某一作业只能在部分设备上进行，这更符合一般企业的生产实际，但约束更多，在求解时更为复杂。在能源供应中，往往要求达到多个目标、要能够适应紧急情况，与部分作业排程相似，而多目标、动态、部分柔性作业排程问题仍旧难以找到好的解决方案。

发明内容

针对当前企业在生产排程时未考虑动力能源消耗等问题，本发明提供了一种多目标的能源供应与作业柔性排程方法，以节能增效为优化目标，构建柔性排程优化指标、特别是能源优化指标，应用改进的遗传算法，辅助调度人员快速生成排产计划，进而生成能源供应计划。

具体技术方案如下：

一种多目标的能源供应与作业柔性排程方法，包括以下步骤：

(1)确定柔性排程的能源供应优化指标与能源供应约束，构建多目标能源供应优化模型；所述的多目标能源供应优化模型的目标函数包括最大完工时间最小的目标函数、能耗最大负荷最小的目标函数以及总能耗负荷最小的目标函数；

(2)采用改进的遗传算法求解所述的多目标能源供应优化模型，使得最大完工时间最小的目标函数、能耗最大负荷最小的目标函数以及总能耗负荷最小的目标函数均达到最小值，获得最优的能源供应与作业柔性排程；所述的改进的遗传算法采用自适应的交叉和变异概率，采用基于NSGA-Ⅱ的选择操作。

本发明的柔性排程方法考虑了动力能源消耗，以最大完工时间最小、能耗最大负荷最小以及总能耗负荷最小为能源优化指标，采用改进的遗传算法辅助调度人员快速生成排产计划，进而生成能源供应计划，实现生产的节能增效。

最大完工时间指某产品完成其所有加工工序的最大时间，代表着生产作业的效率，能源供应排程时也要服务于这一生产优化的根本指标，最大完工时间最小的目标函数为：

其中，i表示工序编码；n表示工序数；t

能源供应的一个重要方面就是减少浪费，而不同加工工序所需的能耗负荷是不一样的。不失一般性，认为某工序所在设备能源有预备、供应、退出的过程，预备过程中能耗负荷从0逐渐加大，退出过程负荷逐渐减小直至为0，供应过程中能耗负荷保持不变。通过使得能耗负荷尽量小而均匀，能够有效提高能源的使用效率，能耗最大负荷最小的目标函数为：

其中，j表示设备编码；m表示设备数；h表示工序执行总数，h

由于不同设备对不同能源的需求量不一定相同，所以总能耗负荷随着排程方案而异。在满足上述最大完工时间最小、设备最大能耗最小的前提下，如果让总能耗负荷，也可达到节能的目的，总能耗负荷最小的目标函数为：

优选的，步骤(2)包括：

(2-1)建立柔性排程染色体编码，染色体包括设备选择部分和工序排程部分；设备选择部分与工序排程部分的长度相同，均等于所有工序的总和S；

(2-2)对设备选择部分和工序排程部分均采用随机生成的方式来生成，构成个体；生成N个个体，构成初始种群P

(2-3)通过交叉和变异操作，得到子代Q

(2-4)将P

(2-5)通过快速非支配前端排序算法求得种群中每个个体的适应度函数；

(2-6)运用拥挤度比较算子执行自然选择过程，得到个体数为N的下一代种群P

(2-7)迭代执行步骤(2-3)-(2-6)，直至达到预设终止条件。

所述的预设终止条件可设置为达到最大迭代次数，当达到最大迭代次数时即停止搜索。

本发明在全局搜索方面，运用改进的遗传算法进行全局寻优；在局部搜索方面，运用变领域搜索算法快速改变搜索区域，避免搜索局部区域得到局部最优解；在多目标优化方面，通过非支配排序的方式对多个优化目标进行综合评价。

本发明的方法综合了多目标优化、变邻域搜索、基于个体拥挤距离的锦标赛选择、自适应交叉和变异概率等方法，能够较好地提高企业传统的作业排程能力，提高生产效率，降低能源消耗。

由于能源供应柔性排程主要研究两个问题：设备选择与工序排程。设备选择是指确定每个生产任务的可选设备集；工序排程是指选定设备后工序的先后顺序及开始加工时间。而能源的供应主要是由设备、工序排程、工序要求所确定的，并使用一定的策略。为此，本发明在染色体编码时选择设备与工序联合编码方式，染色体分为两段，一段记录设备选择，一段记录工序排程。

优选的，步骤(2-1)包括：

(2-1a)采用整数对可选设备进行编号，以整数指代设备序号填入设备选择部分的染色体基因位；染色体基因按生产任务依次排列；

(2-1b)采用整数对工序进行编号，相同工序编号出现次数即为该工序的执行总数，以整数指代工序序号填入工序排程部分的染色体基因位；在所选设备上，从左到右依次加工。

优选的，步骤(2-2)中，对设备选择部分和工序排程部分均采用随机生成的方式来生成，构成个体，包括：

(2-2a)假设共有n项作业w

设置数组A和数组B，各数组长度为所有工序总和S，数组A存放从1至S所有工序的可选设备的编号

(2-2b)在数组A中，从作业1的第1道工序的可选设备集里随机抽取一个设备，将该设备的编号存入数组A的第1个位置；从作业1的第2道工序的可选设备集里随机抽取一个设备，将该设备的编号存入数组A的第2个位置，依次操作，直至从作业n的最后1道工序的可选设备集里随机抽取一个设备，将该设备的编号存入数组A的第S个位置；

(2-2c)在数组B中，在满足产品加工工艺的基础上，将作业的工序编号随机存入数组B的各个位置；

(2-2d)将得到的数组B衔接至数组A尾部，形成一个染色体编码，即一个个体。

为生成新的个体，在满足交叉算子基本要求(继承、完全、非冗余等)的基础上，对设备选择部分执行均匀交叉，对工序排程部分执行作业优选顺序的POX交叉。

设备选择部分进行均匀交叉，可保证各基因位间先后顺序不会改变。均匀交叉方法如下：通过随机生成一个屏蔽字来决定子代个体如何从父代个体获得基因。这个屏蔽字的长度要与个体基因串长度相同，且均由0，1生成。比如说屏蔽字的第一位数是0，那么第一个子代个体基因串的第一位基因便继承父代个体A，第二个子代个体基因串的第一位基因便继承父代个体B；如果屏蔽字的第一位数是1，那么第一个子代个体基因串的第一位基因便继承父代个体B，第二个子代个体基因串的第一位基因便继承父代个体A。以此类推。

工序排程部分进行POX交叉，染色体p1和p2交叉生成两个子代c1和c2，交叉过程如下：1)随机划分作业集为两个非空子集o1和o2；2)复制p1中属于作业集o1中作业的工序到c1，复制p2中属于作业集o1中作业的工序到c2，保留它们的位置；3)复制p1中属于作业集o2中作业的工序到c2，复制p2中属于作业集o2中作业的工序到c1，保留它们的顺序。

为增强遗传算法的局部搜索能力，结合柔性排程的业务特性，优选的，步骤(2-3)中，所述的变异操作包括：

设备选择部分：随机生成若干个变异点；针对每个变异点位上的工序，在其对应可选设备集中选择加工时间最短的设备，如果当前的设备加工时间最短，则选择次短的设备；

工序排程部分：采用基于邻域搜索变异方式，包括：

(a)在工序排程部分的染色体c上随机选出m个基因位，基于这些基因位生成可能的变异邻域N

(b-1)令i＝1；

(b-2)重复下列过程，直到i＝m；

(b-2-1)解染色体c在变异邻域N

(b-2-2)若c′优于c，则c＝c′，i＝1，否则i＝i+1。

在交叉操作或变异操作中，交叉概率p

其中，f

步骤(2-5)包括：将种群P根据个体之间的支配关系，分成具有支配关系且互不交叉的前端子种群支配关系p

其中，n

步骤(2-6)中，首先保留最优非支配曲面的所有解，如果个数小于N，则继续保留第二非支配曲面的解，以此类推，直至无法保留此非支配曲面的所有解，即保留总数大于N，则运用拥挤比较算子选取适应度函数值更优的解，直至总数达到N，完成选择过程。

与现有技术相比，本发明的有益效果为：

(1)本发明考虑动力能源消耗问题，以能源优化指标采用改进的遗传算法搜索最优的柔性排程，以实现节能增效的目的；

(2)遗传算法通过模拟自然界中生物的生存竞争过程，利用选择、交叉、变异等算子，能够对复杂工程问题进行全局寻优。但传统的遗传算法的局部搜索能力受到限制，在搜索过程中容易陷入局部最优解。本发明对传统的遗传算法进行改进，一方面，适应目标问题中多目标优化求解，对遗传种群中个体根据拥挤距离进行非支配排序，不仅满足生产时间要求，也满足节能要求；另一方面，结合变邻域搜索算法，改进局部搜索能力，提升了算法性能。

附图说明

图1为改进的遗传算法的流程示意图；

图2为染色体编码结构示意图；

图3为通过选择操作生成新种群的过程示意图。

具体实施方式

下面结合附图和实施例对本发明作进一步详细描述，需要指出的是，以下所述实施例旨在便于对本发明的理解，而对其不起任何限定作用。

1、在构建柔性排程优化指标与能源供应约束，建立能源供应柔性排程数学模型的基础上，设计改进的遗传算法，改进的遗传算法流程如图1所示，步骤如下：

(1)建立柔性排程染色体编码与解码。

(2)初始化柔性排程种群。

(3)实施基于NSGA-Ⅱ方法的锦标赛选择操作。

(4)实施染色体交叉操作。

(5)实施染色体变异操作。

(6)判断是否达到终止条件。

2、建立能源供应柔性排程优化指标，包括：

1)最大完工时间最小。最大完工时间指某产品完成其所有加工工序的最大时间，代表着生产作业的效率，能源供应排程时也要服务于这一生产优化的根本指标，可表示为：

其中，i表示工序编码，t

2)能耗最大负荷最小。能源供应的一个重要方面就是减少浪费，而不同加工工序所需的能耗负荷是不一样的。不失一般性，认为某工序所在设备能源有预备、供应、退出的过程，预备过程中能耗负荷从0逐渐加大，退出过程负荷逐渐减小直至为0，供应过程中能耗负荷保持不变。通过使得能耗负荷尽量小而均匀，能够有效提高能源的使用效率，可表示为：

其中，j表示设备编码，m表示设备数，h表示工序数量，h

其中，a

3)总能耗负荷最小。由于不同设备对不同能源的需求量不一定相同，所以总能耗负荷随着排程方案而异。在满足上述最大完工时间最小、设备最大能耗最小的前提下，如果让总能耗负荷最小，也可达到节能的目的，可表示为：

3、本方法是一种复合方法，在全局搜索方面，运用改进的遗传算法进行全局寻优；在局部搜索方面，运用变领域搜索算法快速改变搜索区域，避免搜索局部区域得到局部最优解；在多目标优化方面，通过非支配排序的方式对多个优化目标进行综合评价。

4、建立柔性排程染色体编码方案

由于能源供应排程主要研究两个问题：设备选择与工序排程。设备选择是指确定每个生产任务的可选设备集；工序排程是指选定设备后工序的先后顺序及开始加工时间。而能源的供应主要是由设备、工序排程、工序要求所确定的，并使用一定的策略。为此在染色体编码时选择设备与工序联合编码方式，为此，染色体编码方案如图2所示，分为两段，一段记录设备选择，一段记录工序排程：

1)设备选择部分，长度为S(工序总和)。由于每个工序所能选择的设备是有限的，可选设备集设为M

2)工序排程部分，长度也为S。用整数表示工序编号，相同工序编号出现次数即为该工序的执行总数h

5、种群初始化

为避免低质量的初始种群对算法执行速度与质量的影响，针对本方法所采用的染色体编码的特征，采用对设备选择和工序排程均随机生成的方式来生成初始种群。具体为：

1)假设共有n项作业w

2)在数组A中，从作业1的第1道工序的可选设备集M

3)重复步骤2)，直至作业n的最后1道工序的设备被随机选取并将设备序号存入数组A第S个位置。

4)在数组B中，在满足产品加工工艺的基础上，将作业的工序编号随机存入各个位置。

5)重复步骤4)直至所有作业、工序均存放完毕，然后数据B衔接到数据A尾部，形成一个染色体编码。

6、实施染色体交叉操作。

为生成新的个体，在满足交叉算子基本要求(继承、完全、非冗余等)基础上，对设备选择部分执行均匀交叉，对工序排程部分执行基于作业优先顺序的交叉。

1)设备选择部分进行均匀交叉，可保证各基因位间先后顺序不会改变。均匀交叉方法如下：通过随机生成一个屏蔽字来决定子代个体如何从父代个体获得基因。这个屏蔽字的长度要与个体基因串长度相同，且均由0，1生成。比如说屏蔽字的第一位数是0，那么第一个子代个体基因串的第一位基因便继承父代个体A，第二个子代个体基因串的第一位基因便继承父代个体B；如果屏蔽字的第一位数是1，那么第一个子代个体基因串的第一位基因便继承父代个体B，第二个子代个体基因串的第一位基因便继承父代个体A。以此类推。

2)工序排程部分进行POX交叉，染色体p1和p2交叉生成两个子代c1和c2，交叉过程如下：1)随机划分作业集为两个非空子集o1和o2；2)复制p1中属于作业集o1中作业的工序到c1，复制p2中属于作业集o1中作业的工序到c2，保留它们的位置；3)复制p1中属于作业集o2中作业的工序到c2，复制p2中属于作业集o2中作业的工序到c1，保留它们的顺序。

7、实施染色体变异操作。

为增强遗传算法的局部搜索能力，结合柔性排程业务特性，采用如下的变异方式：

1)设备选择部分：随机生成n个变异点；针对每个变异点位上的工序，在其对应可选设备集M

2)工序排程部分：采用基于邻域搜索变异方式，具体为：

a.在工序排程部分染色体c上随机选出m个基因位，基于这些基因位生成可能的变异邻域N

b.重复下列过程，直到算法终止：

b-1令i＝1；

b-2重复下列过程，直到i＝m；

b-2-1解c在邻域N

b-2-2若c′优于c，则c＝c′，i＝1，否则i＝i+1。

8、自适应交叉和变异概率

上述交叉和变异操作中的交叉概率p

其中，f

9、染色体选择操作。

本步骤采用基于NSGA-Ⅱ的锦标赛选择操作，该操作可保持染色体的多样性。首先定义P

1)随机产生初始代种群P

2)通过交叉算子与遗传算子得到子代Q

3)合并种群P

4)通过快速非支配前端排序算法求得种群中每个个体的适应度函数。将种群P根据个体之间的支配关系，分成具有支配关系且互不交叉的前端子种群支配关系p

5)通过拥挤比较算子执行自然选择过程。同时，在选择过程中引入精英机制，保留排在前面的非支配曲面。具体来说，首先保留最优非支配曲面的所有解，如果个数小于N，则继续保留第二非支配曲面的解，以此类推，直至无法保留此非支配曲面的所有解，即保留总数大于N，则运用拥挤比较算子选取适应度函数值更优的解，直至总数达到N，完成选择过程。其中每一前端内部个体间拥挤距离d计算公式如下：

其中，n

6)得到个体数为N的下一代种群P

7)按照模型的规定进化次数重复执行2-6步，直至完成算法。

10、终止准则

本方法采用最大迭代次数为终止准则，即算法进化到一定迭代次数即停止搜索。

以上所述的实施例对本发明的技术方案和有益效果进行了详细说明，应理解的是以上所述仅为本发明的具体实施例，并不用于限制本发明，凡在本发明的原则范围内所做的任何修改、补充和等同替换等，均应包含在本发明的保护范围之内。