考虑可再生能源的多目标柔性流水车间调度问题

吴秀丽，崔 琪

(北京科技大学 机械工程学院，北京 100083)

0 引言

近几十年来，人们越来越关注全球变暖和气候变化问题。众所周知，全球变暖是由温室气体排放量增加造成的，尤其是化石燃料燃烧过程中产生的二氧化碳，而能源发电的主要来源是化石燃料，因此降低能源消耗能够显著减少二氧化碳排放量，从而减缓全球变暖。国家“十三五规划”对我国节能减排提出了新的目标，到2020年单位GDP二氧化碳排放比2005年下降40%～45%，争取在2030年达到二氧化碳排放的峰值。为此，我国采取并强化了一系列节能减排措施，例如建立完善的节能减排制度、法律和市场环境，积极构建低碳生产制造体系，大力发展新型储能装置和储能技术，增加工业生产过程中可再生能源的利用[1]。

据研究，工业生产能耗占全球能源消耗总量的一半左右[2]。制造企业已经成为全球气候变暖的一个重要来源，碳排放很可能被未来的高税收和相关规定所限制[3]。面对这种情况，制造企业必须寻求切实可行的办法，以减少生产过程中的能源消耗和碳排放。在全球气候变暖问题日益严峻及传统能源日益紧缺的情况下，探索开发新能源是节能减排的有效途径。

冶金、化工、机械制造、钢铁等高耗能流程工业中的生产方式大多是流水作业，大多数类似的加工生产过程可抽象为柔性流水车间调度问题(Flexible Flow Shop Scheduling Problem, FFSP)。FFSP的主要特征是某些或所有工序上存在并行机器，即每个工件的每道工序可以在几个可选择的机器上加工，并且每台机器的加工时间不同。

目前主要采用智能优化算法求解FFSP，如遗传算法[4]、分布估计算法[5]、蚁群算法[6]等。随着对全球气候问题的研究和节能减排政策的颁布，国内外针对面向节能的流水车间调度问题的研究越来越多，根据节能目标的不同，这些研究大致可分为以能耗为目标[7]、以电力高峰负荷为目标[8]和以电力成本为目标3类[9]，其中以能耗为目标的流水车间调度问题研究最多。例如，刘向等[10]针对FFSP，以能耗最小为目标函数建立数学模型，提出一种结合局部搜索的混合遗传算法(memetic algorithm);Dai等[11]采用改进的模拟遗传算法求解以降低能耗和完工时间为目标的FFSP；曾令李[12]针对FFSP，以最大流程时间和最小能耗为目标建立数学模型，提出一种混合粒子群算法；周严伟[13]对考虑车间耗能的多目标流水车间调度问题进行研究，利用快速非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm-Ⅱ, NSGA-Ⅱ)进行求解；张立萍[14]采用混合差分算法求解面向节能的流水车间调度问题。

最近几年，人们探索替代能源的兴趣与日俱增，替代能源可以降低成本消耗和对环境的影响，如可再生能源。可再生能源不会产生温室气体，不会造成空气污染，也没有处理长期废弃物的问题和发生灾难性事故的风险[15]。随着可再生能源发电技术及大规模储能技术的大力发展，可再生能源的有效利用必将成为未来的趋势，而在生产过程中利用可再生能源，不仅能够有效降低非再生能源的消耗，还能够减少碳排放。利用可再生能源实现高耗能企业的节能减排，需要解决将可再生电源接入现有电网为高耗能企业供电的问题。现有研究表明，微电网技术是发挥可再生能源效益最有效的方式之一[16]。目前已有学者考虑将微电网技术应用于高耗能企业，通过利用可再生能源来实现节能减排。邢文[17]针对高耗能企业，以增加可再生能源的利用为前提，设计高耗能企业微电网平台，通过最大化利用可再生能源来提高企业能源效率，降低温室气体的排放，减少环境污染;胡真[18]以微电网理论为基础，对高耗能企业能源微电网的经济效益进行了分析和优化，通过实验证明了在保证高耗能企业正常生产的前提下,充分利用可再生能源，融合自备电厂发电，能极大地提高微电网的整体经济效益，减少能量损失和碳排放；李能学[19]以高耗能企业为研究对象，建立了含风电与自备电厂的高耗能企业新能源微电网模型，通过算例仿真,证明了新能源微电网和需求响应在降低经济成本、减少碳排放方面的巨大作用,为高耗能企业调整能源结构、提高经济效益提供理论和数据支撑;李明[20]等针对可再生能源的消纳问题，分析得出高载能企业具备参与电网调节、增加可再生能源消纳的能力,提出考虑高载能企业的“荷—网—源”协调控制的思路;陈润泽等[21]研究了高载能企业参与电力系统调度的相关问题，提出多种联合调度模式，通过算例展示了联合调度的必要性及其在消纳大规模可再生能源时的效益。考虑可再生能源生产调度问题的研究刚刚起步，成果尚有不足，仅有Wang等[22]研究的考虑可再生能源的低碳生产调度问题，该文提出考虑可再生能源的低碳生产调度系统架构，以最小碳排放量为目标建立数学模型，针对单机调度问题设计了低碳生产调度算法。

