Dual-enhanced Memetic Algorithm for Multi-task Scheduling in Sustainable Production
-
摘要: 从经济、环境和社会3个维度, 全面提升生产调度方案的可持续性具有重要意义. 针对并行机生产场景, 建立考虑机器指派、加工顺序、人员安排以及开关机控制等4种决策任务的调度模型. 为实现对复杂决策空间的高效寻优, 提出一种融合两种局部优化策略的双重增强模因算法(Dual-enhanced memetic algorithm, DMA)求解模型. 从随机更新角度, 针对不同决策任务, 构造单步变邻域搜索(One-step variable neighborhood search, 1S-VNS)策略. 从定向优化角度, 分析目标和关键任务之间的匹配关系, 提出一种可持续目标导向策略(Sustainable goals-oriented strategy, SGS). 考虑到两种优化策略的不同特点, 单步变邻域搜索策略作用于整个种群, 目标导向策略强化种群中的精英个体, 实现对输出解集的双重优化. 仿真实验结果表明, 双重优化策略能有效地增强算法性能, 并且所提算法在非支配解的多样性和收敛性上具有优越性.Abstract: It is of great significance to comprehensively enhance the sustainability of production scheduling with economic, environmental and social demand. A scheduling model for parallel machine production is established with consideration of four decision tasks: Machine assignment, processing sequence, personnel arrangement, and on/off machine control. To solve this complex problem, a dual-enhanced memetic algorithm (DMA) that integrates two local optimization strategies is proposed. In a random manner, a one-step variable neighborhood search (1S-VNS) suitable for decision-making tasks is designed. For targeted optimization, a sustainable goals-oriented strategy (SGS) is constructed after analyzing the matching relationship between objectives and key tasks. Based on the different characteristics of the two optimization strategies, the 1S-VNS acts on the entire population, and the SGS strengthens the elite individuals, achieving dual optimization of the output solution set. The simulation experimental results show that the dual optimization strategies effectively enhance the algorithm performance, and the proposed DMA has superiority in diversity and convergence of non-dominated solutions.
-
可持续生产调度 (Sustainable production scheduling) 是顺应当下制造业绿色与可持续发展需求的新兴研究课题[1-2]. 相比于以优化经济维度为核心的传统调度, 可持续生产调度在此基础上, 从调度目标或者约束角度扩充环境维度 (高能效、低碳排放等) 和社会维度 (工作公平、人员安全等) 的可持续制造指标[3-5], 从而有效地兼顾制造业的正面绩效和负面影响, 有利于企业的长远发展.
依据考虑的可持续维度, 可持续生产调度研究可以细分为: 1) 高能效调度 (Energy-efficient scheduling), 旨在通过制造调度实现能源效率最大化, 由此得到的调度方案既降低能耗又兼顾生产性能[6-9]; 2) 低碳调度 (Low carbon scheduling), 指的是通过制造调度优化生产性能, 同时降低制造过程中的碳排放量[10-12]; 3) 考虑需求响应策略的调度 (Scheduling with demand response strategies), 是在调度过程中考虑供电方制定的策略, 从而在保证生产性能的基础上优化电力消耗[13-14]. 在综述文献方面, Giret等在文献[15]的基础上, 整理经济、环境以及社会3个维度的可持续制造性能指标, 并从制造车间、目标系统、模型类型、目标函数、约束条件以及求解方法这6个角度进行整理和归纳[3]. 结合已有综述和细分领域的研究现状来看, 目前成果在优化目标或者约束上有各自的侧重和不同, 但关注的可持续性指标大多局限于经济和环境两个维度, 对社会维度关注较少. 随着制造业用工合理和工人安全等社会性问题频发, 全面考虑经济−环境−社会三维可持续性的调度研究有待深入开展.
随着指标维度的拓宽, 可持续生产调度的任务也由传统生产任务 (投料、工件排序与机器指派) 向机器控制与人员安排等相关任务泛化. 环境维度上, 引入包括调整机器加工速度[16-17]和选择机器开关机[18-19]的机器控制任务, 进一步降低能源消耗. 社会维度上, 工人是重要的考量因素, 保证其工作负荷的公平是实现生产可持续性的必然要求[20]. 为满足不同维度可持续指标的优化需求, 调度决策过程中必将面临多种不同类型的调度任务. 因此, 研究多类型任务的调度优化对提高制造企业生产方案的全方位可持续性有着重要的意义. 针对制造生产中经典的并行机场景, 本文将优化来自3个维度的可持续目标, 因而调度决策时包含机器指派、工件排序、工人安排以及机器开关机控制在内的4种任务.
本文研究多维度目标和多类型任务的调度问题, 相应的调度模型必然具有多目标优化和多决策变量的特点. 算法在求解模型时, 搜索空间的范围大且结构复杂. 在这样的搜索空间中, 算法往往极易陷入局部最优解, 因此提高局部寻优能力是求解本文问题的研究重点. 模因算法 (Memetic algorithm, MA) 是一类针对复杂优化问题的元启发式方法, 在平衡全局探索和局部开发上具有良好的性能[21-22]. 该算法使用交叉和变异等全局搜索算子, 同时引入局部搜索技术增强其局部搜索能力. 近年来有学者开始将其用于求解可持续调度问题, Geng等[23]针对考量工人安排的柔性流水车间调度问题, 提出一种多目标模因算法优化最大完工时间、拖期时间以及工人负荷差异. Zhu等[24]研究具有工人学习因子的低碳柔性作业车间调度问题, 设计一种包含遗传算法和变邻域搜索的模因算法. Wu等[16]提出一种多目标的模因差分进化算法, 同时优化最大完工时间和总能耗这两个目标. Zhang等[25]针对考虑机器速度可调的高能效调度问题, 在遗传算法的基础上, 设计两种优化策略以分别优化拖期时间和总能耗.
在上述基于模因算法的求解方法中, 全局搜索基本是基于交叉和变异的遗传算子, 而局部搜索主要分为以下两类: 1) 基于跳变的随机搜索策略, 即将当前的候选解作为起点, 在该点附近的邻域内, 以迭代的方式随机生成新解[24]. 这种方式往往是基于变邻域搜索、模拟退火等已有算法, 设计简便但参数调整困难. 2) 基于问题结构的特定策略, 这是针对具体问题而设计的定向优化方法[16, 23, 25], 通过分析问题的优化需求, 构建针对性的启发式策略, 设计难度相对较高. 已有研究在构建模因算法时, 大多仅利用单一类型的策略, 鲜有结合两种策略的研究工作. 对于复杂的可持续调度优化问题, 这两种局部搜索策略各有优势, 如何将两者有效地结合起来以实现双重优化, 是一种值得探索的研究思路.
本文针对多类型任务的可持续并行机调度问题, 提出一种融合两种局部优化策略的双重增强模因算法 (Dual-enhanced memetic algorithm, DMA). 考虑多决策变量, 构造单步变邻域搜索 (One-step variable neighborhood search, 1S-VNS). 考虑多目标优化, 设计分步优化的可持续目标导向策略 (Sustainable goals-oriented strategy, SGS). 最后, 实验对所提双重模因算法在求解本文问题上的有效性和优越性开展验证和分析.
1. 问题描述和建模
带多类型任务的不相关并行机三维可持续制造调度问题可以描述为: 车间里有N个独立工件$( i= 1,\;2,\;\cdots,\;N) $和M台不相关并行机$ (j=1,\;2, \;\cdots, M )$, 由K个工人$ (v=1,\;2,\;\cdots,\;K )$负责操作机器加工工件. 问题的实际背景可参见车辆装配生产过程[20, 26], 在组装车辆外部构件时, 要求工人操作机器完成上料、组装以及下料等工作. 出于生产效率的考虑, 工人数量往往不大于投入使用的机器数量. 因而, 对于某个工件来说, 会出现机器可用而工人不可用 (正在加工其他工件) 的情况. 此外, 这里假设机器允许出于节能考虑而出现开关机情况[18]. 调度问题的任务类型包含4类: 1) 为机器指派所加工的工件; 2) 为各个机器上的工件排序; 3) 为工人安排所负责的工件; 4) 控制处于非加工状态的机器进入待机或者关机.
研究的调度目标涵盖了可持续制造指标体系的全部维度: 1) 在经济维度上, 考虑最小化最大完工时间$ C_{\rm{max}} $; 2) 在环境维度上, 最小化加工过程中的总能耗$ E_{\rm{all}} $, 包括加工能耗$ E_{\rm{p}} $和非加工能耗$ E_{\rm{np}} $; 3) 在社会维度上, 最小化工人之间工作负荷的不平衡度W [20].
决策变量的定义如下: $ x_{ijlv} $为决策变量, 工件i在机器j上的第l个位置由工人v操作时$ x_{ijlv}= 1 $; 否则, $ x_{ijlv}=0 $. 该决策变量对应工件排序、机器指派以及工人安排这3个调度任务. $ y_{\rm{mac}} $ 是辅助变量, 用来指代机器开关机的决策条件, 假如机器待机能耗比关机能耗低, 则$ y_{\rm{mac}}=1 $; 否则, $ y_{\rm{mac}}=0 $.
基于上述的问题定义和描述, 带多类型任务的不相关并行机三维可持续制造调度问题的三元命名是$ R|x_{ijlv},y_{\rm{mac}}|C_{\rm{max}},E_{\rm{all}},W, $相应的数学模型如下所示.
目标函数为
$$ \begin{equation} {\rm{min}}\ Z = [C_{\rm{max}},E_{\rm{all}},W] \end{equation} $$ (1) $$ \begin{equation} C_{\rm{max}} = \mathop{{\mathrm{max}}}\limits_{1 \leq j \leq M}\ C_{{j}} \end{equation} $$ (2) $$ \begin{equation} E_{\rm{all}} = E_{\rm{p}} + \sum\limits_{j=1}^M\sum\limits_{l=1}^{N-1}{E_{\rm{np}}^{{j,l}}} \end{equation} $$ (3) $$ \begin{equation} E_{\rm{np}}^{{j,l}} = \begin{cases} p_{{j}}^{\rm{idle}} \times (s_{{j,l+1}} - c_{{j,l}}), & y_{\rm{mac}} = 1\\ H_{\rm{turn}}^{{j}}, & y_{\rm{mac}} = 0 \end{cases} \end{equation} $$ (4) 其中, $p^{\mathrm{idle}}_j $代表机器$j $的单位空闲能耗, $ H^j_{\mathrm{turn}} $代表机器$j $开关机能耗.
$$ \begin{equation} E_{\rm{p}} = \sum\limits_{i=1}^N\sum\limits_{j=1}^M\sum\limits_{l=1}^N\sum\limits_{v=1}^K{p_{{ijv}}^{\rm{prc}}} \times {t_{{ijv}}} \times {x_{{ijlv}}} \end{equation} $$ (5) $$ \begin{equation} W = \sqrt{\sum\limits_{v=1}^K(b_{{v}} - b_{\rm{max}})^2} \end{equation} $$ (6) $$ \begin{equation} b_{{v}} = \sum\limits_{i=1}^N\sum\limits_{j=1}^M\sum\limits_{l=1}^N{t_{{ijv}} \times x_{{ijlv}}} \end{equation} $$ (7) 约束条件为
$$ \begin{equation} \sum\limits_{j=1}^M\sum\limits_{l=1}^N\sum\limits_{v=1}^K{x_{{ijlv}} = 1}, \qquad i = 1,2,\cdots,N \end{equation} $$ (8) $$ \begin{equation} \sum\limits_{i=1}^N\sum\limits_{j=1}^M\sum\limits_{v=1}^K{x_{{ijlv}} \leq 1},\qquad l = 1,2,\cdots,N \end{equation} $$ (9) $$ \begin{equation} b_{\rm{max}} = \mathop{{\mathrm{max}}}\limits_{1 \leq v \leq K}\ b_{{v}} \end{equation} $$ (10) $$ \begin{split} & c_{{j,l}} \geq s_{{j,l}} + \sum\limits_{i=1}^N\sum\limits_{v=1}^K{t_{{ijv}} \times x_{{ijlv}}}, \\ & \qquad j = 1,2,\cdots,M, \qquad l = 1,2,\cdots,N \end{split} $$ (11) $$ \begin{equation} s_{{j,l+1}} \geq c_{{j,l}},\;\; j = 1,2,\cdots,M,\;\; l = 1,2,\cdots,N \end{equation} $$ (12) $$ \begin{equation} \begin{split} x_{{ijlv}} \in\;& \{0,1\},\;\;i=1,2,\cdots,N, \;\;j = 1,2,\cdots,M,\\ &l = 1,2,\cdots,N,\;\; v = 1,2,\cdots,K \\[-5pt]\end{split} \end{equation} $$ (13) 在目标函数中, 式(1)表明优化的是3个不同维度的调度目标, 各个调度目标的具体计算方式如式(2) ~ (7)所示. 在约束条件中, 式(8)表示任何一个工件只能被安排到一台机器上的一个位置并且由一个工人进行加工; 式(9)约束了机器每个位置上最多加工一个工件; 式(10)明确了最大工作负荷的计算方式; 式(11)表示在机器j的l位置上工件的结束时间$ c_{{j,l}} $的计算方式; 式(12)表示在机器j的$ l+1 $位置上工件的开始时间$ s_{{j,l+1}} $的计算方式; 式(13)表示决策变量$ x_{{ijlv}} $是0-1变量.
相比于文献[27]中经典的并行机调度模型, 本文研究的调度模型呈现以下特点: 1) 调度目标上, 本文同时优化3个可持续目标$ C_{\rm{max}} $、$ E_{\rm{all}} $和$ W, $ 其中$ C_{\rm{max}} $和$ W $属于时间量纲, $ E_{\rm{all}} $属于能耗量纲, 因此本文目标数量更多且量纲不一致. 2) 决策变量上, 本文不仅考虑传统的机器指派和工件排序, 而且拓展了工人安排和机器控制两种任务. 因此, 决策变量$ x_{{ijlv}} $的数量$( M \times N \times K) $远大于传统调度模型$ (M \times N )$. 3) 约束条件上, 随着目标和决策变量的复杂化, 约束条件的数量$ (2 \times N+1+ 2 \;\times M \times N+M \times N \times K) $也明显更多.
鉴于调度模型的复杂度, 本文基于模因算法框架, 从目标优化需求和决策变量特点两个角度入手设计双重局部优化策略, 进而提出一种融合两种策略优势的双重增强模因算法.
2. 双重局部优化策略
2.1 任务对应的个体编码
编码是将问题的解空间转变为算法寻优的个体, 因此编码方法与调度问题的决策任务直接相关. 为匹配个体与$ R|x_{{ijlv}},y_{\rm{mac}}|C_{\rm{max}},E_{\rm{all}},W $问题的调度方案, 下面针对问题中的4类调度任务设计编码方式. 考虑到机器开关机的选择需要以其他三类任务的确定为前提, 因此采取三段式编码方式将算法个体与调度问题中的机器指派、工人安排以及工件排序三类任务相对应. 图1给出了一个三段式个体的示例说明, 针对的是5个工件在3台机器上由2个工人加工的案例. 在图1的个体中, $ \alpha $段表示各个工件的加工顺序, $ \beta $段表示各个工件的机器指派, $ \gamma $段则代表了各个工件的工人安排. 基于三段式编码形式, 以随机的方式形成初始种群.
2.2 单步变邻域随机搜索策略
变邻域搜索是围绕单个解的邻域展开迭代搜索, 其关键在于设计合适的邻域动作, 以达到产生更优个体的效果[28]. 针对第2.1节中三段式个体, 每段代表不同的任务, 因此需要为各段设计相应的邻域动作. 可选的邻域动作包括插入、突变和交换等方式[29-34]. 本文借鉴已有方法的经验, 并通过多次试验, 设计了如下4种邻域动作:
1) 对机器指派$ \beta $段, 随机改变一个工件的机器指派, 以$ N_1 $指代该邻域动作;
2) 对工人安排$ \gamma $段, 随机改变一个工件的工人安排, 以$ N_2 $指代该邻域动作;
3) 对加工顺序$ \alpha $段和机器指派$ \beta $段做组合动作, 对$ \alpha $段以插入的方式改变, 同时以方式$ N_1 $改变$ \beta $段, 以$ N_3 $指代该邻域动作;
4) 对加工顺序$ \alpha $段和工人安排$ \gamma $段做组合动作, 对$ \alpha $段以插入的方式改变, 同时以方式$ N_2 $改变$ \gamma $段, 以$ N_4 $指代该邻域动作.
传统的变邻域搜索算法往往需要进行多次迭代, 迭代是以计算时间换取解质量的方式. 在模因算法的框架中, 每一次全局寻优后, 都会运行多次局部迭代. 假设全局寻优次数是num_global, 局部迭代次数是num_local, 那么算法总的迭代次数将是$ num\_global \times num\_local $. 如此大量的迭代次数, 必然造成算法整体的搜索效率不高. 另一方面, 鉴于本文将融合两种局部优化策略, 无需展开过多的随机搜索. 因此, 以单步的方式运作变邻域随机搜索策略, 其更新单个个体的作用流程如算法1所示.
算法1. 单步变邻域随机搜索策略
输入. 个体$ \pi $
输出. 新个体$ \pi $
1: $ h \leftarrow 0 $
2: while $ h \leq 4 $ do
3: $ \pi' \leftarrow$将邻域动作 $N_{{h}} $ 作用于 $\pi $
4: if $ \pi' $ 支配 $ \pi $ then
5: $ \pi \leftarrow \pi' $
6: end if
7: $ h \leftarrow h+1 $
8: end while
2.3 可持续目标导向优化策略
基于单步变邻域随机搜索策略有助于产生新个体, 但随机性使其优化效果难以得到保障. 通过探索问题的特征来构建的优化策略, 往往能够直接有效地改善解质量, 并且时间复杂度也较低[16, 25]. 因此, 本文将针对带多类型任务的可持续调度问题, 分析各个维度目标与不同调度任务之间对应关系, 进而设计针对性的优化策略. 然后, 考虑到不同目标之间的冲突耦合关系, 构建了分步作用方式以逐步优化不同维度的目标.
2.3.1 社会维度目标导向的优化策略
研究问题中的社会维度目标, 是降低工人工作负荷差异度W, 这可以通过减小各个工人工作负荷$ b_{{v}} $与最大工作负荷$ b_{\rm{max}} $之间的差值(式(6))实现. 在所有差值中, 工作负荷最小值$ b_{\rm{min}} $与工作负荷最大值$ b_{\rm{max}} $的差值$ \Delta b $是最大的, 因而降低$ \Delta b $对于优化W而言是最为直接且简便的. 鉴于此, 下面针对$ \Delta b $开展优化策略的设计.
在$R|x_{{ijlv}},y_{\rm{mac}}|C_{\rm{max}},E_{\rm{all}},W$问题中, 调整工人安排即改变工人负责的工件, 可以有效改变$ \Delta b $. 假设目前具有$ b_{\rm{max}} $和$ b_{\rm{min}} $的两位工人分别是$ v $和$ v' $, 社会维度目标导向的优化策略核心是从工人$ v $负责的工件集$ J_{\rm{mv}} $中挑选合适的工件转变为$ v' $负责加工, 以此来减小$ b_{\rm{max}} $同时增大$ b_{\rm{min}} $. 在这样的调整方式下, 其余工人的工作负荷并不会发生改变. 在不造成新$ b_{\rm{min}} $大于原$ b_{\rm{max}} $的情况下, 其余工人与$ b_{\rm{max}} $之间的负荷差异也会随着$ b_{\rm{max}}$的减小而下降, 结果是整体的W值得到优化. 该优化策略是在不改变加工顺序和机器指派的情况下, 通过调整工人安排以优化社会维度目标, 具体步骤如算法2所示.
算法2. 社会维度目标导向的优化策略
输入. 个体$ \pi $
输出. 新个体$ \pi $
1: $ \Delta b = b_{\rm{max}} - b_{\rm{min}}\; {\%} $最大负荷差异
2: $ t \leftarrow $具有最大负荷$ b_{\rm{max}} $的工人$ v $, 其在机器指派$ M_{\rm{mv}} $上负责工件$ J_{\rm{mv}} $的加工时间矩阵$ t $
3: $ t' \leftarrow $具有最小负荷$ b_{\rm{min}} $的工人$ v' $, 其在机器指派$ M_{\rm{mv}} $上负责工件$ J_{\rm{mv}} $的加工时间矩阵$ t' $
4: for $ i = 1 \ {\mathrm{to}} \ |J_{\rm{mv}}| $ do
5: $\Delta b' = {\mathrm{abs}}(b_{\rm{max}} -$ $ t_i \;- \;b_{\rm{min}}\; -\; t_i') $ $ =\; {\mathrm{abs}}(\Delta b\; - $ $ (t_i + t_i')) $
6: if $ \Delta b' < \Delta b \ {\mathrm{and}} \ (b_{\rm{min}} + t_i') < b_{\rm{max}} $ then
7: $ \pi \leftarrow $将原个体$ \pi $负责工件$ i $的工人调整为$ v' $
8: break
9: end if
10: end for
为了进一步说明社会维度目标导向优化策略的特点, 图2基于附录A中的案例数据给出了该策略的作用效果. 在未作用的调度方案(图2(a))中, 两个工人的负荷分别是$ b_1 = 16 $、$ b_2 = 4 $, 此时的社会维度指标$ W $的值是12. 将所提优化策略作用于此调度方案: 首先, $ b_{\rm{max}} $和$ b_{\rm{min}} $分别对应$ b_1 $和$ b_2 $, 两者之间的差异$ \Delta b = 12 $. 接着, 统计负荷是$ b_{\rm{max}} $的工人$ W1 $所负责的工件集合$ J_{\rm{mv}} $及其加工时间:$ J1(3) $, $ J2(4) $, $ J3(3) $, $ J4(6) $. 在不改变机器指派的情况下, 由工人$ W2 $负责$ J_{\rm{mv}} $, 那么各个工件的加工时间是: $ J1(6) $, $ J2(2) $, $ J3(3) $, $ J4(2) $. 按照设计步骤, 针对$ J_{\rm{mv}} $中的每个工件计算$ \Delta b' $, 即尝试替换工人安排. 可以发现, 当$ J1 $替换为 $ W2 $负责后, $ \Delta b' = 3 $. 依据替换条件, 加工$ J1 $的工人由$ W1 $调整为$ W2 $, 由此形成了新调度方案(图2(b)). 此时$ b_1 = 13 $, $ b_2 = 10 $, 目标值$ W $的值是3. 对比图2(a)和图2(b)两种调度方案, 社会维度目标$ W $由12降低为3, 因此设计的优化策略改善了社会维度目标.
图 2 社会维度目标导向的优化策略作用效果说明图Fig. 2 Explanation of the effectiveness of optimization strategy guided by social dimension goal2.3.2 经济维度目标导向的优化策略
研究问题中的经济维度目标, 是降低最大完工时间$ C_{\rm{max}} $(式(2)). 针对具有最大完工时间的机器, 其消耗的时间主要由必要加工时间和空闲时间两个部分组成, 其中空闲时间是无效的非必要时间. 本节通过调整工件之间的加工顺序减少空闲时间, 以优化该机器上所有工件的完工时间. 为此, 经济维度目标导向优化策略的核心思路是, 将完工时间靠后的工件提前至空闲时间段进行加工. 因此, 该策略调整的是工件的加工顺序, 而不改变机器指派和工人安排, 其具体的优化步骤如算法3所示.
算法3. 经济维度目标导向的优化策略
输入. 个体$ \pi $
输出. 新个体$ \pi $
1: $ M_{\rm{mc}} \leftarrow $个体$ \pi $中具有最大完工时间的机器
2: for $ l = 1 \ {\mathrm{to}} \ |M_{\rm{mc}}| $ do
3: $t_{{i}} \leftarrow$获取该机器$ l $上最后一个工件$ i $的加工时间$t_{{i}}$
4: $ J_{\rm{mc}} \leftarrow $获取在机器$ l $上加工的其他工件集合$ J_{\rm{mc}} $
5: for $ j = 1 \ {\mathrm{to}} \ |J_{\rm{mc}}| $ do
6: if 当前工件$ j $是机器$ l $上的第1个工件 then
7: if $t_{{i}}$小于工件$ j $的开工时间 then
8: $ \pi \leftarrow $在原个体$ \pi $上将工件$ i $安排为机器$ l $上的第1个工件
9: break
10: end if
11: else
12: if 该工件$ j $与工件$j-1 $之间的空闲时间可以插入工件$ i $ then
13: $\pi \leftarrow$在原个体$ \pi $上将工件$ i $安排至工件$ j $与工件$j- 1$之间进行加工
14: break
15: end if
16: end if
17: end for
18: end for
为了进一步说明经济维度目标导向优化策略的效果, 图3同样基于附录A数据给出了优化策略作用前后的效果对比. 作用前, 调度方案(图3(a))的经济维度指标$ C_{\rm{max}} = 21 $. 将优化策略应用于该调度方案: 首先找到$ C_{\rm{max}} $对应的机器是$ M3 $, 其加工的工件集合$ J_{\rm{mc}} $包含了$ J3 $ 和$ J4 $. 接着, 尝试将$ J4 $的开始时间前移至$ J3 $之前以降低机器的完工时间. 由于此时$ J4 $的加工时间是6, 而$ J3 $的开工时间是12, 因而满足前移条件. 将$ J4 $提前至$ J3 $之前加工, 形成了新调度方案(图3(b)). 对比作用前后的两种调度方案, 经济维度目标$ C_{\rm{max}} $从21降低至了15, 因此设计的优化策略改善了经济维度目标.
图 3 经济维度目标导向的优化策略作用效果说明图Fig. 3 Explanation of the effectiveness of optimization strategy guided by economic dimension goal2.3.3 不同优化策略的分步作用方式
在第2.3.1节和第2.3.2节中, 考虑社会维度目标导向的优化策略, 也会影响其他两个维度的目标值. 对于经济维度目标导向的优化策略, 会同时影响经济维度目标以及环境维度目标, 但不会对社会维度目标造成影响. 假如策略作用顺序不当, 相互的优化效果就会出现冲突, 进而导致无效优化的情况. 为了避免不同策略的优化冲突, 有必要设计一种分步作用方式.
第1步是运作社会维度目标导向的优化策略, 第2步是运作经济维度目标导向的优化策略. 在经济维度目标导向设计的作用后, 针对空闲时间段以调度机器控制任务的方式优化环境维度目标值 (控制机器处于待机或关机的任务), 并将其作为分步作用方式的第3步. 这样的分步作用方式使得三个维度目标依次得到针对性的调整, 并且保证了后一步的优化策略不会破坏上一步的优化结果, 不同优化策略分步作用方式的具体步骤如算法4 所示.
算法4. 不同优化策略的分步作用方式
输入. 个体$ \pi $
输出. 新个体$ \pi $
1: $ \pi_{\rm{1}} \leftarrow $依据算法2中的优化策略, 将社会维度目标导向的设计作用于个体$ \pi $
2: $ \pi_{\rm{2}} \leftarrow $依据算法3中的优化策略, 将经济维度目标导向的设计作用于个体$ \pi_{\rm{1}} $
3: $ \pi_{\rm{3}} \leftarrow $针对个体$ \pi_{\rm{2}} $, 以开关机的方式减少空闲能耗以优化环境维度目标
4: if $ \pi_3 $支配$ \pi $ then
5: $ \pi \leftarrow \pi_3 $
6: end if
3. 双重增强模因算法
在模因算法框架中, 寻优过程由全局搜索算子和局部搜索策略两个部分完成. 针对本文问题, 全局搜索算子仍延续传统交叉和变异的设计思路, 对应上文个体做了相应的设计. 针对多目标和多任务带来的局部寻优困境, 提出了随机跳变和定向优化双重优化策略. 并且, 依据不同策略的各自特点, 将两种策略作用于不同个体的更新, 以融合各自的优势.
3.1 全局搜索算子
对应第2.1节中三段式个体, 这里设计分段作用的全局搜索算子, 以充分地更新每一段上的基因. 依据各个个体支配等级, 采取轮盘赌的方式挑选出$ PS \times 0.8 $个个体作为全局搜索算子的作用对象.
针对具有三段结构的个体, 分段作用的全局搜索算子包括了交叉算子和变异算子, 具体设计是: 对于代表加工顺序的$ \alpha $段, 交叉操作以顺序交叉 (Ordered crossover) 的方式进行, 变异操作以交换 (Swap) 的方式进行; 对于表示机器指派的$ \beta $段, 交叉操作以均匀交叉 (Uniform crossover) 的方式进行, 变异操作则以单点 (Single point) 的方式进行突变; 最后对于代表工人安排的$ \gamma $段, 交叉操作也采取均匀交叉, 变异操作以单点突变.
考虑到本文问题中的多目标优化, 采用了NSGA-II中的非支配解排序和拥挤度计算等方法[20], 可参考相关文献, 这里不再赘述.
3.2 双重增强模因算法的主流程
基于上述设计, 所提算法 (DMA) 求解$ R|x_{{ijlv}}, y_{\rm{mac}}|C_{\rm{max}},E_{\rm{all}},W $问题的主流程如下:
步骤 1. 初始化种群$ P_{\rm{G}} $, 精英集合$ P_{\rm{E}} $, 令迭代次数$i = 0$.
步骤 2. 初始化精英集合, 精英集合是由每代中对应非支配解的个体所构成, $ P_{\rm{E}} = P_{\rm{G}} \times 20\% $. 当精英集合超过限定大小时, 按照拥挤度挑选新的精英集合.
步骤 3. 判断是否终止迭代, 如果达到终止条件, 则算法终止并输出非支配解; 否则, 令$i = i +1$.
步骤 4. 针对种群$ P_{\rm{G}} $, 以第3.1节中的全局搜索算子, 形成新种群$ P_{\rm{G}}' $.
步骤 5. 对于$ P_{\rm{G}}' $, 以第2.2节中的单步变邻域随机搜索策略, 形成种群$ P_{\rm{G}}'' $.
步骤 6. 针对精英集合$ P_{\rm{E}} $, 以第2.3节中的可持续目标导向优化策略更新精英集合中的个体, 得到新精英集合$ P_{\rm{E}}' $.
步骤 7. 结合$ P_{\rm{G}}'' $和$ P_{\rm{E}}' $, 更新种群$ P_{\rm{G}} $和精英集合$ P_{\rm{E}} $. 返回步骤3.
从上述步骤中看出, 双重优化策略的融合方法是: 首先, 将单步变邻域随机搜索作用于种群中的所有个体; 接着, 可持续目标导向策略进一步更新精英集合中的个体. 之所以将可持续导向策略独立作用于精英个体而非参与到所有个体的更新过程, 主要是为了避免算法过早陷入局部最优解. 假如将单步变邻域随机搜索策略和定向优化策略同时作用于种群, 那么种群会早早地出现较多优质个体. 在这些个体的引导下, 算法会因为缺乏个体多样性而过早收敛. 其次是, 相比所有个体参与优化策略, 仅部分个体参与消耗的计算时间更少. 综上, 所提DMA在全局搜索算子的基础上, 有效地融合两种局部搜索策略, 以期达到兼顾全局探索和局部开发的寻优效果.
4. 实验验证
为了验证双重增强模因算法 (DMA) 在求解多目标和多任务的$ R|x_{{ijlv}},y_{\rm{mac}}|C_{\rm{max}},E_{\rm{all}},W $问题上的有效性和优势, 接下来开展多组对比实验和分析讨论. 所有测试实验均采用MATLAB 2016b编程实现, 在8.0 GB的RAM、2.30 GHz的CPU环境下运行.
实验案例来源于Costa等[26]的研究工作, 文献[26]在不相关并行机调度问题中考虑了人员安排, 构建了相应的标准测试案例. 基于此, 本文从小规模和大规模案例中各选8种, 组成16种测试场景. 加工过程中的其余参数设置如下: 加工时间从均匀分布区间[2, 6]随机获取; 单位时间的加工能耗和空闲能耗分别从均匀分布区间[3, 8]和[1, 4]中随机获取; 机器的开关机所需的能耗和时间分别从均匀分布区间[1, 12]和[1, 3]中随机得到. 考虑到参数随机性, 本文在各个场景下构建了5个具有不同参数的案例, 形成的测试案例总数是$16 \times 5=80$个.
本文引入反转世代距离 (Inverted generational distance, IGD) 和非支配解占比两种性能指标, 对算法求解案例的结果做分析和对比. 反转世代距离是常用于比较多目标算法在收敛性和多样性上优劣的综合指标. 算法的IGD值越小, 则算法的性能越好. 对于某一类算法来说, 其IGD的计算方式为
$$ \begin{equation} IGD(A) = \frac{\sum\limits_{y^* \in F}{\mathop{\rm{min}}\limits_{y \in A}}{\ d(y^*,y)}}{|F|} \end{equation} $$ (14) 其中, A代表某一类算法; $ F $表示所有对比算法求解结果中的非支配解集, 即近似最优Pareto解集. $ F $的构造方式是将所有对比算法求解问题获得的解集合并, 然后以快速非支配排序的方式处理, 最终获得的非支配解集即为$ F $. $ |F| $代表$ F $中解的个数, $ d(y^*,y) $表示$ y^* $和$ y $两点之间的欧氏距离.
非支配解占比以$ R_{\rm{nd}} $表示, 是将算法所得的非支配解集与近似最优解集$ F $比较. 算法的$ R_{\rm{nd}} $值越大, 代表相应的算法越好, 其$ R_{\rm{nd}} $的计算方式为
$$ \begin{equation} R_{\rm{nd}}(A) = \frac{N_{\rm{nd}}(A)}{|F|} \end{equation} $$ (15) 其中, $ N_{\rm{nd}}(A) $表示算法所得非支配解同样也存在于$ F $中的数量.
为了保证比较的公平性, 所有对比算法的运行时间均相同, 即终止条件相同, 都是$ N \times M \times K \times 100 $ms. 此外, 所有实验中各个算法均独立重复运行10次后取平均结果, 以消除随机误差.
4.1 双重局部优化策略的提升作用
4.1.1 单步变邻域随机搜索策略的有效性
邻域动作是单步变邻域随机搜索策略 (1S-VNS) 能否发挥作用的关键, 因此通过对比不同邻域动作, 以验证本文所设计的方法是适用于问题的. 这里参与对比的邻域动作包括3种, 都是来源于第2.2节中的变种. 基于此, 具体用于对比分析的算法如下:
1) MOA: 代表解决问题的多目标优化算法, 即仅具有第3.1节中全局搜索算子;
2) MMA_1: 代表在MOA中加入第2.2节中邻域动作的第1变种;
3) MMA_2: 代表在MOA中加入第2.2节中邻域动作的第2变种;
4) MMA_3: 代表在MOA中加入第2.2节中邻域动作的第3变种;
5) MMA: 代表在MOA中加入第2.2节中邻域动作.
对比MMA与MOA, 可验证局部优化方法(1S-VNS)是否有效. 对比MMA与其余变种, 可验证所设计的邻域动作是否更为适用. 5种算法的初始种群大小均为100, 交叉和变异概率均分别设置为0.9和0.1. 基于此, 表1统计了各算法求解不同案例所得的平均性能值, 加粗形式表示占优的结果.
表 1 MMA与MOA、MMA_1、MMA_2、MMA_3的性能指标结果Table 1 Results for MMA, MOA, MMA_1, MMA_2 and MMA_3案例 $ IGD$ $R_{{\mathrm{nd}}} $ MOA MMA_1 MMA_2 MMA_3 MMA MOA MMA_1 MMA_2 MMA_3 MMA 7&4&2 0.79 0.66 0.63 0.39 0.24 0.10 0.39 0.55 0.70 0.87 7&5&3 0.79 0.65 0.58 0.86 0.33 0.13 0.39 0.47 0.42 0.72 8&4&2 0.97 0.53 0.52 0.50 0.36 0.00 0.41 0.43 0.46 0.71 8&5&3 0.74 0.63 0.53 0.57 0.47 0.00 0.14 0.40 0.35 0.61 9&4&2 0.87 0.71 0.69 0.63 0.39 0.13 0.08 0.19 0.31 0.71 9&5&3 0.64 0.57 0.63 0.59 0.35 0.00 0.19 0.11 0.32 0.75 10&4&2 0.97 0.69 0.66 0.78 0.41 0.00 0.13 0.33 0.23 0.70 10&5&3 0.70 0.67 0.55 0.59 0.44 0.00 0.07 0.38 0.29 0.67 20&10&6 0.69 0.64 0.67 0.69 0.43 0.07 0.23 0.14 0.09 0.66 20&10&8 0.67 0.82 0.80 0.73 0.36 0.15 0.02 0.11 0.13 0.70 20&12&8 0.68 0.77 0.47 0.75 0.49 0.50 0.10 0.63 0.23 0.62 20&12&10 0.48 0.90 0.53 0.72 0.40 0.68 0.08 0.58 0.12 0.68 40&10&6 0.85 0.94 0.64 0.90 0.32 0.10 0.00 0.29 0.00 0.71 40&10&8 0.92 0.91 0.62 0.65 0.31 0.05 0.08 0.28 0.12 0.78 40&12&8 0.86 0.69 0.74 0.85 0.39 0.09 0.17 0.11 0.10 0.69 40&12&10 0.77 0.78 0.71 0.81 0.43 0.14 0.13 0.17 0.12 0.67 从表1可知, MMA在所有的小规模场景(前8种)上占据优势. 无论是$ IGD $还是$ R_{\rm{nd}} $, MMA都比其他算法表现得更好, 这说明所设计的1S-VNS在算法求解小规模场景时具有提升作用. 对于大规模场景(后8种), MMA并没有在所有案例上都取得最好的结果. 尤其是20&12&10场景, MOA与MMA的性能指标结果十分相近, 这说明此时邻域搜索并没有起到改善算法性能的作用. 究其原因, 1S-VNS本质是随机寻优, 在计算时间限定时, 难以保证在大规模场景的复杂搜索空间中产生更优的个体. 需要说明的是, 表中的结果是多次测试后的平均值, 因此有可能会出现$ IGD $不同而$ R_{\rm{nd}} $相同的情况. 对于20&12&8场景, MMA虽然表现不如MMA_2, 但两者的性能差距较小. 综合16种场景, MMA在大多数(15种)结果上是具有求解优势的.
本文进一步采用方差分析法 (Analysis of variance, ANOVA), 对表1中的算法性能差异展开显著性检验. 以5种算法为控制变量, 将2种性能指标作为响应量, 检验结果如图4所示. 无论是指标$ IGD $还是$ R_{\rm{nd}} $, MMA与其他对比算法的置信区间都没有重合, 这表明MMA的算法优势是显著的. 综合16种案例的结果来看, 1S-VNS方法能够明显地提升算法性能, 尤其是对于小规模案例. 此外, MOA与MMA_1、MMA_3的置信区间存在重合, 表明这些算法之间的差异并不显著, 这说明不合适的邻域动作并不能有效改善算法求解结果. MMA_2虽然与MOA不存在明显重合, 但其性能远不如MMA. 因此, 相比其他3个变种, MMA中的邻域动作是最为适合本文问题的.
图 4 MMA与MOA、MMA_1、MMA_2、MMA_3性能指标的均值和95%置信区间Fig. 4 Mean and 95% confidence interval of performance indicators of MMA, MOA, MMA_1, MMA_2 and MMA_34.1.2 目标导向优化策略的有效性
对于可持续目标导向策略(SGS)有效性的验证, 本文从有无策略以及融合方式两个角度开展. 因此, 将所提DMA与以下2种算法进行对比:
1) MMA: 表示没有融合目标导向优化策略的多目标模因算法(同第4.1.1节);
2) MMA&SGS: 表示将SGS作用于多目标模因算法中所有个体的算法.
对比DMA和MMA, 可以验证SGS是否有提升算法性能的作用. 对比DMA和MMA&SGS, 能够分析SGS作用于个体和种群之间的效果差异. 3种算法中种群大小均为100, 交叉和变异概率都设置为0.9和0.1. DMA中的精英集合大小均设置为20. 表2统计了各个算法求解不同场景中案例所得的平均性能值, 加粗的字体表示占优的结果.
表 2 DMA与MMA、MMA&SGS的性能指标结果Table 2 Results for DMA, MMA and MMA&SGS案例 $ IGD$ $R_{{\mathrm{nd}}} $ MMA MMA&SGS DMA MMA MMA&SGS DMA 7&4&2 0.00 0.00 0.00 1.00 1.00 1.00 7&5&3 0.35 0.49 0.38 0.87 0.70 0.86 8&4&2 0.45 0.51 0.39 0.71 0.48 0.76 8&5&3 0.29 0.44 0.34 0.74 0.49 0.72 9&4&2 0.61 0.57 0.41 0.62 0.52 0.73 9&5&3 0.52 0.80 0.39 0.65 0.36 0.77 10&4&2 0.80 0.80 0.36 0.47 0.46 0.77 10&5&3 0.57 0.85 0.43 0.42 0.30 0.71 20&10&6 0.71 0.57 0.41 0.20 0.69 0.74 20&10&8 0.65 0.51 0.43 0.12 0.70 0.73 20&12&8 0.71 0.44 0.47 0.22 0.74 0.72 20&12&10 0.85 0.39 0.42 0.22 0.79 0.75 40&10&6 0.80 0.59 0.39 0.11 0.28 0.79 40&10&8 0.71 0.58 0.37 0.16 0.33 0.72 40&12&8 0.73 0.83 0.42 0.19 0.30 0.71 40&12&10 0.74 0.65 0.40 0.22 0.26 0.73 在表2的小规模场景 (前8种) 求解结果中, DMA在其中的5种场景占据优势, 而MMA在2种场景上表现最佳, 3个算法在最小规模场景下同时最优. 这一方面说明, 在精英个体上作用SGS, 对DMA在大多数小规模场景的求解性能的确具有提升效果. 另一方面, MMA求解结果占优表明, 随机局部搜索 (1S-VNS) 比定向优化 (SGS) 效果更好的作用场景是存在的. 可以理解的是, 小规模场景下的寻优个体简单, 算法寻优空间小, 1S-VNS通过邻域动作仍可以有效地搜索到更优个体. 并且, 由于无需在定向优化上花费计算时间, MMA相比DMA有更多的随机搜索次数. 综合搜索次数和单次寻优能力, 才使得MMA 在小规模案例上仍保持着一定的竞争力.
对于表2中大规模场景 (后8种) 的求解结果, 其中6种场景由DMA占优, 而剩余2种则是MMA&SGS更优, MMA在所有场景中都表现最差. 相比小规模场景的结果, 定向优化策略SGS起到了更加明显的作用. 因为随着场景规模变大, 寻优空间随之扩展, 随机搜索的盲目性更加明显, 而定向优化产生更优个体的概率更高. 此外, DMA 在更多场景下优于MMA&SGS, 这也说明将SGS作用于精英个体比作用于所有个体对提升性能更为合适. 主要原因是, 当SGS作用于所有个体, 就意味着定向优化将消耗更多的计算时间. 在限定运行时间的情况下, 寻优过程难以平衡全局寻优、随机搜索以及定向优化, 这导致MMA&SGS算法的整体搜索效率不高.
为了验证上述算法性能之间的差异是否具有统计意义, 接着利用ANOVA对表2中的实验结果进行差异性检验, 结果如图5所示. 可以看出, 在$ IGD $ 和$ R_{\rm{nd}} $上, DMA与其他两种算法的置信区间都没有重合, 这说明DMA 是显著地优于对比算法, 验证了作用于精英个体的SGS是可以显著提升算法性能的. 此外, MMA和MMA&SGS在两种性能指标上的差异都不显著, 这也侧面说明SGS作用于所有个体时不具有明显提升性能的作用.
图 5 DMA与MMA、MMA&SGS性能指标的均值和95%置信区间Fig. 5 Mean and 95% confidence interval of performance indicators of DMA, MAA and MMA&SGS4.2 与其他算法对比
鉴于鲜有与本文$ R|x_{{ijlv}},y_{\rm{mac}}|C_{\rm{max}},E_{\rm{all}},W $问题一样的研究工作, 这里从问题所属的可持续制造调度领域研究中选取了3种较为常见的求解方法, 并从应用角度做了针对性的变更. 通过对比现有技术, 以验证所提DMA在求解本文问题上的有效性. 对比算法的来源文献以及应用说明具体是:
1) V-NSGA-II: 来自Akbar等[20]提出的求解考虑人员安排的调度研究, 是一种基于经典NSGA-II的变种算法. 为了将其应用于本文问题, 采用第2.1节中的编码和初始化, 沿用了原文中的交叉和变异方式.
2) IABC: 来自Li等[35]的研究工作, 其在基本人工蜂群算法的基础上引入遗传算子, 求解考虑3种调度任务的多目标柔性作业车间调度问题, 获得了良好的性能结果. 在将其应用于本文问题时, 同样采用第2.1节中的编码和初始化, 沿用了原文中的更新方式.
3) MA: 选自文献[24]中的研究成果, 该模因算法是以变邻域搜索算法对局部范围展开搜索, 用于求解考虑人员的柔性作业车间低碳调度问题. 为了将该算法应用于本文问题, 这里采用第2.1节中的初始化以及第3.1节中的全局搜索算子, 沿用了文献[24]中的变邻域搜索算法.
DMA的参数设置同第4.1.2节, 4种算法的初始种群大小均为100, V-NSGA-II的交叉和变异概率与DMA相同, IABC中的精英集合大小也与DMA保持一致. MA中变邻域搜索算法的迭代次数设置为50. 基于上述设置, 表3统计了各个算法求解不同场景下案例所得的平均性能值, 加粗形式表示占优的结果.
表 3 DMA与V-NSGA-II、IABC、MA的性能指标结果Table 3 Results for DMA, V-NSGA-II, IABC and MA案例 $IGD$ $R_{{\mathrm{nd}}}$ V-NSGA-II IABC MA DMA V-NSGA-II IABC MA DMA 7&4&2 0.85 0.67 0.48 0.15 0.00 0.15 0.70 0.87 7&5&3 0.74 0.85 0.66 0.24 0.00 0.08 0.22 0.82 8&4&2 0.65 0.76 0.41 0.32 0.20 0.08 0.43 0.76 8&5&3 0.78 0.80 0.32 0.25 0.32 0.24 0.44 0.87 9&4&2 0.41 0.63 0.56 0.36 0.39 0.34 0.37 0.76 9&5&3 0.86 0.61 0.57 0.13 0.15 0.20 0.35 0.86 10&4&2 0.52 0.31 0.49 0.22 0.21 0.31 0.27 0.77 10&5&3 0.63 0.56 0.52 0.20 0.12 0.22 0.45 0.78 20&10&6 0.85 0.88 0.69 0.21 0.07 0.05 0.15 0.83 20&10&8 0.83 0.91 0.72 0.18 0.02 0.00 0.11 0.86 20&12&8 0.79 0.84 0.74 0.31 0.05 0.00 0.23 0.71 20&12&10 0.82 0.93 0.69 0.30 0.03 0.00 0.35 0.74 40&10&6 0.78 0.81 0.55 0.11 0.00 0.00 0.15 0.85 40&10&8 0.62 0.89 0.61 0.29 0.14 0.00 0.14 0.73 40&12&8 0.59 0.87 0.53 0.23 0.11 0.00 0.15 0.77 40&12&10 0.62 0.83 0.50 0.31 0.09 0.00 0.18 0.71 从表3可以看出, 无论是$ IGD $还是$ R_{\rm{nd}} $, DMA在所有场景的求解结果都是占据优势的, 这说明DMA求解本文问题的性能优于其他3种算法. 与MA相比, 虽然两种算法都同时具备了全局优化和邻域搜索, 但很明显DMA中的更新方式是针对本文问题设计的. 不仅如此, DMA还融合了可持续目标导向的定向优化策略, 因此求解性能更具优势. 此外, MA比IABC和V-NSGA-II表现更佳, 这也验证了模因求解框架在本文问题上比单一的全局优化更为合适. 值得说明的是, IABC和V-NSGA-II的更新方式仍是以沿用原文为主, 原文问题和本文问题上的较大差异会造成算法力有不逮, 尤其是在大规模场景上体现的较为明显.
对于算法求解性能差异的显著性, 图6展示了ANOVA方法对表3数据的检验结果. 可以看出, DMA与对比算法的置信区间在$ IGD $和$ R_{\rm{nd}} $上都不重合, 这表明DMA的求解性能是显著地优于其他算法. MA与V-NSGA-II、IABC 也没有性能值上的重合, 说明模因框架的优势也是较为显著的. 此外, V-NSGA-II和IABC在两种性能指标上的检验结果都有明显的重合, 这表明这两种算法在统计意义下具有相似的求解性能.
图 6 DMA与V-NSGA-II、IABC、MA性能指标的均值和95%置信区间Fig. 6 Mean and 95% confidence interval of performance indicators of DMA, V-NSGA-II, IABC and MA为了进一步可视化上述比较算法的求解性能, 图7绘制了4种算法求解大规模场景(40&10&6)所得的Pareto前沿. 图7(a)展示了含所有目标的总体情况, 其余子图是含部分目标. 在图7(b)和图7(c)中, 可以清楚地看到3种对比算法的解都被DMA的解所支配. 在图7(d)中, 虽然DMA所得解有少部分不如MA, 但仍明显优于IABC和V-NSGA-II所得解.
图 7 DMA与V-NSGA-II、IABC、MA获得的Pareto前沿Fig. 7 Pareto frontiers obtained by DMA, V-NSGA-II, IABC and MA此外, 从图7也可以看出最大完工时间$ C_{\rm{max}} $与总能耗$ E_{\rm{all}} $之间存在一定的负相关性. 当某个调度方案的最大完工时间较大时, 往往其总能耗会较低. 其主要原因是: 为了降低加工能耗, 在挑选工人时会尽量选取加工时间或者能耗低的. 结果会出现机器等待工人的情况, 造成大量的非加工时间, 因此延长了相应的完工时间. 关于总能耗$ E_{\rm{all}} $与工人负荷差异度$ W $, 两者之间存在明显的冲突关系. 相比出于降低能耗而尽可能挑选低加工时间的策略, 优化工人负荷差异度是以增大某些工件的加工时间为代价来降低工人负荷差异的. 最大完工时间$ C_{\rm{max}} $与工人负荷差异度$ W $两者存在相对正相关关系. 当某个调度方案的最大完工时间较高时, 其相应的工人负荷差异度也较高. 这里的原因也是由于降低工人负荷差异度时, 往往会以增加加工时间为代价, 由此机器完成工件的完工时间就会变大.
综上所述, 本文设计的DMA算法对于带多类型任务的不相关并行机三维可持续制造调度问题具有良好的寻优性能, 其优势可归结为以下几点: 1) 设计的单步变邻域随机搜索策略适用于本文问题, 有效地加强了对局部范围的寻优能力; 2) 可持续目标导向策略针对问题优化需求并且作用于精英个体的构造, 有效地提高了算法寻优效率; 3) 相比领域文献中的V-NSGA-II、IABC和MA这3种算法, DMA求解本文问题所得解的质量更高.
5. 结束语
本文提出了一种双重局部优化策略增强的模因算法 (DMA) 求解带多类型任务的不相关并行机三维可持续制造调度问题. 考虑多任务决策, 设计了单步变邻域随机搜索策略 (1S-VNS), 有效地更新任务分配以产生新解. 进一步分析不同维度目标的优化需求与任务调度之间的关系, 设计了可持续目标导向的优化策略 (SGS), 并分步作用于精英个体, 实现调度目标的定向优化. 在实验过程中, 验证了单步变邻域随机搜索策略的有效性, 并且说明了可持续目标导向策略能够显著地提升算法的求解性能. 最后, 与文献中V-NSGA-II、IABC和MA这3种算法对比, 实验结果表明所提DMA求得的非支配解集在多样性和收敛性上更具优势.
由于本文研究的问题是在静态环境下, 实际生产中往往会存在不确定情况, 下一步将着手研究考虑不确定性的可持续调度问题. 当问题从确定转变为不确定后, 模因算法的设计也将要求兼顾高效和适应性, 以应对生产过程中的变化. 另外, 随着机器人在生产制造过程中的广泛应用, 如何集成调度机器人和传统资源也是未来的另一个研究方向.
附录 A. 可持续目标导向优化策略的说明案例
表 A1 各个工件的基本加工数据Table A1 Basic machining data for each job工件 机器 工人 加工时间$t$ 加工单位能耗$p^{\rm{prc}}$ $J1$ $M1$ $W1$ 3 8 $J1$ $M1$ $W2$ 6 6 $J1$ $M2$ $W1$ 4 6 $J1$ $M2$ $W2$ 2 4 $J1$ $M3$ $W1$ 6 5 $J1$ $M3$ $W2$ 6 6 $J2$ $M1$ $W1$ 4 7 $J2$ $M1$ $W2$ 2 5 $J2$ $M2$ $W1$ 3 5 $J2$ $M2$ $W2$ 4 8 $J2$ $M3$ $W1$ 4 3 $J2$ $M3$ $W2$ 3 8 $J3$ $M1$ $W1$ 5 8 $J3$ $M1$ $W2$ 5 7 $J3$ $M2$ $W1$ 3 3 $J3$ $M2$ $W2$ 2 4 $J3$ $M3$ $W1$ 3 5 $J3$ $M3$ $W2$ 3 7 $J4$ $M1$ $W1$ 4 3 $J4$ $M1$ $W2$ 4 7 $J4$ $M2$ $W1$ 2 3 $J4$ $M2$ $W2$ 3 6 $J4$ $M3$ $W1$ 6 5 $J4$ $M3$ $W2$ 2 7 $J5$ $M1$ $W1$ 6 7 $J5$ $M1$ $W2$ 5 8 $J5$ $M2$ $W1$ 4 8 $J5$ $M2$ $W2$ 4 5 $J5$ $M3$ $W1$ 3 7 $J5$ $M3$ $W2$ 4 4 表 A2 机器单位空闲能耗以及开关机能耗Table A2 Unit idle energy consumption and on/off energy consumption of machines机器 空闲单位能耗$p^{\rm{idle}}$ 开关机时间$t_{\rm{on/off}}$ 开关机能耗$H_{\rm{turn}}$ $M1$ 1 2 2 $M2$ 3 3 9 $M3$ 3 3 6 -
图 2 社会维度目标导向的优化策略作用效果说明图
Fig. 2 Explanation of the effectiveness of optimization strategy guided by social dimension goal
图 3 经济维度目标导向的优化策略作用效果说明图
Fig. 3 Explanation of the effectiveness of optimization strategy guided by economic dimension goal
图 4 MMA与MOA、MMA_1、MMA_2、MMA_3性能指标的均值和95%置信区间
Fig. 4 Mean and 95% confidence interval of performance indicators of MMA, MOA, MMA_1, MMA_2 and MMA_3
图 5 DMA与MMA、MMA&SGS性能指标的均值和95%置信区间
Fig. 5 Mean and 95% confidence interval of performance indicators of DMA, MAA and MMA&SGS
图 6 DMA与V-NSGA-II、IABC、MA性能指标的均值和95%置信区间
Fig. 6 Mean and 95% confidence interval of performance indicators of DMA, V-NSGA-II, IABC and MA
图 7 DMA与V-NSGA-II、IABC、MA获得的Pareto前沿
Fig. 7 Pareto frontiers obtained by DMA, V-NSGA-II, IABC and MA
表 1 MMA与MOA、MMA_1、MMA_2、MMA_3的性能指标结果
Table 1 Results for MMA, MOA, MMA_1, MMA_2 and MMA_3
案例 $ IGD$ $R_{{\mathrm{nd}}} $ MOA MMA_1 MMA_2 MMA_3 MMA MOA MMA_1 MMA_2 MMA_3 MMA 7&4&2 0.79 0.66 0.63 0.39 0.24 0.10 0.39 0.55 0.70 0.87 7&5&3 0.79 0.65 0.58 0.86 0.33 0.13 0.39 0.47 0.42 0.72 8&4&2 0.97 0.53 0.52 0.50 0.36 0.00 0.41 0.43 0.46 0.71 8&5&3 0.74 0.63 0.53 0.57 0.47 0.00 0.14 0.40 0.35 0.61 9&4&2 0.87 0.71 0.69 0.63 0.39 0.13 0.08 0.19 0.31 0.71 9&5&3 0.64 0.57 0.63 0.59 0.35 0.00 0.19 0.11 0.32 0.75 10&4&2 0.97 0.69 0.66 0.78 0.41 0.00 0.13 0.33 0.23 0.70 10&5&3 0.70 0.67 0.55 0.59 0.44 0.00 0.07 0.38 0.29 0.67 20&10&6 0.69 0.64 0.67 0.69 0.43 0.07 0.23 0.14 0.09 0.66 20&10&8 0.67 0.82 0.80 0.73 0.36 0.15 0.02 0.11 0.13 0.70 20&12&8 0.68 0.77 0.47 0.75 0.49 0.50 0.10 0.63 0.23 0.62 20&12&10 0.48 0.90 0.53 0.72 0.40 0.68 0.08 0.58 0.12 0.68 40&10&6 0.85 0.94 0.64 0.90 0.32 0.10 0.00 0.29 0.00 0.71 40&10&8 0.92 0.91 0.62 0.65 0.31 0.05 0.08 0.28 0.12 0.78 40&12&8 0.86 0.69 0.74 0.85 0.39 0.09 0.17 0.11 0.10 0.69 40&12&10 0.77 0.78 0.71 0.81 0.43 0.14 0.13 0.17 0.12 0.67 
下载: 导出CSV
表 2 DMA与MMA、MMA&SGS的性能指标结果
Table 2 Results for DMA, MMA and MMA&SGS
案例 $ IGD$ $R_{{\mathrm{nd}}} $ MMA MMA&SGS DMA MMA MMA&SGS DMA 7&4&2 0.00 0.00 0.00 1.00 1.00 1.00 7&5&3 0.35 0.49 0.38 0.87 0.70 0.86 8&4&2 0.45 0.51 0.39 0.71 0.48 0.76 8&5&3 0.29 0.44 0.34 0.74 0.49 0.72 9&4&2 0.61 0.57 0.41 0.62 0.52 0.73 9&5&3 0.52 0.80 0.39 0.65 0.36 0.77 10&4&2 0.80 0.80 0.36 0.47 0.46 0.77 10&5&3 0.57 0.85 0.43 0.42 0.30 0.71 20&10&6 0.71 0.57 0.41 0.20 0.69 0.74 20&10&8 0.65 0.51 0.43 0.12 0.70 0.73 20&12&8 0.71 0.44 0.47 0.22 0.74 0.72 20&12&10 0.85 0.39 0.42 0.22 0.79 0.75 40&10&6 0.80 0.59 0.39 0.11 0.28 0.79 40&10&8 0.71 0.58 0.37 0.16 0.33 0.72 40&12&8 0.73 0.83 0.42 0.19 0.30 0.71 40&12&10 0.74 0.65 0.40 0.22 0.26 0.73
下载: 导出CSV
表 3 DMA与V-NSGA-II、IABC、MA的性能指标结果
Table 3 Results for DMA, V-NSGA-II, IABC and MA
案例 $IGD$ $R_{{\mathrm{nd}}}$ V-NSGA-II IABC MA DMA V-NSGA-II IABC MA DMA 7&4&2 0.85 0.67 0.48 0.15 0.00 0.15 0.70 0.87 7&5&3 0.74 0.85 0.66 0.24 0.00 0.08 0.22 0.82 8&4&2 0.65 0.76 0.41 0.32 0.20 0.08 0.43 0.76 8&5&3 0.78 0.80 0.32 0.25 0.32 0.24 0.44 0.87 9&4&2 0.41 0.63 0.56 0.36 0.39 0.34 0.37 0.76 9&5&3 0.86 0.61 0.57 0.13 0.15 0.20 0.35 0.86 10&4&2 0.52 0.31 0.49 0.22 0.21 0.31 0.27 0.77 10&5&3 0.63 0.56 0.52 0.20 0.12 0.22 0.45 0.78 20&10&6 0.85 0.88 0.69 0.21 0.07 0.05 0.15 0.83 20&10&8 0.83 0.91 0.72 0.18 0.02 0.00 0.11 0.86 20&12&8 0.79 0.84 0.74 0.31 0.05 0.00 0.23 0.71 20&12&10 0.82 0.93 0.69 0.30 0.03 0.00 0.35 0.74 40&10&6 0.78 0.81 0.55 0.11 0.00 0.00 0.15 0.85 40&10&8 0.62 0.89 0.61 0.29 0.14 0.00 0.14 0.73 40&12&8 0.59 0.87 0.53 0.23 0.11 0.00 0.15 0.77 40&12&10 0.62 0.83 0.50 0.31 0.09 0.00 0.18 0.71
下载: 导出CSV
A1 各个工件的基本加工数据
A1 Basic machining data for each job
工件 机器 工人 加工时间$t$ 加工单位能耗$p^{\rm{prc}}$ $J1$ $M1$ $W1$ 3 8 $J1$ $M1$ $W2$ 6 6 $J1$ $M2$ $W1$ 4 6 $J1$ $M2$ $W2$ 2 4 $J1$ $M3$ $W1$ 6 5 $J1$ $M3$ $W2$ 6 6 $J2$ $M1$ $W1$ 4 7 $J2$ $M1$ $W2$ 2 5 $J2$ $M2$ $W1$ 3 5 $J2$ $M2$ $W2$ 4 8 $J2$ $M3$ $W1$ 4 3 $J2$ $M3$ $W2$ 3 8 $J3$ $M1$ $W1$ 5 8 $J3$ $M1$ $W2$ 5 7 $J3$ $M2$ $W1$ 3 3 $J3$ $M2$ $W2$ 2 4 $J3$ $M3$ $W1$ 3 5 $J3$ $M3$ $W2$ 3 7 $J4$ $M1$ $W1$ 4 3 $J4$ $M1$ $W2$ 4 7 $J4$ $M2$ $W1$ 2 3 $J4$ $M2$ $W2$ 3 6 $J4$ $M3$ $W1$ 6 5 $J4$ $M3$ $W2$ 2 7 $J5$ $M1$ $W1$ 6 7 $J5$ $M1$ $W2$ 5 8 $J5$ $M2$ $W1$ 4 8 $J5$ $M2$ $W2$ 4 5 $J5$ $M3$ $W1$ 3 7 $J5$ $M3$ $W2$ 4 4
下载: 导出CSV
A2 机器单位空闲能耗以及开关机能耗
A2 Unit idle energy consumption and on/off energy consumption of machines
机器 空闲单位能耗$p^{\rm{idle}}$ 开关机时间$t_{\rm{on/off}}$ 开关机能耗$H_{\rm{turn}}$ $M1$ 1 2 2 $M2$ 3 3 9 $M3$ 3 3 6
下载: 导出CSV
-
[1] 国家制造强国建设战略咨询委员会. 中国制造2025蓝皮书 (2018). 北京: 电子工业出版社, 2018.National Manufacturing Power Construction Strategy Advisory Committee. China Manufacturing 2025 Bluebook (2018). Beijing: Publishing House of Electronics Industry, 2018. [2] Bertolini M, Leali F, Mezzogori D, Renzi C. A keyword, taxonomy and cartographic research review of sustainability concepts for production scheduling in manufacturing systems. Sustainability, 2023, 15(8): Article No. 6884 doi: 10.3390/su15086884 [3] Akbar M, Irohara T. Scheduling for sustainable manufacturing: A review. Journal of Cleaner Production, 2018, 205: 866−883 doi: 10.1016/j.jclepro.2018.09.100 [4] Catanzaro D, Pesenti R, Ronco R. Job scheduling under time-of-use energy tariffs for sustainable manufacturing: A survey. European Journal of Operational Research, 2023, 308(3): 1091−1109 doi: 10.1016/j.ejor.2023.01.029 [5] 李远征, 倪质先, 段钧韬, 徐磊, 杨涛, 曾志刚. 面向高比例新能源电网的重大耗能企业需求响应调度. 自动化学报, 2023, 49(4): 754−768Li Yuan-Zheng, Ni Zhi-Xian, Duan Jun-Tao, Xu Lei, Yang Tao, Zeng Zhi-Gang. Demand response scheduling of major energy-consuming enterprises based on a high proportion of renewable energy power grid. Acta Automatica Sinica, 2023, 49(4): 754−768 [6] 范厚明, 郭振峰, 岳丽君, 马梦知. 考虑能耗节约的集装箱码头双小车岸桥与AGV联合配置及调度优化. 自动化学报, 2021, 47(10): 2412−2426Fan Hou-Ming, Guo Zhen-Feng, Yue Li-Jun, Ma Meng-Zhi. Joint configuration and scheduling optimization of dual-trolley quay crane and AGV for container terminal with considering energy saving. Acta Automatica Sinica, 2021, 47(10): 2412−2426 [7] 贾兆红, 王燕, 张以文. 求解差异机器平行批调度的双目标协同蚁群算法. 自动化学报, 2020, 46(6): 1121−1135Jia Zhao-Hong, Wang Yan, Zhang Yi-Wen. A bi-objective synergy optimization algorithm of ant colony for scheduling on non-identical parallel batch machines. Acta Automatica Sinica, 2020, 46(6): 1121−1135 [8] Tonelli F, Bruzzone A A G, Paolucci M, Carpanzano E, Nicolò G, Giret A, et al. Assessment of mathematical programming and agent-based modelling for off-line scheduling: Application to energy aware manufacturing. CIRP Annals, 2016, 65(1): 405−408 doi: 10.1016/j.cirp.2016.04.119 [9] Alotaibi A, Lohse N, Vu T M. Dynamic agent-based bi-objective robustness for tardiness and energy in a dynamic flexible job shop. Procedia CIRP, 2016, 57: 728−733 doi: 10.1016/j.procir.2016.11.126 [10] Zhou G H, Chen Z H, Zhang C, Chang F T. An adaptive ensemble deep forest based dynamic scheduling strategy for low carbon flexible job shop under recessive disturbance. Journal of Cleaner Production, 2022, 337: Article No. 130541 doi: 10.1016/j.jclepro.2022.130541 [11] 潘子肖, 雷德明. 基于问题性质的分布式低碳并行机调度算法研究. 自动化学报, 2020, 46(11): 2427−2438Pan Zi-Xiao, Lei De-Ming. Research on property-based distributed low carbon parallel machines scheduling algorithm. Acta Automatica Sinica, 2020, 46(11): 2427−2438 [12] 雷德明, 杨冬婧. 基于新型蛙跳算法的低碳混合流水车间调度. 控制与决策, 2020, 35(6): 1329−1337Lei De-Ming, Yang Dong-Jing. A novel shuffled frog-leaping algorithm for low carbon hybrid flow shop scheduling. Control and Decision, 2020, 35(6): 1329−1337 [13] 耿凯峰, 叶春明, 吴绍兴, 刘丽. 分时电价下多目标绿色可重入混合流水车间调度. 中国机械工程, 2020, 31(12): 1469−1480Geng Kai-Feng, Ye Chun-Ming, Wu Shao-Xing, Liu Li. Multi-objective green re-entrant hybrid flow shop scheduling under time-of-use electricity tariffs. China Mechanical Engineering, 2020, 31(12): 1469−1480 [14] Liang Y L, Guo C X, Li K J, Li M Y. Economic scheduling of compressed natural gas main station considering critical peak pricing. Applied Energy, 2021, 292: Article No. 116937 doi: 10.1016/j.apenergy.2021.116937 [15] Giret A, Trentesaux D, Prabhu V. Sustainability in manufacturing operations scheduling: A state of the art review. Journal of Manufacturing Systems, 2015, 37: 126−140 doi: 10.1016/j.jmsy.2015.08.002 [16] Wu X Q, Che A. A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. Omega, 2019, 82: 155−165 doi: 10.1016/j.omega.2018.01.001 [17] Lu H, Qiao F. A sustainable parallel-machine scheduling problem with time constraint based on hybrid metaheuristic algorithm. In: Proceedings of the Chinese Automation Congress (CAC). Shanghai, China: IEEE, 2020. 1506−1510 [18] Dai M, Tang D B, Giret A, Salido M A, Li W D. Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robotics and Computer-Integrated Manufacturing, 2013, 29(5): 418−429 doi: 10.1016/j.rcim.2013.04.001 [19] Mouzon G, Yildirim M B, Twomey J. Operational methods for minimization of energy consumption of manufacturing equipment. International Journal of Production Research, 2007, 45(18−19): 4247−4271 doi: 10.1080/00207540701450013 [20] Akbar M, Irohara T. NSGA-Ⅱ variants for solving a social-conscious dual resource-constrained scheduling problem. Expert Systems With Applications, 2020, 162: Article No. 113754 doi: 10.1016/j.eswa.2020.113754 [21] Neri F, Cotta C. Memetic algorithms and memetic computing optimization: A literature review. Swarm and Evolutionary Computation, 2012, 2: 1−14 doi: 10.1016/j.swevo.2011.11.003 [22] Amaya J E, Cotta P C, Fernández Leiva A J. Memetic and hybrid evolutionary algorithms. Springer Handbook of Computational Intelligence. Berlin Heidelberg: Springer, 2015. 1047−1060 [23] Geng K F, Ye C M, Liu L. Research on multi-objective hybrid flow shop scheduling problem with dual resource constraints using improved memetic algorithm. IEEE Access, 2020, 8: 104527−104542 doi: 10.1109/ACCESS.2020.2999680 [24] Zhu H, Deng Q W, Zhang L K, Hu X, Lin W H. Low carbon flexible job shop scheduling problem considering worker learning using a memetic algorithm. Optimization and Engineering, 2020, 21(4): 1691−1716 doi: 10.1007/s11081-020-09494-y [25] Zhang R, Chiong R. Solving the energy-efficient job shop scheduling problem: A multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption. Journal of Cleaner Production, 2016, 112: 3361−3375 doi: 10.1016/j.jclepro.2015.09.097 [26] Costa A, Cappadonna F A, Fichera S. A hybrid genetic algorithm for job sequencing and worker allocation in parallel unrelated machines with sequence-dependent setup times. The International Journal of Advanced Manufacturing Technology, 2013, 69(9−12): 2799−2817 doi: 10.1007/s00170-013-5221-5 [27] Fanjul-Peyro L, Ruiz R. Iterated greedy local search methods for unrelated parallel machine scheduling. European Journal of Operational Research, 2010, 207(1): 55−69 doi: 10.1016/j.ejor.2010.03.030 [28] Guo P, Cheng W M, Wang Y. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial and Management Optimization, 2014, 10(4): 1071−1090 doi: 10.3934/jimo.2014.10.1071 [29] Fontes D B M M, Homayouni S M, Gonçalves J F. A hybrid particle swarm optimization and simulated annealing algorithm for the job shop scheduling problem with transport resources. European Journal of Operational Research, 2023, 306(3): 1140−1157 doi: 10.1016/j.ejor.2022.09.006 [30] 王飞, 孟凡超, 郑宏珍. 基于禁忌搜索和遗传算法的云仓储分配优化. 计算机集成制造系统, 2022, 28(1): 208−216Wang Fei, Meng Fan-Chao, Zheng Hong-Zhen. Distribution and optimization of cloud warehousing based on tabu search algorithm. Computer Integrated Manufacturing Systems, 2022, 28(1): 208−216 [31] Bezerra S N, Souza M J F, de Souza S R. A variable neighborhood search-based algorithm with adaptive local search for the vehicle routing problem with time windows and multi-depots aiming for vehicle fleet reduction. Computers and Operations Research, 2023, 149: Article No. 106016 [32] Sun K X, Zheng D B, Song H H, Cheng Z W, Lang X D, Yuan W D, et al. Hybrid genetic algorithm with variable neighborhood search for flexible job shop scheduling problem in a machining system. Expert Systems With Applications, 2023, 215: Article No. 119359 doi: 10.1016/j.eswa.2022.119359 [33] Wagner S, Mönch L. A variable neighborhood search approach to solve the order batching problem with heterogeneous pick devices. European Journal of Operational Research, 2023, 304(2): 461−475 doi: 10.1016/j.ejor.2022.03.056 [34] Guo H F, Zhang L S, Ren Y P, Li Y, Zhou Z W, Wu J Z. Optimizing a stochastic disassembly line balancing problem with task failure via a hybrid variable neighborhood descent-artificial bee colony algorithm. International Journal of Production Research, 2023, 61(7): 2307−2321 doi: 10.1080/00207543.2022.2069524 [35] Li Y B, Huang W X, Wu R, Guo K. An improved artificial bee colony algorithm for solving multi-objective low-carbon flexible job shop scheduling problem. Applied Soft Computing, 2020, 95: Article No. 106544 doi: 10.1016/j.asoc.2020.106544 期刊类型引用(0)
其他类型引用(1)
-
下载:
计量
- 文章访问数: 438
- HTML全文浏览量: 89
- PDF下载量: 166
- 被引次数: 1
