考虑光伏辅助供能的柔性作业车间调度

邓鑫睿 曹阳

（重庆理工大学电气与电子工程学院 重庆 401320）

光伏辅助供能的柔性作业车间调度问题（FJSPPE）是在柔性作业车间调度问题（FJSP）基础上加入了光伏储能微电网，在生产过程中，优先使用光伏储能，光伏储能使用完毕后，切换电网供电，进而减少化石能源消耗，减少碳排放。在FJSP 环境下，工件的工序加工可以选择的机器更多。车辆组装、纺织、材料加工、半导体制造等场景都可以抽象为FJSP模型，该模型是一类典型的NP难问题。

在求解FJSP方面，智能优化算法都发挥了极为重要的作用，并取得了一定的研究成果。Gu和Ding提出了一种改进型的粒子群算法（PSO），求解车间调度问题。Mouzon 和Yildirim将贪婪随机自适应搜索算法应用于以总能耗和总延误最小为目标的单机多目标优化调度问题。Rager 等人提出了一种面向能量的并行机器调度进化算法。Liu 等人提出了一种以总能耗和总加权拖期为目标的经典作业车间调度问题多目标调度方法。赵小惠等人为求解FJSP，提出一种改进型蚁群算法，仿真结果验证了算法的有效性。王家海等人设计了一种精确邻域结构混合进化算法求解FJSP。

随着绿色生产研究的兴起，智能算法优化车间调度问题成为了热门研究方向。20世纪50年代起，关于生产调度的研究就受到运筹学、应用数学等领域学者的关注。20世纪80年代起，人们就一直在尝试并致力于解决实际调度问题，调度研究由理论研究转向应用研究阶段。关于使用光伏辅助供能对碳排放的影响，吴秀丽和崔琪根据太阳能的发电特性，建立了光伏供电模型，在此基础上，构建了考虑光伏供能的柔性流水车间调度数学优化模型，通过大量实例，证明了引入光伏供能能够在保证完工时间的前提下有效降低碳排放量。

1 问题描述

光伏辅助供能的柔性作业车间调度问题可作如下描述：工件集={，，…，J}包含个工件，每个工件都需要经过一道或多道加工工序，工件J具有h道工序，工序o为工件J的第道工序。每道工序均有多台相同的机器可供选择。每台机器具有种速度，={，，…，v}为速度集合。机器的加工速度在加工工件时就已经确定，不可在加工过程中变更加工速度。

机器的状态可分为加工状态和准备状态。当机器M以速度v加工时，加工状态下单位时间的能耗为E；机器M∈不加工工件时，处于准备状态，单位时间的该机器瞬时能耗为E。每道工序o在机器M∈上有一个给定的标准加工时间η，当工序o在机器M上以速度加工时，相应的加工时间p= η v。p是工序o在机器M上的总的加工时间，总加工时间包含使用普通能源的时间pN及使用光伏电能的加工时间pL，即p= pN+ pL。

光伏辅助供能的柔性作业车间调度问题满足以下约束：不同工件的工序之间没有先后顺序约束，但同一工件的各道工序必须按照预先规定顺序完成；一台机器同一时刻只能用于一道工序的加工；每道工序同一时刻只能在一台机器上加工；工序一旦开始加工不能中断；所有加工机器优先使用太阳能储能装置供能，储能装置的能量用尽后，再切换至普通电网。

FJSP-PE 包含4 个子问题：（1）调度子问题；（2）机器分配子问题；（3）速度选择子问题；（4）能耗分配子问题。问题（1）确定每台机器加工工件的顺序，问题（2）确定每道工序的加工机器，问题（3）为每道工序的加工机器确定加工速度，问题（4）确定每台机器使用太阳能储能装置的时长。

同时，考虑以下两个目标函数。

碳排放量：

最小化最大完成时间：

其中，y()、z()均为二进制量。

时刻，机器M∈处于加工状态，则y()=1，否则，y()=0；时刻，机器M∈为准备状态，则z()=1，否则z()=0。

为能耗与碳排放量之间的转化系数，通常为0.680。表示最大完成时间，E为机器在待机状态下的单位时间能耗，E表示令机器M以速度v加工时的单位时间能量消耗。式（3）表示每台机器的空转时间包含该机器使用两种能源的空转时间；式（4）表示太阳能储能装置的容量为，周期内可使用的太阳能来自于前一周期太阳能产生的电能；式（5）表示周期内，使用太阳能进行加工时的总能耗及机器空转总能耗不超过周期内可使用的太阳能。

Ding 等给出了一种假设描述机器的加工时间与能耗的关系，即能耗与速度正相关，更快的加工速度缩短了加工时间，同时也会导致更高的能耗。因此，本文研究的两个目标函数之间的冲突关系是显而易见的，更快的加工速度会缩短最大完成时间，同时也会造成更多的碳排放量。

表1给出一个例子的加工信息，4个工件总共10道工序，其中，工件包含2道工序，工件包含3道工序，工件仅有1道工序，而工件包含4道工序。每道工序均有3台加工机器可供选择，工序在机器上的加工时间如表1所示，每台机器的能耗信息如表2所示。

图1是表1中的算例的一种调度甘特图。表2是每个阶段各台机器的加工功率及空载功率，根据相关文献中的计算方法，算出光伏供能的时间及普通能源供能的时间，绘制出能耗甘特图，如图2所示，其中，浅色部分表示工件加工消耗的是光伏能源，深色部分表示消耗的是普通能源。经计算，采用光伏辅助供能的作业车间碳排放降低18.4%。