因此，本文针对考虑可再生能源的柔性流水车间调度问题(Flexible Flow Shop Scheduling Problem with Renewable Energy, FFSP-RE)，并根据可再生能源特性建立可再生能源供电模型，在此基础上建立FFSP-RE数学优化模型，提出一种利用可再生能源以减少碳排放的调度机制，设计NSGA-Ⅱ。通过一个铝工业生产调度实例，针对铝工业能耗情况搭建微电网仿真场景，进行数值实验，通过对比低碳解码与时间优先解码两种解码机制，证明了低碳解码调度能够在保证完工时间的前提下有效减少碳排放；通过对比FFSP-RE与标准的FFSP实验结果，验证了求解算法的有效性，并证明了考虑可再生能源能够大幅减少碳排放，具有一定的现实意义和研究价值。

1 FFSP-RE优化模型

1.1 问题描述

1.1.1 可再生能源

可再生能源[23]指资源不因开发利用而减少或可周期性恢复的能源，包括水能、风能、太阳能、生物质能、地热能和海洋能等，具有资源分布广、利用潜力大、环境污染低、可永续利用的特点。可再生能源发电是可再生能源利用的主要形式。目前，风能和太阳能发电技术已经非常成熟。由于可再生能源资源自身的固有特性，与煤炭等常规能源发电技术相比，可再生能源发电具有随机性和间歇性的特点，例如风能资源时大时小、时有时无，太阳能资源白天有、晚上无。

本文以太阳能光伏电站[24]为例，选取中国西部某省份的实测数据，分析2010年200 MWp装机的光伏电站发电的输出特性。图1和图2所示分别为典型晴天、阴天日发电输出曲线图和连续一周发电输出曲线图。从图1可以看出，晴天光伏电站的发电输出特性曲线类似于光滑的正弦半波，发电时间集中在上午6点至下午6点之间，在中午12点达到峰值;阴天由于受到云层遮挡，辐照数据波动较大，造成光伏电站的发电输出短时间内波动较大，但是即便在阴天，发电依旧集中在早6点至晚6点，在正午左右达到峰值。从图2可以看出，连续一周光伏电站的发电输出具有明显的周期性和随机性。

由于可再生能源的间歇和随机特性，可再生能源发电难以控制，无法确保及时响应电力需求，成为制约可再生能源发电发展的一大因素。而实际的生产加工具有连续性，需要稳定的电力供能，若用可再生能源为企业供电，则需要解决可再生能源发电与电力需求之间的不匹配问题。

为了解决可再生能源供电问题，微电网技术应运而生。微电网是由分布式电源、储能装置、能量转换装置、负荷、监控和保护装置等组成的小型发配电系统，是一个能够实现自我控制、保护和管理的自治系统，其能够满足用户对电能质量和供电安全的需求，既可以与外部电网并网运行，也可以孤立运行[25]。企业可以自建一个光伏电站微电网，当微电网孤立运行时，生产用电来源于太阳能；当微电网切换至并网运行时，生产用电来源于普通电网的非再生能源。由于太阳能的间歇性和随机性，在发电的同时进行供电不能保证生产的连续性，因此需要储能装置先将太阳能产生的电能存储下来，再由储能装置进行稳定供电。在企业的光伏电站微电网内设置两个储能装置，将某天太阳能产生的电存储在储能装置1中，第二天微电网孤立运行时使用储能装置1的电能，即前一天太阳能产生的电能，储能装置2则存储第二天太阳能产生的电能。

微电网技术使利用可再生能源降低工业生产碳排放成为可能，目前已有研究[17]将微电网技术应用于高耗能企业。

1.1.2 FFSP-RE问题描述

FFSP-RE是一类典型的组合优化问题(如图3)，一般可以描述为：n个工件有m道工序需要加工，每道工序有Mj台不相同的并行机器(j=1,2,…,m,Mj≥1)，工件排产到第j道工序时可以被该工序并行的Mj台机器中的任一台机器加工，加工时间可以不同，单位时间能耗也可以不同。每台机器有加工和空转两种模式，对应每台机器的两种模式，每台机器的能耗由加工能耗和空转能耗两部分组成。

化石燃料燃烧是我国碳排放的重要来源，因此能源消费活动中产生的碳排放是我国碳排放量的主要部分。我国消费的能源种类主要包括煤类、油类、天然气，以及水电、太阳能电和风电，其中煤类、油类和天然气属于化石燃料，其在燃烧过程中释放大量二氧化碳等温室气体，产生碳排放;太阳能和风属于可再生能源，其在转化为电能的过程中不会产生碳排放。碳排放量指在生产、运输、使用及回收时所产生的平均温室气体排放量,本文中的碳排放主要来源于调度过程中机器的加工能耗和空转能耗。

FFSP-RE与FFSP的区别在于生产过程中考虑使用可再生能源，不只用普通电能供电，而是利用光伏电站微电网技术，由太阳能和普通电网协同为车间供电。考虑到太阳能发电的周期性和随机性，以及储能装置容量的有限性，太阳能无法长期向车间供电，将生产过程划分为若干周期，每一周期内太阳能的发电量根据天气状况随机波动，且可使用量不超过储能装置的容量。由于太阳能的特性，利用太阳能为车间供电期间，无论生产加工还是机器空转均不会产生碳排放。因此为了保证企业能够最大限度地降低碳排放量，在每个周期内均优先由太阳能光伏电站微电网孤立运行进行供能，储能装置中的能量用尽后，微电网切换至并网运行，由传统电网供电，产生碳排放。

为便于讨论，表1给出一个FFSP-RE的例子，该问题包括4个工件，每个工件有3道工序，表中数据是每道工序在不同机器上的加工时间，表2所示为各工件各工序单位时间加工能耗，表3所示为各机器的空转能耗，太阳能的发电周期为24 h。

表1 加工时间 h

表2 加工能耗 kW·h

表3 机器空转能耗 kW·h

图4所示为该问题的一个调度方案，每个矩形框内的数字表示“(工件号，工序号)”，纵坐标表示机器号，横坐标表示时间。图5所示为该调度方案的能源分配调度方案，每个矩形框内的数字表示“能源使用量”，浅色部分表示在此期间工件加工使用的是可再生能源，深色部分表示在此期间工件加工使用的是普通能源。

FFSP-RE以最大完工时间和碳排放量为优化目标，与现有研究不同的是其生产加工过程中考虑使用两种能源。因此，在确定工件加工顺序和各工序机器分配两个子问题的基础上，增加了能源分配问题。由于不同机器的单位能耗和加工时长不同，工件选择不同的机器进行加工将会影响总碳排放量和完工时间。传统的调度解码算法通常根据加工时间长短来选择机器，而FFSP-RE则需要同时考虑加工时间和碳排放量进行机器选择。由于太阳能的周期性和有限性，每个周期内太阳能的可用量是有限的。为了降低碳排放量，在每个周期内优先使用太阳能以保证最大化利用太阳能，从而使碳排放量尽可能最低。从图5能够看出，最大完工时间越小，每个周期排产的工件越多，而太阳能可用量是一定的，太阳能用尽后将会消耗更多的非再生能源，产生更多的碳排放，反之亦然。本文通过机器选择和能源分配能够在保证完工时间的前提下降低碳排放量。

从图4和图5可以直观地看出，进行工件调度时，每插入一个新的工件，不仅会影响调度的完工时间和机器分配情况，还会影响插入工件所在周期的能源分配情况，进而影响总碳排放量，这大大增加了调度的难度。传统的调度解码算法专注于求解工件加工顺序和机器分配，无法考虑两种能源的分配问题。问题规模为n的FFSP的计算复杂性为O(n!)，已经被证明是一个NP难问题[26]，随着问题规模的增大，问题的解空间呈阶乘级增长，FFSP-RE在FFSP的基础上还需要进行能源分配，具有更复杂的求解难度。因此，本文针对FFSP-RE，建立了可再生能源供电模型和FFSP-RE数学模型，提出一种考虑可再生能源特性的低碳调度策略，设计了NSGA-Ⅱ。

1.2 假设条件

(1)一般性假设条件

1)工件是相互独立的，每个工件是一个整体不能分割。

2)工件一旦开始加工便不允许中断，不得中途停止插入其他工件。

3)每个工件的每道工序只能选择一台机器进行加工。

4)每个工件在每道工序上的加工时间事先已知。

5)每台机器同一时刻只能加工一个工件。

(2)FFSP-RE假设

假设一个柔性流水车间的运作由能够与普通电网并网运行的太阳能光伏电站微电网供电。有两种供电阶段：①微电网孤立运行，离网供电，由太阳能发电及微电网自带的储能装置供电;②微电网并网运行，由普通电网供电，即消耗非再生能源。基于此，特增加以下假设：

1)工件在每道工序每台机器上的加工时间和各台机器的单位时间加工能耗及空转能耗为己知和固定的。

2)机器所需要的能量可以通过储能装置(太阳能发电)和普通电网(火力发电)提供。

3)储能装置由太阳能对其充电，具有固定的容量。

4)所有加工机器优先使用太阳能储能装置，储能装置的电能用尽后再切换至普通电网。

5)太阳能发电的周期是24 h。

1.3 符号定义

符号定义如表4所示。

表4 符号定义

1.4 数学模型

1.4.1 可再生能源供电模型

根据图1得到太阳能一个周期内的发电量tt，

(1)

式中：h0为周期t的开始时刻，h1为周期t的结束时刻，SE(h)为周期t内每一时刻h太阳能的发电量函数。从图1的太阳能光伏电站发电输出特性曲线可以看出，一天中的太阳能发电特性近似符合正态分布，可以用正态分布的概率密度函数表达为

h∈[0,24];

(2)

SE(h)=

(3)

式中：F1为晴天时的太阳能发电输出峰值，F2为阴天时的太阳能发电输出峰值。

1.4.2 FFSP-RE数学优化模型

大多数生产制造企业追求的目标都是高效快速地完成生产加工任务，在节能减排的大形势下，节能降耗、减少碳排放成为企业新的目标。因此确定优化目标函数为最大完工时间和碳排放量，建立如下FFSP-RE的数学模型：