图1 调度甘特图

图2 能耗甘特图

表1 加工信息

表2 机器能耗

2 多学习对象蛙跳算法双目标绿色FJSP

考虑一种多学习对象的蛙跳算法（MLO-SFLA）用于求解该问题。算法改变了原有的单一学习对象的选择策略，扩大的学习对象的选择范围，使得算法更容易找到更优的可行解。

2.1 编码和解码

为了独立地优化和处理各子问题，采用调度串、机器分配串和速度选择串分别地表示各子问题的解。对于具有个工件、台机器的低碳FJSP，问题的解可由调 度 串[(，)，(，)，…，(θ，r)，…，(θ，r)]，机器分配串[，，…，，…，ρ]和速度选择串[，，…，，…，u]表示，其中，串长均为=∑h。

调度串中，θ∈{1，2，…，}，1 ≤r≤h，二元组(θ，r)对应工序o，这样整个串对应一个有序工序表[o，o，…，o，…，o]。机器分配串中，ρ∈S表示用于加工工序o的机器。第三个串中，u为ρ加工o时的速度。能耗子问题的解码方法为优先使用能耗低的机器加工，优先安排能耗低的工序加工。

2.2 生成初始种群与模因组构建

提出一种多学习对象蛙跳算法，其模因组构建方法如下：在初始种群随机产生后开始进行种群划分，确定模因组的个数及模因组内解的个数，=×。对种群中的解进行排序，根据其值，找到最好的个解，第一的解分配到模因组，第二的解分配到模因组，依次进行直到序列第的解分配到模因组，最后，采用二元锦标赛，选择将剩余解依次分配到各模因组内：随机选择两个解x和x，如果x优于x，那么x将分配到模因组，如果两个解彼此非劣，则随机选择其中一个分配到模因组，另外一个解回到种群，重复执行上述步骤，直至所有解分配完毕。

2.3 局部搜索策略

通常，模因组内的搜索过程为首先利用模因组内最好解x和模因组内最差解x产生一个新解x，如果x优于x，则替换最差解x；否则，利用种群内的最好解x和x产生新解x，若x优于x，则替换最差解x；否则，随机产生一个解替换x，重复上述步骤，直到达到设定的迭代次数。

上述方法中，优化对象学习的对象比较单一，通常为模因组内最好解或种群内的最好解。本文提出一种新的学习对象的选择方法，具体过程如下。

（1）=1。

（2）=1。

（3）确定模因组内的最差解x，每隔10 次更换x的学习对象，记为，优于x或与x彼此非劣。

（4）对和x执行全局搜索，产生新解x，产生随机数。如果＜0.5，利用两个解的调度串交叉产生新解；如果0.5 ≤＜0.7，则执行机器分配串的交叉操作；如果≥0.7，则通过速度选择串交叉获得新解。如果x满足替换条件，则用x替代x，更新外部档案Ω并转到（7）。

（5）从外部档案Ω 中随机选择一个解≠x，对∈Ω 和x执行全局搜索，产生随机数，如果＜0.7，则对与x的调度串进行交叉，否则，对两个解的机器分配串执行交叉。否则，直接对x的速度选择串执行，产生新解x，如果x达到替换要求，则用x替代x，更新外部档案并转到（7）。

（6）产生新解x∈N()，ρ= ρ+1，若ρ=4，则令ρ=1。若x符合替换条件，则用x替代x，并更新外部档案Ω。

（7）=+1，如果≤，则转到（3）。

（8）=+1，如果≤，则转到（2）。当x支配或者两者彼此非劣时，称x满足替换条件。

3 实验结果

为了验证MLO-SFLA的性能，采用相关文献中的算例，这些算例在Microsoft Visual Studio C++2019编程实现，并运行在12.0G RAM 2.50GHz CPU的PC机上。

机器在加工状态下单位时间瞬时能耗为E∈[2，4]；空闲状态下，单位时间瞬时能耗为E=1。加工机器有5 种速度可供选择 ：={1.00，1.25，1.45，1.80，2.00}。

采用PSO 及变邻域搜索（variable neighborhood search，VNS）作为对比算法。MLO-SFLA 参数设置为=60，=6，最大迭代次数为10；PSO 的加速参数=2，=2，惯性因子=1.2，n=200，=100，最大迭代次数为10；VNS中=350，最大迭代次数为10。

评价指标用来衡量算法所产生的解集Ω所提供的非劣解在整个参考集Ω中所占的比例。显然，越大，说明算法的综合性能越好。

表3记录了3种算法关于指标的运算结果。表3表明，关于指标，MLO-SFLA 有17 个实例结果占优，远远优于PSO 及VNS 运算得到的结果，表明MLO-SFLA 产生了更多的优质可行解，增加了解决方案的多样性。图3、图4反映了3种算法关于两种实例的解的分布图。从图中也可以直观反映出MLO-SFLA产生的解要优于PSO 及VNS，证明MLO-SFLA 在求解FJSP-PE的优越性。

表3 MLO-SFLA、PSO、VNS 关于指标ρ的运算结果

图3 实例MK01 关于3 种算法的解的分布图

图4 实例MK05 关于3 种算法的解的分布图

4 结语

本文在简要介绍光伏辅助供能FJSP的原理之后，建立了该问题的数学模型；而后，从生成初始种群、模因组的构建、局部搜索策略等方面详细描述了MLO-SFLA；最后，通过大量的实例验证对比MLO-SFLA 和PSO、VNS的优化性能，最终的实验结果和分析表明，MLO-SFLA 对所研究的问题具有良好的优化能力。