(4)

minf2=max(Cijk)。

(5)

s.t.

(6)

Cijkxijk≤Si(j+1)rxi(j+1)r,i=1,2,…,n,

j=1,2,…,m,k∈Mj,r∈Mj+1;

(7)

Pijkxijk=PEijkxijk+PRijkxijk,

i=1,2,…,n,j=1,2,…,m,k∈Mj;

(8)

Cijkxijk=Sijkxijk+Pijkxijk,

i=1,2,…,n,j=1,2,…,m,k∈Mj;

(9)

CRjkjkxRjkjk≤S(R+1)jkjkx(R+1)jkjk,j=1,2,…,m,

k∈Mj,R=1,2,…,Njk-1;

(10)

Ijk=IERjk+IEEjk,

j=1,2,…,m,k∈Mj;

(11)

SRt=min(Q,bt-1),t=1,2,…,T;

(12)

IEjkIERjkzjkt≤SRt,t=1,2,…,T;

(13)

i=1,2,…n,j=1,2,…m,k∈Mj;

(14)

xijk∈{0,1},∀i,j,k;

(15)

yijkt∈{0,1},∀i,j,k,t;

(16)

zjkt∈{0,1},∀j,k,t。

(17)

其中：式(4)为碳排放量的计算公式，0.680为中国工程院给出的单位标准煤燃烧的碳排放系数[27]，碳排放系数的单位为吨碳/吨标准煤(tC/tJ)，即每燃烧1 t标准煤将产生0.68吨碳，由于电力转换系数的计量单位是吨标准煤/千瓦时(tJ/kWh)，因此也可描述为每消耗1度电将产生0.68 kg碳；式(5)为完工时间目标函数;式(6)为分配约束，表示分配给每道工序所有可用机器的工件数之和为n；式(7)～式(11)为时间约束，式(7)表示工艺约束，即每个工件下一阶段的作业必须在上一阶段完成后才能开始；式(8)表示每个工件在每道工序上使用两种能源的加工时间之和等于每个工件在每道工序上的加工时间；式(9)表示任何工件的完成时间取决于其在某机器上的处理时间和开始时间；式(10)表示每台机器在同一时间仅能处理一个工件，即工序j的机器k上加工的第R+1个工件的开始加工时间，必须大于或等于工序j的机器k上加工的第R个工件的完成加工时间；式(11)表示每台机器使用两种能源的空转时间之和等于该机器的空转时间;式(12)和式(13)为可再生能源约束，式(12)表示周期t内可使用的太阳能来自于前一周期太阳能产生的电能，且不得超过储能装置容量Q，式(13)表示周期t内，使用太阳能进行加工时的总能耗及机器空转总能耗不超过周期t内可使用的太阳能;式(14)表示每个工件在每道工序上的加工只能被分配给一台机器;式(15)～式(17)为变量有效性约束。

2 快速非支配排序遗传算法

遗传算法是基于自然进化和选择机制的智能优化算法，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等众多领域，具有全局寻优能力强、快速、易于实现等优点。快速非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm-Ⅱ, NSGA-Ⅱ)在求解多目标优化问题上表现良好[13]，因此本文结合FFSP-RE的特点，提出考虑可再生能源特性的低碳调度解码算法，设计了基于操作编码的NSGA-Ⅱ。

2.1 总体流程

FFSP-RE需要求解工件排序、机器分配、能源分配3个子问题。由于可再生能源具有间歇性和随机性的特点，且现有储能设备有容量限制，在设计解码算法时引入“可再生能源周期”的概念，设计能源分配规则。在一个周期内，采取优先消耗可再生能源的能源使用规则，当可再生能源消耗完后切换至传统电网。调度过程中，对于跨周期生产的工件，根据每周期的能源消耗情况，在不同的周期为工件分配不同的能源。FFSP-RE问题是多目标优化问题，目标函数为最大完工时间和碳排放量，本文采用集成低碳调度策略的NSGA-Ⅱ求解FFSP-RE问题，在解码过程中，每周期内优先使用太阳能，在保证完工时间最小的情况下，通过选择碳排放量最小的机器达到低碳的目的。

为此，针对这3个子问题，借助NSGA-Ⅱ的基本思想，求解可再生能源的FFSP问题的算法总体流程如图6所示，具体操作步骤如下：

步骤1设置总迭代次数gen、种群规模Psize、交叉概率Pc、变异概率Pm。

步骤2初始化。将所有待加工工件的加工顺序作为一条染色体，随机生成Psize个染色体，令迭代次数u=0。

步骤3如果满足终止准则(u>gen)，则输出最优Pareto解集；否则，利用考虑可再生能源特性和容量限制的低碳调度解码算法计算种群中所有染色体个体的最大完工时间和总碳排放量，记录全局最优Pareto解集为BestBX。

步骤4适应度计算。采用权重系数法计算个体适应度，分别为两个目标赋予随机数权重，然后线性相加得到个体适应度值。采用轮盘赌选择法选取Psize个染色体进入交叉操作。

步骤5根据交叉概率Pc选取进行交叉的父代个体，随机选择线性次序交叉(Liner Order Crossover，LOX)和基于位置的交叉(Position-Based Crossover，PBX)两种交叉算子进行交叉，得到子代个体。

步骤6根据变异概率Pm选取进行变异的个体，随机选择染色体中的两个基因位置，对两个基因位置间的基因片段执行反转逆序操作得到新的个体。

步骤7交叉变异操作结束后，将子代个体与父代个体合并，组成一个规模为2×Psize的新种群。

步骤8计算规模为2×Psize的新种群的最大完工时间和总碳排放量，对种群内个体进行快速非支配排序。

步骤9若非支配等级为1的个体数量大于Psize，则计算每个个体的拥挤度，进行升序排列，选择拥挤度小的个体进入下一代种群；若数量小于Psize，则对非支配等级为2及其以上的个体，计算每个个体的拥挤度。对这些个体随机进行两两比较，根据每个个体的非支配等级和拥挤度决定该个体是否进入下一代种群。然后将种群规模恢复为Psize。

步骤10求出当前种群中的Pareto最优个体，记录当前最优解集为CurrentBX。将当前最优解集CurrentBX与全局最优解集BestBX合并，求出新的Pareto最优个体，更新BestBX。令u=u+1，继续执行步骤3。

2.2 详细设计

2.2.1 编码与初始化

本文采用基于操作的编码方式，加工工件的编号是构成染色体个体的基因值，工件编号在染色体中的位置表示该工件的加工顺序。例如有4个待加工工件的FFSP，取P1=[2 4 3 1]为一个染色体个体，其中： 第1位2表示工件2第1个加工， 第2位4表示工件4第2个加工，第3位 3表示工件3第3个加工， 第4位1表示工件1第4个加工。染色体由所有待加工工件的工件号随机排列生成，工件编号在染色体中出现的位置决定了该工件的加工顺序。然后根据工件的加工顺序，采用一定规则的解码算法确定该种调度方案的碳排放量和最大完工时间。

根据上述编码方式，若待加工工件为n，则随机产生Psize个1×n的自然数编码数组组成多目标遗传算法的初始种群。

2.2.2 低碳调度解码算法

本文以太阳能光伏电站为例，其发电周期为24 h，通过预测未来某一段时间内的天气状况，确定每周期可再生能源的发电量，并在每个周期内最大化利用可再生能源为车间供能，由此设计如下低碳调度解码算法生成一个低碳调度方案。

步骤1针对每个工件每道工序的所有可用机器，计算当前工序的开始时间、完成时间、加工时间和机器当前负载。计算工序的开始时间时，需要比较该工件上道工序的完成时间(TP)和该机器所加工的上道工序的完成时间(TM)，取大。若TM≥TP，且在TP与TM之间存在大于该工序加工时间的空隙，则将该工序插入空隙内，开始时间为空隙前一道工序的结束时间；若TM

步骤2计算当前工件当前工序在当前机器的开始时间所在的可再生能源周期T1、完成时间所在的可再生能源周期T2，令t=T1，开始循环。

步骤4记录周期内加工各工件各工序及空转机器分别使用的可再生能源消耗量与非再生能源消耗量，根据非再生能源消耗量计算当前工件当前工序使用当前机器的碳排放量，令t=t+1，若t>T2，则结束循环；否则，返回步骤3。

步骤5选择机器，遵循如下规则：

(1)根据式(4)计算碳排放量，优先选取碳排放量最小的机器。

(2)若碳排放量相同，则根据可再生能源消耗量

(18)

优先选取可再生能源消耗量最小的机器。

(3)若可再生能源消耗量相同，则根据机器负载

(19)

优先选取当前机器负载最小的机器。

(4)若机器负载相同，则随机选择机器,即选择机器的优先级为碳排放量>可再生能源消耗量>机器负载。

步骤6判断是否所有工件的所有工序都已进行机器选择。若否，则返回步骤1；若是，则结束循环，输出调度方案。

步骤7根据每个工件每道工序使用的可再生能源量与非可再生能源量，计算每个工件每道工序在每个周期内使用可再生能源的开始时间和结束时间，以及使用非可再生能源的开始时间和结束时间，输出能源调度方案。

2.2.3 交叉算子

在遗传算法中，交叉算子是对两个原有染色体进行交叉，通过交叉得到更为优异的染色体，从而使种群进化。在求解FFSP的各类遗传算法中，大多数交叉算子都采用PBX和LOX[28]，因此本文也采用这两种交叉算子。

研究表明，随机采用LOX和PBX两种交叉算子的优化效果优于单一交叉算子[29]。因此在进行交叉操作时，随机采用LOX和PBX两种交叉操作，其过程是：随机产生1～2之间的整数，若为1，则采用LOX进行交叉操作；若为2，则采用PBX进行交叉操作。

2.2.4 变异算子

在遗传算法中，变异算子是对某个原有染色体进行变异，以改善算法的局部搜索能力。因为本文采用的是基于操作的编码方式，所以本文选用反转逆序的变异算子[28]。

2.2.5 非支配等级排序

将父代个体与子代个体合并后计算拥挤度，据此进行种群浓度控制，以保证种群多样性，使种群朝着更好的方向进化。在算法中引入拥挤度的定义，表示在同一非支配等级中某个个体与周围其他个体的密集程度。将同一非支配等级中所有个体的某个目标函数进行升序排列，计算个体Xi由Xi-1和Xi+1组成的长方形的平均边长，即为个体Xi的拥挤度。拥挤度计算的具体操作步骤如下：

步骤1令个体Xi的拥挤度Crowdi=0，i=1,2,…,num,num为同一非支配等级中的个体数量。

步骤2个体Xi的拥挤度计算公式[13]为

采用标准非支配排序方法[13]对种群内的个体进行排序，再利用拥挤度比较算子选择进入下一代的个体。拥挤度比较算子的规则如下：

(1)个体进行两两比较时，优先选择非支配等级小的个体。

(2)若两个个体的非支配等级相同，则选择拥挤度大的个体。

选择非支配等级小的染色体能够极大程度上保留种群中的精英个体，而同一非支配等级中选择拥挤度大的个体能够保证种群的多样性。

3 数值实验

实验数据来自某铝工业生产系统[12]，该系统有4道工序，每道工序的并行机数量分别为4,2,3,2，假设需要生产12个批量的铝土矿，已知各批量各工序在各机器上的生产时间(单位:h)和单位能耗(单位:kW·h)，以及各机器的空转能耗(单位：kW·h)。

铝工业生产属于高耗能企业，目前已有研究[17]以中国中部地区某钢铁企业的风电发电、用电负荷、大电网和储能系统等组成的微电网作为对象，根据国家推出的一系列新能源政策，搭建针对高耗能企业的微电网仿真场景。本文借鉴上述研究成果，分析中国西部某省份太阳能光伏电站发电的输出特性[20]，建立晴天和阴天两种天气状况下太阳能发电输出的数学模型，针对铝工业生产系统的能耗情况，构建太阳能光伏电站微电网仿真场景，铝工业微电网中的储能装置采用蓄电池组，以太阳能发电的周期“24 h”作为可再生能源的周期。

针对铝工业生产系统的能耗情况，假设晴天太阳能发电输出峰值F2在区间[360,400]内随机分布，阴天太阳能发电输出峰值F2在区间[240,340]内随机分布。根据式(3)计算得出晴天太阳能每个周期发电输出的总量在[1 800,2 000]内随机分布，阴天太阳能每个周期发电输出的总量在[1 200,1 700]内随机分布，从图2可以看出，7天中晴天占5天，阴天占2天，因此本算例太阳能每个周期发电输出的总量以5/7的概率在[1 800,2 000]内随机分布，以2/7的概率在[1 200,1 700]内随机分布。

NSGA-Ⅱ在Intel Core i5 2.7 GHz CPU,8 GB RAM,OS X EI Capitan操作系统和MATLAB编程环境下编译通过。算法的实验参数如下：种群规模Psize=50,迭代次数gen=200,交叉概率Pc=0.9,变异概率Pm=0.2。

为验证NSGA-Ⅱ的性能，开展以下数值实验,以验证FFSP-RE能够在保证完工时间的前提下有效减少碳排放，具有现实意义和研究价值。

3.1 低碳调度解码算法性能测试实验

本实验的目的是通过对比本文所提的低碳调度解码算法和传统调度算法，测试低碳调度解码算法对碳排放量的优化效果。分别以低碳调度解码算法和以时间优先解码的传统调度算法[31]构造调度方案，得到的实验结果如图7所示。

从图7可以看出，低碳调度解码算法求得的Pareto解个数为28个，以时间优先解码的调度算法求得的Pareto解个数为14个。当完工时间在区间[105～120]时，低碳调度解码算法的Pareto解支配以时间优先解码的Pareto解，即完工时间相同时，低碳调度解码算法求得的碳排放量均低于以时间优先解码的传统调度算法。而且低碳调度解码算法的Pareto解个数多于时间优先解码调度，有部分解支配时间优先解码调度算法的解。因此，低碳调度解码算法的表现优于时间优先解码调度算法。由所有Pareto解的碳排放量、最大完工时间的均值得到的实验结果如表5所示。

表5 低碳调度解码算法性能测试实验结果

从表5可以看出：使用低碳调度解码算法使碳排放量平均减少了24.87%，而且最大完工时间与碳排放量呈现的是相悖的关系。最大完工时间越长，意味着调度将会经历更多的可再生能源周期，调度过程中可使用的可再生能源相应增加，非再生能源消耗造成的碳排放随之减少，反之亦然。因此，通过Pareto解可为企业提供多种调度方案，决策者可以通过交工时间和碳排放定额来选择适宜的调度方案。

为了更直观地比较两种算法的差异，对于同一个染色体[5,8,7,10,6,3,2,11,12,9,1,4]，分别用低碳解码调度算法和以时间优先解码的传统调度算法求解，得到的能源调度方案如图8和图9所示。以时间优先解码的传统调度算法求得的完工时间为106 h，碳排放量为12 180.05 kg；低碳解码调度算法求得的完工时间为108 h，碳排放量为10 538.24 kg。机器1～4为加工的第一阶段，机器5～6为加工的第二阶段，机器7～9为加工的第三阶段，机器10～11为加工的第四阶段。

表6所示为图8和图9的能源调度方案对应的周期1和周期2各台机器的能源分配占比。白色部分表示可再生能源消耗，黑色部分表示非再生能源消耗。

在周期1中，第一阶段的机器1和机器2使用低碳调度解码的可再生能源的消耗占比均高于以时间优先解码的调度算法，分别高出14%和20%;第一阶段的机器3和机器4使用时间优先解码的可再生能源消耗占比高于低碳调度解码，分别高出3%和14%。总体而言，第一阶段使用低碳调度解码的可再生能源消耗占比高于时间优先解码。第二阶段使用低碳调度解码的两台机器可再生能源消耗占比全部高于时间优先解码，分别高出2%和5%。第三阶段工件选择了不同的机器，低碳解码选择机器8和机器9，而时间优先解码选择机器9，第三阶段的所有机器全部消耗非再生能源。

在周期2中，只有低碳调度解码还未完成第一阶段的加工，其第一阶段的可再生能源消耗占比为100%。第二阶段使用低碳调度解码的两台机器可再生能源的消耗占比均低于以时间优先解码的调度算法，第三阶段使用低碳解码的机器7和机器8的可再生能源消耗占比全部低于以时间优先解码的调度算法。原因是低碳调度解码在第一阶段的加工消耗了一部分可再生能源，而周期2内可再生能源的可消耗量是固定的，导致第二阶段和第三阶段可使用的可再生能源减少，因而占比低于以时间优先解码的调度算法。第四阶段工件选择不同的机器，使用以时间优先解码的调度算法的两台机器全部消耗非再生能源，可再生能源消耗占比为0%，而使用低碳调度解码的机器10可再生能源消耗占比达到了27%。

表6 低碳调度解码算法性能测试能耗对比

综上，同样的加工顺序、相同的可再生能源周期及相同的可消耗量下，两种解码机制得到的完工时间几乎相同，但低碳解码调度算法的碳排放量比时间优先解码的传统调度算法低15.58%。因为时间优先解码机制追求完工时间最快，所以在选择机器时不考虑能耗，优先选择完工时间最小的机器，而加工时间短的机器能耗相应更高，因此会消耗更多的可再生能源，而每个周期的可再生能源可消耗量是有限的，当可再生能源消耗完后，该周期将会消耗更多的非再生能源，导致时间优先解码的碳排放量更高。

结合上述实验结果能够看出，低碳调度解码算法在碳排放量的表现上明显优于传统调度算法，能够有效降低碳排放。国家对于节能减排政策的推进使得企业不再一味追求高效生产而忽视环境污染，因此生产调度需要进行多方面优化，不仅要保证按时完成生产，还要降低碳排放。本文提出的低碳调度规则能够最大限度地利用可再生能源，降低碳排放。

3.2 FFSP-RE与FFSP实验

本实验的目的是通过实例对NSGA-Ⅱ进行实验，验证NSGA-Ⅱ算法求解FFSP-RE的有效性，通过对比考虑可再生能源与不考虑可再生能源两种情况，证明FFSP-RE能够在一定完工时间内有效减少碳排放，且优化空间更大，可选择的调度方案更多。FFSP实验不考虑可再生能源，全部使用非再生能源进行调度，即各周期的可再生能源量为0。分别运行程序30次，取30次实验中碳排放量、最大完工时间的变化均值，如表7所示。

表7 FFSP-RE与FFSP实验结果对比

30次FFSP-RE实验找到的Pareto解平均为30个，最多为36个，最少为23个;30次FFSP实验找到的Pareto解平均为8.27个，最多为12个，最少为3个。与FFSP相比，FFSP-RE可以使碳排放量平均减少38.49%。分别从30次实验中随机抽取FFSP-RE和FFSP的某次实验结果，得到FFSP-RE与FFSP的Pareto解的分布对比如图10所示，碳排放量收敛曲线分别如图11和图12所示，最大完工时间收敛曲线如图13所示。

从图10可以看出，FFSP-RE算法求得的Pareto解为32个，FFSP调度算法求得的Pareto解为9个。在FFSP实验中，由于加工能耗是固定的，只能通过减少机器空转时间来优化碳排放量，优化空间有限，Pareto解的个数较少。而机器空转能耗相对于加工能耗而言比较低，FFSP对碳排放量的优化效果并不明显。在FFSP-RE实验中，由于可再生能源的周期性，每个周期都会产生新的可再生能源，当完工时间跨越更多周期时，生产中可消耗的可再生能源随之增加，碳排放量相应减少，因此优化空间更大，Pareto解的个数较多。

从图11和图12可以看出，FFSP-RE初始解的碳排放量是FFSP最优碳排放量的一半左右，证明了在生产调度中使用可再生能源能够有效减少碳排放。图10中，当完工时间在[100,120]间，FFSP-RE与FFSP的完工时间接近时，FFSP-RE比FFSP的碳排放量降低了近50%，这主要是可再生能源不产生碳排放的原因。但是当企业对完工时间有一定的容忍度，完工时间在[120,160]间时，FFSP几乎没有优化空间，无法降低碳排放量，而FFSP-RE由于可再生能源的周期性，碳排放量依旧保持良好的下降趋势。

从图13可以看出，FFSP-RE的最大完工时间明显优于FFSP，初始效果优于FFSP，最优解优于FFSP。

图14所示为加工顺序为[5,8,7,10,6,3,2,11,12,9,1,4]时，分别用FFSP-RE和FFSP算法进行求解得到的总碳排放量、加工碳排放量和机器空转碳排放量的对比情况。

从图14可以看出，同样的加工顺序下，FFSP-RE相比于FFSP，总碳排放量减少了33.47%，加工碳排放降低了33.78%，机器空转碳排放降低了27.87%。

很多企业对完工时间有一定的容忍度，在不影响交工时间的情况下，可以适当放宽对完工时间的要求。FFSP只能通过减少机器空转时间来优化碳排放量，FFSP-RE却能够在完工时间增大、跨越更多可再生能源周期的情况下，通过消耗更多的可再生能源来大幅度降低碳排放量。而且FFSP-RE相对于FFSP的Pareto解个数更多，即可选择的调度方案更多。企业的决策者可以根据实际情况，在不影响交工时间的前提下，选择碳排放量最低的调度方案。

3.3 NSGA-Ⅱ算法性能测试实验

为了比较NSGA-Ⅱ与其他优秀智能优化算法的性能，本文编程实现了文献[30]中提出的改进的遗传模拟退火算法(Improved Genetic-Simulated Annealing Algorithm, IGAA)，并与NSGA-Ⅱ的实验结果进行对比分析。将IGAA运行15次，15次最大完工时间与碳排放量解集的空间分布如图15所示。

IGAA运行一次只得到1个解，将15次运行结果放在一张图中，得到Pareto解，即图15中实线标注的4个解构成IGAA算法的Pareto解。与NSGA-Ⅱ 30次实验结果中任一Pareto解进行对比，并将两种算法求得的目标函数最小值进行对比，如表8所示。

表8 NSGA-Ⅱ与IGAA的实验结果对比

由表8可知， NSGA-Ⅱ能够找到更小的最大完工时间和更低的碳排放量，其求得的Pareto解个数远大于IGAA。NSGA-Ⅱ与IGAA算的Pareto解分布对比如图16所示。

从图16可以看出，当完工时间位于[100，120]区间时，NSGA-Ⅱ与IGAA求得的实验结果不相上下，各有优劣;当完工时间大于120时，IGAA没有找到任何解，而NSGA-Ⅱ找到了21个Pareto解。IGAA将多目标优化问题转化为单目标优化问题，虽然决策者能够根据决策需要确定两个目标函数的权重，从而影响实验结果，但是单目标优化一次仅能得到1个解，15次实验结果后能够得到的Pareto解十分有限，而且15次实验耗时较长。NSGA-Ⅱ属于多目标优化算法，其采用Pareto解的机制一次优化就能得到几十个Pareto解，从而为决策者提供更多的调度方案，且一次优化耗时较短。

综上，对于多目标优化问题，NSGA-Ⅱ算法相比于IGAA算法更优秀。NSGA-Ⅱ算法耗时短，能够在一次优化中得到多个Pareto解，且从单个目标函数来看NSGA-Ⅱ算法的优化效果也比IGAA算法优秀。

4 结束语

全球气候变暖和能源紧缺问题日益严峻，大力探索开发可再生能源是解决这些问题的重要途径。随着可再生能源的利用和存储技术越来越成熟，将其应用于工业生产过程中能够有效减少碳排放，缓解气候变暖，降低对非再生能源的消耗。

本文深入探讨了太阳能光伏电站的发电输出特性，建立了太阳能光伏电站供电模型，根据太阳能发电的周期性和储能装置存储容量的限制，针对FFSP-RE建立了碳排放量和完工时间的双目标数学优化模型，提出了NSGA-Ⅱ，并设计了低碳调度解码算法。NSGA-Ⅱ算法包括种群的选择操作、交叉操作、变异操作和非支配排序，通过非支配排序等级和拥挤度对每代Pareto解集进行浓度控制，以保留种群精英和多样性。最后针对铝工业系统构建太阳能光伏电站微电网仿真场景，进行了实例数值实验，通过性能测试证明了本文所提低碳调度解码算法能够在不影响完工时间的前提下有效降低碳排放量；相比于FFSP， FFSP-RE不但能够有效减少碳排放，降低对非再生能源的消耗，而且比FFSP的优化空间更大，可以为企业提供更多的调度方案，具有一定的现实意义和研究价值；通过与现有优秀算法进行对比，证明了NSGA-Ⅱ算法求解FFSP-RE的有效性。

本文提出的NSGA-Ⅱ能够有效求解FFSP-RE，未来的研究方向是在此基础上考虑可变加工时长的FFSP。