Research on Property-based Distributed Low Carbon Parallel Machines Scheduling Algorithm
-
摘要: 针对分布式低碳并行机调度问题(Distributed low carbon parallel machine scheduling problem, DLCPMSP), 由于该问题子问题众多, 为此, 首先将问题转换为扩展的低碳不相关并行机调度问题以降低子问题的数量; 然后提出了一种基于问题性质的非劣排序遗传算法-Ⅱ(Property-based non-dominated sorting genetic algorithm-Ⅱ, PNSGA-Ⅱ)以同时最优化总延迟时间和总能耗, 该算法运用针对问题特征的两种启发式算法初始化种群, 给出了问题的四种性质及证明, 提出了两种基于问题性质的局部搜索方法.运用大量实例进行了算法策略分析和对比实验, 结果分析表明, PNSGA-Ⅱ在求解DLCPMSP方面具有较强优势.Abstract: In this study distributed low carbon parallel machine scheduling problem (DLCPMSP) is considered. Owing to many sub-problems, DLCPMSP is transformed into an extended low carbon unrelated parallel machine scheduling problem to diminish the number of sub-problems. A property-based non-dominated sorting genetic algorithm-Ⅱ (PNSGA-Ⅱ) is proposed to minimize total tardiness and total energy consumption. In PNSGA-Ⅱ, two heuristics based on problem features of the problem are used to initialize population, four properties and related proofs are given and two property-based local searches are applied. Many experiments are conducted to show the effect of strategies and compare PNSGA-Ⅱ with other algorithms from literature. Computational results validate that PNSGA-Ⅱ has strong advantages for solving DLCPMSP.
-
Key words:
- Distributed scheduling /
- low carbon scheduling /
- heuristic /
- problem property
-
并行机调度问题(Parallel machine scheduling problem, PMSP)是制造过程中一类典型问题, 在云计算、半导体加工、汽车制造等行业具有广泛的应用背景[1]它通过对制造资源的合理分配与调度实现既定目标的最优化.传统PMSP多以总延迟时间等时间指标作为优化目标, 而很少考虑降低能耗或碳排放.随着制造企业的环保压力日益增大, 以及能源短缺、能源需求与供给之间的矛盾日益突出, 因而迫切需要研究低碳调度理论与方法, 在满足企业市场竞争需要的同时, 实现企业和社会的可持续发展[2].
近些年, 低碳并行机调度研究取得了一些进展.文献[3]在能源成本和清理成本之和小于给定值条件下提出了几种启发式算法分别优化makespan和总完成时间. Wang等[4]给出了一种增广$\varepsilon $-约束算法、构造性启发式算法和非劣排序遗传算法-Ⅱ (Non-dominated sorting genetic algorithm-Ⅱ, NSGA-Ⅱ)以同时优化总能耗和makespan. Wu等[5]提出了一种混合差分进化算法以同时最小化makespan和总能耗. Zheng等[6]给出了一种改进的多目标果蝇优化算法. Liang等[7]运用一种蚁群优化算法解决了具有总延迟时间和总能耗加权和的PMSP. Li等[8]描述了低碳PMSP的模型并提出10种启发式算法. Che等[9]提出了一种节能并行机调度方法在给定发电成本下最小化最大完成时间.雷德明等[10]结合字典序的方法, 提出了一种改进的帝国竞争算法以优化总能耗和总延迟时间.
随着经济全球化的发展, 企业为了快速地响应市场变化, 在服装[11]、渔具[12]、汽车[13]、食品和化学品加工[14]等行业中, 生产制造已从单一工厂向多工厂转换, 分布式生产调度研究引起了工业界和学术界的重视和关注[15-16].针对分布式PMSP, Chen[17]等分析了问题的复杂性, 并给出了一种快速算法以解决供应链调度问题.文献[18]给出两种双层分解算法解决了多工厂生产调度与计划. Behnamian等[19]运用一种启发式方法和改进的遗传算法(GA)以最小化makespan. Behnamian[20]提出了一种基于分解的混合变邻域禁忌搜索算法以同时优化部分工厂的总成本和其他工厂的总利润. Behnamian等[21]给出了一种结合了7种局部搜索的Monte Carlo启发式算法.
如上所述, 低碳PMSP研究取得了一些进展, 现有研究从实际生产调度[5]中给出了加工速度与能耗呈负相关的结论, 并验证了总能耗与makespan之间的冲突关系, 但这些研究大都在单工厂环境下进行, 很少考虑多工厂环境下的低碳PMSP.另一方面, 分布式PMSP的相关研究工作较少, 主要应用GA和变邻域搜索等智能算法, 其他智能算法很少用来解决分布式PMSP, 而且所优化的目标以makespan、成本和利润等为主, 很少考虑总延迟时间, 也未同时优化总能耗和总延迟时间.随着低碳制造和分布式制造的不断实施和应用, 有必要开展分布式低碳调度包括分布式低碳并行机调度问题(DLCPMSP)的深入研究.
NSGA-Ⅱ[22]是一种经典的多目标进化算法, 目前已广泛应用于路径规划[23-24]、选址[25-26]、调度[27-30]和参数优化[31-32]等工程领域, 显示出较强的搜索优势[33], 只是在NSGA-Ⅱ的应用和以上两类PMSP研究中, 较少关注问题性质与智能算法的结合, 问题性质的引入可避免无效搜索, 加强对最优解可能区域的高效搜索[34].目前, 基于问题性质的调度还未引起研究者的足够重视, 现有工作主要针对makespan[6, 35-37]展开研究, 而对总延迟时间和能耗等目标的研究相对较少, 同时基于问题性质的并行机调度研究进展也很少.
针对以同时最小化总延迟时间和总能耗为目标的DLCPMSP, 考虑到该问题具有较多子问题, 首先通过直接将工件分配给机器的方式, 将该问题转换成扩展的低碳不相关并行机调度问题以减少子问题的数量; 然后, 运用针对问题特征的两种启发式算法初始化种群, 给出了问题的四种性质及相关证明, 提出了两种基于问题性质的局部搜索方法, 在此基础上, 设计一种基于问题性质的非劣排序遗传算法-Ⅱ (PNSGA-Ⅱ).运用大量实例进行仿真实验, 包括新策略对算法性能的影响实验和对比实验, 结果表明, 启发式算法和基于问题性质的局部搜索有效地改进了算法的搜索性能, 且算法在解决DLCPMSP方面具有较强的搜索优势.
1. 分布式低碳并行机调度问题
1.1 符号定义
问题描述中所使用的的符号含义如下:
$F$ 工厂数, 工厂编号以$f$表示
$W$ 所有工厂的机器总数, 机器编号用$k$表示
${M_k}$ 第$k$个机器
${m^f}$ 工厂$f$的机器数
$n$ 工件数, 工件编号以$i$表示
${J_i}$ 第$i$个工件
${D}$ 加工速度的种类
${v_l}$ 第$l$种加工速度
${p_{ikl}}$ 工件${J_i}$在机器${M_k}$上以速度${v_l}$加工的时间
${EC_{kl}} $ 机器${M_k}$以速度${v_l}$加工的单位时间能耗
${C_i}$ 工件${J_i}$的完成时间
${d_i}$ 工件${J_i}$的交货期
${T_i}$ 工件${J_i}$的延迟时间, ${{T}_{i}}=\max \left\{ {{C}_{i}}-{{d}_{i}}, 0 \right\}$
${f_1}$ 总延迟时间
${f_2}$ 总能耗
${z_{ikl}}$ 若工件${J_i}$在机器${M_k}$上以速度${v_l}$加工, 则$z_{ikl}$等于1, 否则为0
1.2 问题描述
DLCPMSP描述如下:存在$F$个独立的工厂, 每个工厂$f$具有$m^f$台不相关并行机, 共有$W$台机器, 其中$\ W=\sum\nolimits_{f=1}^{F}{{{m}^{f}}}$, 机器$\ {{M}_{{{s}_{f}} + 1}}, {{M}_{{{s}_{f}} + 2}}, \cdots, {{M}_{{{s}_{f}} + {{m}^{f}}}}$位于工厂$f$, ${\ s_f=\sum\nolimits_{l=1}^{f-1}{{{m}^{l}}}}$, $f>1$, $s_1=0$.每台机器有$D$种加工速度, ${V=\left({{v}_{1}}, {{v}_{2}}, \cdots, {{v}_{D}} \right)}$.机器$M_k$以速度$v_l$加工时, 单位时间能耗为$EC_{kl}$.具有$n$个工件$\ {{J}_{1}}, {{J}_{2}}, \cdots, {{J}_{n}}$, 每个工件只需加工一次, 其加工机器可以是$W$台并行机中的任一台, 工件$J_i$的交货期为$d_i$, $p_{ikl}$表示工件$J_i$在机器$M_k$上以速度$v_l$加工的加工时间, 工件加工时间取决于其所在加工机器的性能和加工速度, 文献[5$-$6, 35]中给出假设, 同一工件在同一台机器上加工, 加工速度越大, 加工时间越短, 相应的能源消耗也越大, 即若$v_l < v_g$, 则${p_{ikl}>p_{ikg}}$, ${E{{C}_{kl}}\times {{p}_{ikl}} < E{{C}_{kg}}\times {{p}_{ikg}}}$.
存在一些与工件和机器相关的约束, 包括每个工件可在任意一台机器上加工且同一时刻只能在一台机器上加工, 每台机器同一时间只能加工一个工件, 在零时刻所有工件和加工机器都可用, 加工一旦开始就不能中断, 准备时间忽略不计或包含在加工时间内.
DLCPMSP是传统PMSP的扩展, 通常, PMSP由机器分配和调度组成, 而DLCPMSP则增加了工厂分配和速度选择两个子问题, 其中工厂分配子问题用来决定每个工件的加工工厂, 机器分配为工件在其所在工厂内分配合适的机器, 而速度选择子问题则确定机器加工工件时的速度.
由于每个机器所属的工厂已经确定, 将工厂分配和机器分配合并为扩展后的机器分配子问题, 直接为工件分配机器, 而不是先确定工件的加工工厂, 再选择相应工厂内的加工机器, 这样可减少一个子问题, 从而降低子问题数量.
整个问题的目的在于为每个工件分配合适的加工机器并选择机器相应的加工速度, 以及确定每台机器上工件的加工顺序以最小化如下两个目标.
$$ \begin{align} &\min {{f}_{1}}=\sum\limits_{i=1}^{n}{{{T}_{i}}}\nonumber\\ &\min {{f}_{2}}=\sum\limits_{i=1}^{n}{\sum\limits_{k=1}^{W}{\sum\limits_{l=1}^{D}{{{p}_{ikl}}\times E{{C}_{kl}}\times {{z}_{ikl}}}}} \end{align} $$ (1) 2. 问题性质
在搜索过程中结合问题性质, 引导智能算法优化, 能显著地提升算法的搜索能力. DLCPMSP具有总能耗和总延迟时间两个目标, 针对这两个目标, 给出了如下四种性质.
性质1. 机器分配和速度选择保持不变的条件下, 若调整机器上工件的加工顺序, 则总延迟时间将发生改变, 而总能耗保持不变.
性质2. 对于一台机器上的两个相邻工件, 在加工速度不变的条件下互换两者的加工顺序, 则在这两个工件之前和之后加工的工件的延迟时间保持不变.
性质3. 同一台机器$M_k$上相邻两个工件$i$和$j$分别以速度$v_l$和$v_g$加工, 设工件$i$先加工, 且其开始加工时间为$t$, 1)若${T_i=0}$, ${T_j=0}$或${T_i>0}$, ${T_j=0}$, 则仅互换这两个工件, 不会引起它们的延迟时间之和降低; 2)若${T_i=0}$, ${T_j>0}$, 则当${{{d}_{i}}>\max \{{{d}_{j}}, t + {{p}_{jkg}}\}}$时, 只互换两个工件将导致两工件延迟时间之和降低; 3)若${T_i>0}$, ${T_j>0}$, 则当${ {{d}_{j}}>t + {{p}_{jkg}}}$且${{{d}_{j}} < t + {{p}_{ikl}}}$或${{{d}_{j}} < t + {{p}_{jkg}}}$且${{p_{ikl}}>{{p}_{jkg}}}$时, 只互换两个工件将引起它们的延迟时间之和下降.
证明. 互换前工件$i$和$j$完成时间为$C_i$, $C_j$, 互换后为${C_{i}^{*}, C_{j}^{*}}$, ${C_{i}^{*}={{C}_{i}} + {{p}_{jkg}}}$, ${C_{j}^{*}={{C}_{j}}-{{p}_{ikl}}}$, 定义${T_{i}^{*}=\max \left\{ C_{i}^{*}-{{d}_{i}}, 0 \right\}}$, ${T_{j}^{*}=\max \left\{ C_{j}^{*}-{{d}_{j}}, 0 \right\}}$.
1) 若${T_i=0}$, ${T_j=0}$, 则$T_i + T_j=0$, 互换后$ T_{i}^{*} + T_{j}^{*}=\max \left\{ {{C}_{i}}- {{d}_{i}} + {{p}_{jkg}}, 0 \right\} + \max \left\{ {{C}_{j}}-{{d}_{j}}-{{p}_{ikl}}, 0 \right\} \ge 0$, 即互换两工件后它们的延迟时间之和不会降低. ${T_i>0}$, ${T_j=0}$, 则$T_i + T_j=C_i-d_i$, 互换后$T_{i}^{*} + T_{j}^{*}=\max \left\{ {{C}_{i}}-{{d}_{i}} + {{p}_{jkg}}, 0 \right\} + \max \left\{ {{C}_{j}}-{{d}_{j}}-{{p}_{ikl}}, 0 \right\}={{C}_{i}}-{{d}_{i}} + {{p}_{jkg}}$.可见, 只互换两个工件, 会引起它们的延迟时间之和上升.
2) 若${T_i=0}$, ${T_j>0}$, 则, $d_j < t + p_{ikl} + p_{jkg}$, $d_i>t + p_{ikl}$.
若$d_i < t + p_{ikl} + p_{jkg}$, 则, $T_i^*=C_i^*-d_i=t + p_{ikl} + p_{jkg}-d_i$;
若$d_i>t + p_{ikl} + p_{jkg}$, 则, $T_i^*=0$;
若$d_j < t + p_{jkg}$, 则, $T_j^*=C_j^*-d_j=t + p_{jkg}-d_j$;
若$d_j>t + p_{jkg}$, 则, $T_j^*=0$;
当$d_i < t + p_{ikl} + p_{jkg}$, $d_j < t + p_{jkg}$, 互换后若两工件延迟时间之和下降, $T_i^* + T_j^* < T_i + T_j$, 即$t + p_{ikl} + p_{jkg}-d_i + t + p_{jkg}-d_j < t + p_{ikl} + p_{jkg}-d_j$, 则$d_i>t + p_{jkg}$.反之, 若$d_i>t + p_{jkg}$, 则互换后两工件延迟时间之和降低.
当$d_i < t + p_{ikl} + p_{jkg}$, $d_j>t + p_{jkg}$, 互换后若两工件延迟时间之和下降, 即$t + p_{ikl} + p_{jkg}-d_i < t + p_{ikl} + p_{jkg}-d_j$, 则$d_i>d_j$.反之, 若$d_i>d_j$, 则互换后工件延迟时间之和降低.
只要$d_i>t + p_{ikl} + p_{jkg}$, 无论$d_j < t + p_{jkg}$或$d_j>t + p_{jkg}$, 充要条件都成立.
综上所述, 2)成立.
3) 若${T_i>0}$, ${T_j>0}$, 则, $d_j < t + p_{ikl} + p_{jkg}$, $d_i < t + p_{ikl}$.
若$d_j < t + p_{jkg}$, 则, $T_j^*=C_j^*-d_j=t + p_{jkg}-d_j$;
若$d_j>t + p_{jkg}$, 则, $T_j^*=0$;
当$d_j>t + p_{jkg}$, 互换后若两工件延迟时间之和下降, 即$T_i^* + T_j^* < T_i + T_j$, 也即$t + p_{ikl} + p_{jkg}-d_i < t + p_{ikl}-d_i + t + p_{ikl} + p_{jkg}-d_j$, 则$d_j < t + p_{ikl}$, 必要条件成立; 同理可证充分条件.
当$d_j < t + p_{jkg}$, 互换后若两工件延迟时间之和下降, 即$t + p_{jkg} + p_{ikl}-d_i + t + p_{jkg}-d_j < t + p_{ikl}-d_i + t + p_{ikl} + p_{jkg}-d_j$, 则$p_{ikl}>p_{jkg}$, 必要条件成立; 同理可证充分条件.
综上所述, 3)成立.
性质4. 对每台机器上最后加工的工件, 若该工件能按时交货, 则在不引起延期交货的条件下, 可降低该机器加工该工件时的速度, 导致能耗减小, 而总延迟时间保持不变.
以上四种性质也适合目标函数为总能耗和总延迟时间的其他分布式并行机调度问题.
3. 基于PNSGA-Ⅱ的分布式低碳并行机调度
针对DLCPMSP, 结合问题特征构建两种启发式算法, 运用问题的四种性质, 提出基于问题性质的局部搜索方法, 以增强PNSGA-Ⅱ的局部搜索能力, 同时避免无效搜索, 提高搜索效率.
3.1 编码方式
文献[19]给出了一种矩阵编码方式, 矩阵的每一行对应一个工厂, 该方法结构复杂, 行与行之间彼此依赖, 相应的全局搜索方式设计复杂, 若应用该方法对DLCPMSP的解进行编码, 需要引入速度信息, 将导致算法设计更加复杂. Zheng等[6]针对低碳PMSP给出了一个由工件-速度对组成的编码方式, 但该方法结构也较复杂, 相应的交叉和变异设计也不简单.如前所述, DLCPMSP由扩展的机器分配、调度和速度选择三个子问题组成, 对于这类子问题众多的复杂问题, 应对各子问题独立编码, 这样可以对各子问题的编码串单独设计全局和局部搜索操作, 从而降低算法设计复杂性.
给出了一种三串编码方式, 问题的解由机器分配串$\left[{{M}_{{{\theta }_{1}}}}, {{M}_{{{\theta }_{2}}}}, \cdots, {{M}_{{{\theta }_{n}}}} \right]$、调度串$\left[{{\pi }_{1}}, {{\pi }_{2}}, \cdots, {{\pi }_{n}} \right]$和速度选择串$\left[ {{v}_{{{r}_{1}}}}, {{v}_{{{r}_{2}}}}, \cdots, {{v}_{{{r}_{n}}}} \right]$组成, 其中${{M}_{{{\theta }_{i}}}}$表示为工件$J_i$分配的机器, $1\le {{\theta }_{i}}\le W$, ${{\pi }_{i}}\in \left\{ 1, 2, \cdots, n \right\}$, 对于任意$i\ne j$, ${{\pi }_{i}}\ne {{\pi }_{j}}$, ${{v}_{{{r}_{i}}}}$为机器${{M}_{{{\theta }_{i}}}}$的加工速度.
解码过程描述如下:首先, 根据机器分配串和调度串, 确定每台并行机加工的工件; 然后, 根据调度串中工件的先后顺序确定每台机器上工件的加工顺序, 并依照工件加工顺序, 结合速度选择串确定工件的加工速度, 依次安排各工件的加工.
3.2 基于启发式算法的种群初始化
通常, 种群初始化方法包括随机初始化和启发式初始化, PNSGA-Ⅱ的种群初始化结合了这两种初始化方法.
种群初始化过程描述如下:
步骤1. 确定种群规模$N$, $k=1$;
步骤2. 生成一个随机整数$a$, 其中$a\in \left[1, n \right]$;
步骤3. 采用最小负荷最小能耗算法安排解$x_k$的前$a$个工件;
步骤4. 用最小负荷最小延迟算法安排解$x_k$的后$n-a$个工件;
步骤5. 若$k=N$, 则结束; 否则, $k=k + 1$并转到步骤2.
由于调大机器加工速度, 对降低总延迟时间有利, 为此, 将速度$v_{r_i}$的$r_i$设置为$round\left(0.5D\right)$到$D$之间的值, 其中$round\left(x\right)$给出不小于$x$且最接近$x$的整数; 同时为了评估$t$时刻, 工件$J_i$在机器$M_k$上以速度$v_l$加工时按时交货的紧张程度, 定义指标
$$ \begin{equation} e_{ikl}^{t}={{d}_{i}}-t-{{p}_{ikl}} \end{equation} $$ (2) $e_{ikl}^{t}\ge 0$时, $e_{ikl}^{t}$越小, 说明工件$J_i$的完成时间越接近交货期; $e_{ikl}^{t} < 0$时, $e_{ikl}^{t}$越小, 说明工件$J_i$的延迟时间越大, 进而直接影响总延迟时间.显然, $e_{ikl}^{t}$越小, 优先加工工件$J_i$的必要性越大, 根据以上问题性质, 提出了最小负荷最小延迟算法.
最小负荷最小延迟算法具体描述如下:
步骤1. 选取负荷最小的机器$M_k$, 若存在多台, 则随机选择一台;
步骤2. 随机选择加工速度$v_l$, 其中$l$为区间$\left[round(0.5D), D\right]$内的随机整数;
步骤3. 计算每个待加工工件在机器$M_k$上以速度$v_l$加工的指标$e_{ikl}^{t}$;
步骤4. 从待加工工件中选择$e_{ikl}^{t}$最小的工件, 若存在多个, 则随机选取一个, 将该工件安排在机器$M_k$上加工, 并将机器$M_k$的加工速度设为$v_l$;
步骤5. 判断是否还有工件未加工, 若有则返回步骤1;否则结束搜索.
计算指标$e_{ikl}^{t}$时, 将机器$M_k$最早可用的时间定义为$t$, 所谓最早可用指完成当前工件的加工, 能开始新的工件加工的最早时间.由于降低机器加工速度, 有助于降低能耗, 应用最小负荷最小能耗算法时, 将机器速度$v_{r_i}$的$r_i$设置为区间$\left[1, round\left(0.5D\right)\right]$内的整数, 该算法的具体描述如下:
步骤1. 选取负荷最小的机器$M_k$, 若存在多台, 则随机选择一台;
步骤2. 随机选择加工速度$v_l$, 其中$l$为区间$\left[1, round\left(0.5D\right)\right]$内的随机整数;
步骤3. 从待加工工件中选择$M_k$上加工能耗最小的工件, 若存在多个工件, 则随机选取一个, 并将机器$M_k$加工速度定为$v_l$;
步骤4. 判断是否还有工件未加工, 若有, 则返回步骤1;否则结束搜索.
两种启发式算法为工件的加工机器确定合适的加工速度, 并结合指标$e_{ikl}^{t}$和工件加工能耗把工件安排在负荷最小的机器上, 这样有助于获得总延迟时间和总能耗都比较小的初始解, 从而获得质量较高的初始种群.
3.3 基于问题性质的局部搜索
利用第2节描述的四种性质, 设计了两种局部搜索算法, 分别描述如下.
第一种局部搜索侧重对总延迟时间的改善.针对解$x$, 按照性质3给出的互换条件可以降低两工件的延迟时间之和, 由性质2可知, 仅互换两相邻工件不会影响其前后工件的延迟时间, 这样导致新解$y$的总延迟时间减小即$f_1\left(y\right) < f_1\left(x\right)$, 由性质1可知, 单纯改变一个机器上工件的加工顺序, 总能耗不会发生变化即$f_2\left(y\right)=f_2\left(x\right)$, 从而使得新解$y$支配解$x$.
第一种局部搜索的具体描述如下:从机器$M_1$开始, 依次对每台机器$M_k$, 从该机器的第一个工件开始, 确定相邻两个工件是否满足性质3给出的互换条件, 若满足, 则互换两个工件, 否则比较下一对工件, 依此进行, 直到找不到可比较的相邻工件为止.
第二种局部搜索侧重对总能耗的改善, 针对解$x$, 根据性质4依次减小延迟时间为0的相关工件的加工速度, 并保证延迟时间始终为0, 变换后的解$y$的总能耗减小而总延迟时间没有变化, 新解$y$支配解$x$.
第二种局部搜索的具体过程描述如下:机器$M_1$开始, 依次对每台机器$M_k$, 确定机器上的最后加工工件的延迟时间是否为零且加工速度能否降低, 若都是, 则在保证该工件延迟时间为零的条件下确定其最低加工速度, 并将机器的当前加工速度调为最低加工速度; 否则, 该工件的加工速度不变.
两种局部搜索方法利用问题的性质有针对性改善其中一个目标, 整个搜索过程是确定性的, 无随机因素, 与两种启发式方法的区别也在此.
3.4 算法描述
PNSGA-Ⅱ的具体步骤描述如下:
步骤1. 设$gen=1$, 采用两种启发式算法初始化种群$P_{gen}$并产生种群$Q_{gen}$;
步骤2. 采用二元锦标赛对种群$P_{gen}$进行复制;
步骤3. 根据交叉概率$p_c$依次对$P_{gen}$执行调度串、机器分配串和速度串的交叉;
步骤4. 根据变异概率$p_m$对种群$P_{gen}$执行变异操作;
步骤5. 对种群$P_{gen}$中的每个个体依次执行第一种局部搜索和第二种局部搜索;
步骤6. 将种群$P_{gen}$和$Q_{gen}$合并, 对所有个体进行非劣排序并计算拥挤距离, 依据NSGA-Ⅱ的方式得到$P_{gen + 1}$和$Q_{gen + 1}$;
步骤7. 判断是否满足终止条件, 若满足, 则结束搜索; 否则$gen=gen + 1$并跳回步骤2.
关于交叉, 对机器分配串和速度选择串都采用均匀交叉, 对调度串则采用扩展顺序交叉(EOX)[38].
机器分配串的均匀交叉描述如下:
步骤1. 生成一个长度为$n\left[0, 1\right]$内的随机数串;
步骤2. 从随机数串第1位开始, 依次对各位进行判定, 对于第$k$位随机数, 若该随机数大于0.5, 则子代1的第$k$位机器由父代1第$k$位机器赋值; 否则第$k$位机器与父代2同样位置上的机器相同;
步骤3. 重复步骤1和步骤2产生子代2.
速度选择串均匀交叉的过程和上述过程类似. EOX具体过程如下:
步骤1. 从父代1中随机选择一个基因片段$phi$;
步骤2. 删除父代2中与片段$phi$中相同的元素, 同时标出删除操作之前父代2中与片段$phi$第一个元素相同的元素的位置$l$;
步骤3. 将片段$phi$插入父代2中的位置处$l$, 生成交叉后的新的调度串.
针对机器分配串和速度分配串, 采用位变异, 随机选择变异基因, 然后对该基因重新赋值.例如, 从机器分配串中随机选择一个${{M}_{{{\theta }_{i}}}}$, 然后从工件$J_i$所有可能的加工机器中随机选择一台不同于${{M}_{{{\theta }_{i}}}}$的机器替代${{M}_{{{\theta }_{i}}}}$.针对调度串, 采用互换, 随机选择两个不同的工件后, 互换它们的位置.
PNSGA-Ⅱ的二元锦标赛过程如下:随机选择一对个体, 若它们彼此支配, 则选择支配个体进行下一代, 若两种彼此不受支配, 则随机选择一个进入下一代.
PNSGA-Ⅱ的步骤3中, 先对种群$P_{gen}$的所有个体按$p_c$执行调度串交叉, 然后再根据$p_c$选择个体进行分配串交叉, 最后根据$p_c$选择个体进行速度串交叉. 图 1给出了算法流程图.
4. 计算实验
为了验证PNSGA-Ⅱ在求解DLCPMSP方面的搜索优势, 进行了大量计算实验, 这些实验运用MATLAB2015b编程实现并运行于具有16.0 GB RAM 2.80 GHz的计算机上.
4.1 测试实例与评价指标
由于DLCPMSP相关研究很少, 缺乏现成的测试数据.借鉴文献[6]给出了DLCPMSP的一套测试实例集, 包括小、中、大三种规模, 小规模问题$n\in \left \{ 10, 20, 30 \right \}$, 工厂数$F=2$, 机器数$m^f\in\left[2, 3\right]$; 中规模问题$n\in \left \{ 40, 50, 60 \right\}$, $F\in\left\{2, 3, 4\right\}$, $m^f\in\left[2, 4\right]$; 大规模问题$n\in \left \{ 80, 100, 200\right \}$, $F\in\left\{2, 3, 4, 5\right\}$, $m_f\in\left[2, 5\right]$, 存在$F \times n$的组合24组, 共24个实例, $p_{ikl}\in\left[1, 100\right]$, $EC_{kl}\in\left[4, 16\right]$, $D=4$, ${{d}_{i}}=\left(1 + 3\alpha \right){\times \sum\nolimits_{k=1}^{W}{\sum\nolimits_{l=1}^{D}{{{p}_{ikl}}}}}/{\left(W\times D \right)}$, $\alpha$为区间$[0, 1]$内的随机数.
采用如下三个指标评价算法的计算结果.
距离指标$D{{I}_{R}}$[39]用来评价算法$l$所得的非劣解集${{\Omega }_{l}}$中的元素相对于参考集${{\Omega }^*}$的距离.
$$\begin{equation} D{{I}_{R}}\left( {{\Omega }_{l}} \right)=\frac{1}{\left| {{\Omega }^{*}} \right|}\sum\limits_{y\in {{\Omega }^{*}}}{\min \left\{ {{\sigma }_{xy}}|x\in {{\Omega }_{l}} \right\}} \end{equation} $$ (3) 其中$\sigma _{xy}$表示解$x$与参考集${{\Omega}^*}$中元素$y$在归一化目标空间内的欧氏距离, 参考集${{\Omega}^*}$由所有算法的非劣解集并集中的非劣解组成. $D{{I}_{R}}$越小说明算法$l$所得的非劣解集${{\Omega}_l}$相对于参考集${{\Omega}^*}$的距离越小, 算法的收敛性越好, 当${DI}_R\left({\Omega}_l\right)$为0时则算法$l$所得的非劣解集${{\Omega}_l}$包含了参考集${{\Omega}^*}$的所有解.
指标$\rho$[40]用来评价非劣解集${{\Omega}_l}$为参考集${{\Omega}^*}$所提供非劣解的数目.
$$ \begin{equation} \rho \left( {{\Omega }_{l}} \right)=\frac{{\left| \left\{ x\in {{\Omega }_{l}}\text{ }\!\!|\!\!\text{ }x\in {{\Omega }^{\text{*}}} \right\} \right|}}{{\left| {{\Omega }^{\text{*}}} \right|}} \end{equation} $$ (4) $\rho\left({\Omega}_l\right)$指标越大, 说明非劣解集${{\Omega}_l}$为参考集${{\Omega}^*}$提供的非劣解的数目越多, 对应算法越优.
指标$SP$ (Spacing)[35]用来评价非劣解集的分布均匀性情况.
$$ \begin{equation} SP\left( {{\Omega }_{l}} \right)=\sqrt{\frac{1}{\left| {{\Omega }_{l}} \right|}\sum\limits_{x\in {{\Omega }_{l}}}{\frac{{\left( dis{{t}_{x}}-\overline{dist} \right)}^{2}}{{\overline{dist}}}}} \end{equation} $$ (5) 其中$dist_x$表示解$x$和其最近解之间的欧氏距离, $\overline{dist}$为${{\Omega}_l}$内所有解的平均距离. $SP$越小, 说明解的分布越均匀.
4.2 参数设置
PNSGA-Ⅱ的参数包括种群规模$N$, 交叉概率$p_c$, 变异概率$p_m$.为了确定各个参数的值, 选用实例$2\times 50$, 设计了四水平的DOE实验, 表 1给出了每个水平的参数取值, 表 2为正交表, 每组参数独立运行10遍, 每次运行时间为$0.5\times n=25$ (s), 计算每种参数组合下的$D{{I}_{R}}$, 其中${{\Omega}^*}$由算法在每一种参数组合下产生的非劣解集合并后, 所得并集内的非劣解组成, 计算结果如表 2所示. 表 3给出了各参数对应的平均$D{{I}_{R}}$.各参数对算法性能的影响趋势如图 2所示.
表 1 参数各水平取值Table 1 Factor levels of parameters参数 水平 1 2 3 4 $p_c$ 0.80 0.85 0.90 95 $p_m$ 0.00 0.05 0.10 0.15 $N$ 60 90 120 150 表 2 参数正交表及$DI_R$值Table 2 Orthogonal array and $DI_R$ valueNo. Factor $DI_R$ $p_c$ $p_m$ $N$ 1 1 1 1 20.94 2 1 2 2 13.42 3 1 3 3 6.012 4 1 4 4 6.519 5 2 1 2 19.85 6 2 2 1 13.82 7 2 3 4 6.721 8 2 4 3 6.000 9 3 1 3 11.89 10 3 2 4 8.126 11 3 3 1 10.68 12 3 4 2 6.536 13 4 1 4 11.13 14 4 2 3 8.531 15 4 3 2 8.199 16 4 4 1 14.84 表 3 各参数平均$DI_R$Table 3 Average $DI_R$ of factors水平 $p_c$ $p_m$ $N$ 1 11.72 15.95 15.07 2 11.60 10.97 12.00 3 9.308 7.903 8.108 4 10.68 8.474 8.124 Delta 2.415 8.050 6.962 排秩 3 1 2 由表 3和图 2可以看出, PNSGA-Ⅱ的参数设置为$p_c=0.90$, $p_m=0.1$, $N=120$时算法性能最好, 故选择上述参数设置.
4.3 算法策略对比实验
PNSGA-Ⅱ中, 引入了基于启发式算法的种群初始化和基于问题性质的局部搜索, 为了验证这两种新策略对算法的性能影响, 构造了PNSGA-Ⅱ的两种变体, 其中将随机初始化的PNSGA-Ⅱ定义为算法A1, 去掉基于问题性质的局部搜索的PNSGA-Ⅱ定义为算法A2, 相应的计算结果如表 4$\sim$6所示, 其中参考集${\Omega}^*$由6种算法的非劣解集的并集中的非劣解组成, 6种算法每次运行的终止条件为计算时间, 参考文献[41]并结合分布式并行机调度的性质, 设置当运行时间为$0.5\times n$ (s)时, 算法停止搜索, 每个算法关于每个实例运行10次, 其中"$-$"表示算法在规定时间内未能给出有效结果.配对样本均值检验的结果如表 7所示, "$t$-test(A, B)"表示一次配对$t$-test, 用来判断算法B是否给出了优于A的更好的样本均值, 假设显著水平为0.05, 如果相应的$p-$值小于0.05, 说明算法A优于算法B.
表 4 种算法关于指标$DI_R$的对比Table 4 Comparisons of six algorithms on metric $DI_R$实例 PNSGA-Ⅱ A1 A2 NSGA-Ⅱ SPEA2 TIPG $2\times 10$ 1.009 5.989 3.753 13.50 1.147 29.95 $2\times 20$ 0.281 6.376 3.388 7.796 4.388 53.21 $2\times 30$ 0.297 6.272 3.361 9.465 5.240 47.96 $2\times 40$ 0.730 5.559 1.714 6.074 4.894 68.06 $3\times 40$ 0.074 6.583 0.676 7.432 6.269 63.24 $4\times 40$ 0.138 9.122 3.640 11.81 9.682 75.89 $2\times 50$ 0.933 9.606 2.045 8.024 12.73 72.65 $3\times 50$ 0.575 4.534 2.159 9.229 9.567 82.67 $4\times 50$ 0.045 7.053 2.243 8.349 7.639 83.56 $2\times 60$ 1.352 9.857 0.897 9.036 9.905 73.18 $3\times 60$ 0.866 5.166 1.608 6.861 7.685 73.38 $4\times 60$ 0.257 8.610 0.944 9.485 10.09 77.30 $2\times 80$ 1.851 8.616 0.871 9.539 14.04 83.09 $3\times 80$ 0.932 8.299 0.979 10.08 11.30 84.17 $4\times 80$ 1.017 14.53 0.594 16.18 18.06 98.23 $5\times 80$ 0.591 12.02 0.512 11.77 14.91 91.74 $2\times 100$ 1.611 5.917 1.996 6.714 10.73 76.21 $3\times 100$ 0.234 6.328 1.295 7.729 11.84 83.59 $4\times 100$ 0.083 7.440 1.079 11.53 15.13 88.09 $5\times 100$ 1.299 13.47 0.565 13.46 17.34 88.42 $2\times 200$ 1.664 21.42 2.198 28.48 36.18 $-$ $3\times 200$ 2.808 39.37 1.559 45.69 56.06 $-$ $4\times 200$ 0.640 33.89 1.886 38.96 48.04 $-$ $5\times 200$ 0.291 34.63 3.118 36.65 54.36 $-$ 均值 0.816 12.11 1.795 14.33 16.55 74.73 表 5 6种算法关于指标$\rho $的结果对比Table 5 Comparisons of six algorithms on metric $\rho $实例 PNSGA-Ⅱ A1 A2 NSGA-Ⅱ SPEA2 TIPG $2\times 10$ 0.444 0.111 0.000 0.000 0.556 0.000 $2\times 20$ 0.583 0.021 0.333 0.021 0.083 0.000 $2\times 30$ 0.975 0.025 0.000 0.000 0.012 0.000 $2\times 40$ 0.847 0.020 0.053 0.067 0.020 0.000 $3\times 40$ 0.910 0.010 0.080 0.000 0.010 0.000 $4\times 40$ 0.710 0.011 0.290 0.000 0.000 0.000 $2\times 50$ 0.718 0.137 0.076 0.046 0.031 0.000 $3\times 50$ 0.872 0.032 0.106 0.000 0.000 0.000 $4\times 50$ 0.896 0.015 0.104 0.000 0.000 0.000 $2\times 60$ 0.840 0.024 0.080 0.032 0.032 0.000 $3\times 60$ 0.822 0.059 0.129 0.000 0.000 0.000 $4\times 60$ 0.793 0.009 0.198 0.000 0.009 0.000 $2\times 80$ 0.551 0.059 0.324 0.074 0.000 0.000 $3\times 80$ 0.632 0.008 0.361 0.000 0.008 0.000 $4\times 80$ 0.646 0.015 0.354 0.000 0.000 0.000 $5\times 80$ 0.648 0.014 0.352 0.000 0.000 0.000 $2\times 100$ 0.759 0.036 0.015 0.197 0.000 0.000 $3\times 100$ 0.912 0.054 0.039 0.000 0.000 0.000 $4\times 100$ 0.897 0.015 0.088 0.004 0.000 0.000 $5\times 100$ 0.480 0.010 0.520 0.000 0.000 0.000 $2\times 200$ 0.853 0.041 0.086 0.024 0.000 $-$ $3\times 200$ 0.765 0.008 0.212 0.019 0.000 $-$ $4\times 200$ 0.852 0.004 0.148 0.000 0.000 $-$ $5\times 200$ 0.926 0.005 0.074 0.000 0.000 $-$ 均值 0.764 0.031 0.168 0.020 0.032 0.000 表 6 6种算法关于指标$SP$的结果对比Table 6 Comparisons of six algorithms on metric $SP$实例 PNSGA-Ⅱ A1 A2 NSGA-Ⅱ SPEA2 TIPG $2\times 10$ 1.127 3.207 4.554 14.68 2.784 7.470 $2\times 20$ 5.067 7.465 8.554 11.71 6.242 10.89 $2\times 30$ 5.036 13.77 10.95 8.816 14.22 18.55 $2\times 40$ 5.991 11.06 8.533 8.843 8.173 32.89 $3\times 40$ 6.477 8.199 10.12 9.624 6.823 13.56 $4\times 40$ 11.62 6.939 7.778 28.52 7.423 13.82 $2\times 50$ 10.94 6.345 14.26 13.60 16.32 21.35 $3\times 50$ 7.455 6.917 13.66 11.19 8.641 9.448 $4\times 50$ 8.089 9.014 27.52 10.73 8.114 24.12 $2\times 60$ 6.587 15.73 9.264 8.064 10.17 14.75 $3\times 60$ 9.447 12.27 17.74 13.22 8.957 13.86 $4\times 60$ 20.60 17.81 10.13 14.20 7.310 9.080 $2\times 80$ 13.98 13.50 8.977 10.19 6.923 36.90 $3\times 80$ 17.02 16.83 8.464 14.67 10.77 13.87 $4\times 80$ 4.881 17.26 10.34 17.97 7.760 12.32 $5\times 80$ 6.401 12.19 11.54 17.18 11.84 19.29 $2\times 100$ 11.78 12.92 17.65 37.68 38.74 101.1 $3\times 100$ 22.38 19.90 15.50 14.32 14.00 15.60 $4\times 100$ 10.31 16.27 12.09 10.93 20.60 26.28 $5\times 100$ 4.997 10.20 46.75 12.72 7.564 20.12 $2\times 200$ 20.37 22.10 53.72 16.08 41.22 $-$ $3\times 200$ 8.388 34.40 18.14 19.98 25.37 $-$ $4\times 200$ 23.68 36.78 18.37 23.00 32.56 $-$ $5\times 200$ 24.12 28.59 20.19 33.74 11.76 $-$ 均值 11.11 14.99 16.03 15.90 13.93 21.77 表 7 配对样本$t$-testTable 7 Paired-sample $t$-test$t$-test experiment $p-$值$\left(DI_R\right)$ $p-$值$\left(\rho \right)$ $p-$值$\left(SP\right)$ $t$-test (PNSGA-Ⅱ, A1) 0.000 0.000 0.007 $t$-test (PNSGA-Ⅱ, A2) 0.001 0.000 0.048 $t$-test (PNSGA-Ⅱ, NSGA-Ⅱ) 0.000 0.000 0.005 $t$-test (PNSGA-Ⅱ, SPEA2) 0.000 0.000 0.148 $t$-test (PNSGA-Ⅱ, TIPG) 0.000 0.000 0.014 可以发现, PNSGA-Ⅱ关于小、中、大三种规模的24个测试实例所获得的$DI_R$和$\rho$值均优于A1, 关于指标$SP$, PNSGA-Ⅱ关于17个实例所获得的结果优于A1, 这表明, 基于启发式算法的初始化方法能有效地改进算法的收敛性和分布均匀性, 大幅度地提高PNSGA-Ⅱ的求解质量, 表 7的统计结果也验证了该结论, 因此, 引入启发式算法进行种群初始化是合理有效的.和算法A2相比, PNSGA-Ⅱ关于18个实例所获得的$DI_R$优于A2, 关于23个实例, PNSGA-Ⅱ的$\rho $更优, 关于17个实例, PNSGA-Ⅱ的$SP$占优, 且关于所有实例的$SP$均值也优于A2, 可以发现, 基于问题性质的局部搜索, 可以有效地改善算法的收敛性, 一定程度上改善解的分布性. 表 7的统计结果表明, PNSGA-Ⅱ在收敛性和解的分布性方面的确优于A2, 总之, 基于问题性质的局部搜索合理有效.
4.4 与其他算法性能对比分析
由于DLCPMSP的相关研究很少, 缺乏现存的优化算法, 为此, 选择经典的多目标优化算法NSGA-Ⅱ[22]、强度Pareto进化算法2 (Strength Pareto evolutionary algorithm 2, SPEA2)[42]和禁忌增强迭代Pareto贪婪算法(Tabu-enhanced iterated Pareto greedy algorithm, TIPG)[43]作为对比算法.其中TIPG用来解决不相关PMSP, 对编码串调整, 在表示每台机器所加工的所有工件构成的片段中再引入$D-1$个0, 将工件片段划分为$D$个小片段, 同一小片段的工件加工速度一样, 这样就能应用于DLCPMSP.在PNSGA-Ⅱ中去掉启发式算法和基于问题性质的局部搜索后, 就是NSGA-Ⅱ. SPEA2的复制、交叉和变异与NSGA-Ⅱ一样. NSGA-Ⅱ和SPEA2是求解多目标问题的经典算法, 具有较强的搜索能力和优势.其中TIPG的参数设置依据文献[43], NSGA-Ⅱ和SPEA2依据文献[22, 42], $p_c=0.9$, $p_m=1/n$, $n$为工件数, 种群规模为100, SPEA2的外部档案大小为30.
如表 4和表 5所示, PNSGA-Ⅱ在指标$DI_R$和$\rho $方面优势明显, PNSGA-Ⅱ关于所有24个实例均取得了优于TIPG、NSGA-Ⅱ和SPEA2三种算法的$DI_R$, 关于$\rho$值, PNSGA-Ⅱ关于小、中、大三种规模的24个实例均取得了优于TIPG、NSGA-Ⅱ的结果, 仅有1个实例PNSGA-Ⅱ所得的$\rho$值小于SPEA2, 表 7的统计结果也验证了PNSGA-Ⅱ在收敛性方面的明显优势, 如图 3所示, 几种对比算法的解都远离PNSGA-Ⅱ所产生的非劣解, 因此, PNSGA-Ⅱ在收敛性方面具有较强的优势.
图 3 6种算法关于四个实例的非劣解分布Fig. 3 Distribution of non-dominated solutions of six algorithms on four instances从表 6可以发现, 关于分布均匀性指标$SP$, PNSGA-Ⅱ关于18个实例取得了优于NSGA-Ⅱ的结果, 在TIPG能给出有效结果的20个实例中, PNSGA-Ⅱ有17个实例的$SP$占优, 表 7的统计结果表明, PNSGA-Ⅱ在分布均匀性方面的优势是显著的, 只是和SPEA2相比, PNSGA-Ⅱ不占优, 但SPEA2的收敛性明显劣于PNSGA-Ⅱ, 因此, PNSGA-Ⅱ在分布均匀性方面具有一定的优势.
由于启发式算法和基于问题性质的局部搜索的引入, PNSGA-Ⅱ的收敛性得到明显改善, 分布均匀性也有所提高; 另外, 启发式算法也利用了一定的问题性质如调大机器加工速度, 对降低总延迟时间有利, 这表明在DLCPMSP优化求解过程中, 强化问题性质的作用, 对获得质量更高的解是有价值的, 因此, PNSGA-Ⅱ是解决DLCPMSP具有较强竞争力的方法.
5. 结论
分布式PMSP和低碳PMSP研究都取得了一定进展, 但很少同时考虑这两种问题.针对分布式低碳PMSP, 提出了一种基于问题性质的调度算法$-$PNSGA-Ⅱ以同时最小化总延迟时间和总能耗.首先将问题转换为扩展的低碳不相关PMSP以降低子问题的数量; 然后, 提出基于问题特征的两种启发式算法以初始化种群, 描述了问题的四种性质以及相关证明, 在此基础上, 提出了两种局部搜索方法以增强PNSGA-Ⅱ的局部搜索能力.通过仿真实验验证了启发式算法初始化种群和基于问题性质的局部搜索的有效性, 显示了PNSGA-Ⅱ在求解DLCPMSP方面较强的优势.未来将进一步深入研究分布式低碳调度问题包括分布式低碳混合流水车间调度问题, 并加强对基于问题性质的智能调度算法的设计与应用研究.
-
图 3 6种算法关于四个实例的非劣解分布
Fig. 3 Distribution of non-dominated solutions of six algorithms on four instances
表 1 参数各水平取值
Table 1 Factor levels of parameters
参数 水平 1 2 3 4 $p_c$ 0.80 0.85 0.90 95 $p_m$ 0.00 0.05 0.10 0.15 $N$ 60 90 120 150 
下载: 导出CSV
表 2 参数正交表及$DI_R$值
Table 2 Orthogonal array and $DI_R$ value
No. Factor $DI_R$ $p_c$ $p_m$ $N$ 1 1 1 1 20.94 2 1 2 2 13.42 3 1 3 3 6.012 4 1 4 4 6.519 5 2 1 2 19.85 6 2 2 1 13.82 7 2 3 4 6.721 8 2 4 3 6.000 9 3 1 3 11.89 10 3 2 4 8.126 11 3 3 1 10.68 12 3 4 2 6.536 13 4 1 4 11.13 14 4 2 3 8.531 15 4 3 2 8.199 16 4 4 1 14.84
下载: 导出CSV
表 3 各参数平均$DI_R$
Table 3 Average $DI_R$ of factors
水平 $p_c$ $p_m$ $N$ 1 11.72 15.95 15.07 2 11.60 10.97 12.00 3 9.308 7.903 8.108 4 10.68 8.474 8.124 Delta 2.415 8.050 6.962 排秩 3 1 2
下载: 导出CSV
表 4 种算法关于指标$DI_R$的对比
Table 4 Comparisons of six algorithms on metric $DI_R$
实例 PNSGA-Ⅱ A1 A2 NSGA-Ⅱ SPEA2 TIPG $2\times 10$ 1.009 5.989 3.753 13.50 1.147 29.95 $2\times 20$ 0.281 6.376 3.388 7.796 4.388 53.21 $2\times 30$ 0.297 6.272 3.361 9.465 5.240 47.96 $2\times 40$ 0.730 5.559 1.714 6.074 4.894 68.06 $3\times 40$ 0.074 6.583 0.676 7.432 6.269 63.24 $4\times 40$ 0.138 9.122 3.640 11.81 9.682 75.89 $2\times 50$ 0.933 9.606 2.045 8.024 12.73 72.65 $3\times 50$ 0.575 4.534 2.159 9.229 9.567 82.67 $4\times 50$ 0.045 7.053 2.243 8.349 7.639 83.56 $2\times 60$ 1.352 9.857 0.897 9.036 9.905 73.18 $3\times 60$ 0.866 5.166 1.608 6.861 7.685 73.38 $4\times 60$ 0.257 8.610 0.944 9.485 10.09 77.30 $2\times 80$ 1.851 8.616 0.871 9.539 14.04 83.09 $3\times 80$ 0.932 8.299 0.979 10.08 11.30 84.17 $4\times 80$ 1.017 14.53 0.594 16.18 18.06 98.23 $5\times 80$ 0.591 12.02 0.512 11.77 14.91 91.74 $2\times 100$ 1.611 5.917 1.996 6.714 10.73 76.21 $3\times 100$ 0.234 6.328 1.295 7.729 11.84 83.59 $4\times 100$ 0.083 7.440 1.079 11.53 15.13 88.09 $5\times 100$ 1.299 13.47 0.565 13.46 17.34 88.42 $2\times 200$ 1.664 21.42 2.198 28.48 36.18 $-$ $3\times 200$ 2.808 39.37 1.559 45.69 56.06 $-$ $4\times 200$ 0.640 33.89 1.886 38.96 48.04 $-$ $5\times 200$ 0.291 34.63 3.118 36.65 54.36 $-$ 均值 0.816 12.11 1.795 14.33 16.55 74.73
下载: 导出CSV
表 5 6种算法关于指标$\rho $的结果对比
Table 5 Comparisons of six algorithms on metric $\rho $
实例 PNSGA-Ⅱ A1 A2 NSGA-Ⅱ SPEA2 TIPG $2\times 10$ 0.444 0.111 0.000 0.000 0.556 0.000 $2\times 20$ 0.583 0.021 0.333 0.021 0.083 0.000 $2\times 30$ 0.975 0.025 0.000 0.000 0.012 0.000 $2\times 40$ 0.847 0.020 0.053 0.067 0.020 0.000 $3\times 40$ 0.910 0.010 0.080 0.000 0.010 0.000 $4\times 40$ 0.710 0.011 0.290 0.000 0.000 0.000 $2\times 50$ 0.718 0.137 0.076 0.046 0.031 0.000 $3\times 50$ 0.872 0.032 0.106 0.000 0.000 0.000 $4\times 50$ 0.896 0.015 0.104 0.000 0.000 0.000 $2\times 60$ 0.840 0.024 0.080 0.032 0.032 0.000 $3\times 60$ 0.822 0.059 0.129 0.000 0.000 0.000 $4\times 60$ 0.793 0.009 0.198 0.000 0.009 0.000 $2\times 80$ 0.551 0.059 0.324 0.074 0.000 0.000 $3\times 80$ 0.632 0.008 0.361 0.000 0.008 0.000 $4\times 80$ 0.646 0.015 0.354 0.000 0.000 0.000 $5\times 80$ 0.648 0.014 0.352 0.000 0.000 0.000 $2\times 100$ 0.759 0.036 0.015 0.197 0.000 0.000 $3\times 100$ 0.912 0.054 0.039 0.000 0.000 0.000 $4\times 100$ 0.897 0.015 0.088 0.004 0.000 0.000 $5\times 100$ 0.480 0.010 0.520 0.000 0.000 0.000 $2\times 200$ 0.853 0.041 0.086 0.024 0.000 $-$ $3\times 200$ 0.765 0.008 0.212 0.019 0.000 $-$ $4\times 200$ 0.852 0.004 0.148 0.000 0.000 $-$ $5\times 200$ 0.926 0.005 0.074 0.000 0.000 $-$ 均值 0.764 0.031 0.168 0.020 0.032 0.000
下载: 导出CSV
表 6 6种算法关于指标$SP$的结果对比
Table 6 Comparisons of six algorithms on metric $SP$
实例 PNSGA-Ⅱ A1 A2 NSGA-Ⅱ SPEA2 TIPG $2\times 10$ 1.127 3.207 4.554 14.68 2.784 7.470 $2\times 20$ 5.067 7.465 8.554 11.71 6.242 10.89 $2\times 30$ 5.036 13.77 10.95 8.816 14.22 18.55 $2\times 40$ 5.991 11.06 8.533 8.843 8.173 32.89 $3\times 40$ 6.477 8.199 10.12 9.624 6.823 13.56 $4\times 40$ 11.62 6.939 7.778 28.52 7.423 13.82 $2\times 50$ 10.94 6.345 14.26 13.60 16.32 21.35 $3\times 50$ 7.455 6.917 13.66 11.19 8.641 9.448 $4\times 50$ 8.089 9.014 27.52 10.73 8.114 24.12 $2\times 60$ 6.587 15.73 9.264 8.064 10.17 14.75 $3\times 60$ 9.447 12.27 17.74 13.22 8.957 13.86 $4\times 60$ 20.60 17.81 10.13 14.20 7.310 9.080 $2\times 80$ 13.98 13.50 8.977 10.19 6.923 36.90 $3\times 80$ 17.02 16.83 8.464 14.67 10.77 13.87 $4\times 80$ 4.881 17.26 10.34 17.97 7.760 12.32 $5\times 80$ 6.401 12.19 11.54 17.18 11.84 19.29 $2\times 100$ 11.78 12.92 17.65 37.68 38.74 101.1 $3\times 100$ 22.38 19.90 15.50 14.32 14.00 15.60 $4\times 100$ 10.31 16.27 12.09 10.93 20.60 26.28 $5\times 100$ 4.997 10.20 46.75 12.72 7.564 20.12 $2\times 200$ 20.37 22.10 53.72 16.08 41.22 $-$ $3\times 200$ 8.388 34.40 18.14 19.98 25.37 $-$ $4\times 200$ 23.68 36.78 18.37 23.00 32.56 $-$ $5\times 200$ 24.12 28.59 20.19 33.74 11.76 $-$ 均值 11.11 14.99 16.03 15.90 13.93 21.77
下载: 导出CSV
表 7 配对样本$t$-test
Table 7 Paired-sample $t$-test
$t$-test experiment $p-$值$\left(DI_R\right)$ $p-$值$\left(\rho \right)$ $p-$值$\left(SP\right)$ $t$-test (PNSGA-Ⅱ, A1) 0.000 0.000 0.007 $t$-test (PNSGA-Ⅱ, A2) 0.001 0.000 0.048 $t$-test (PNSGA-Ⅱ, NSGA-Ⅱ) 0.000 0.000 0.005 $t$-test (PNSGA-Ⅱ, SPEA2) 0.000 0.000 0.148 $t$-test (PNSGA-Ⅱ, TIPG) 0.000 0.000 0.014
下载: 导出CSV
-
[1] Cheng T C E, Sin C C S. A state-of-the-art review of parallel-machine scheduling research. European Journal of Operational Research, 1990, 47(3): 271-292 [2] 王凌, 王晶晶, 吴楚格.绿色车间调度优化研究进展.控制与决策, 2018, 33(3): 385-391 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=kzyjc201803001Wang Ling, Wang Jing-Jing, Wu Chu-Ge. Advances in green shop scheduling and optimization. Control and Decision, 2018, 33(3): 385-391 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=kzyjc201803001 [3] Li K, Zhang X, Leung J Y T, Yang S L. Parallel machine scheduling problems in green manufacturing industry. Journal of Manufacturing Systems, 2016, 38: 98-106 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=1b1d4c8bcc6bb0b76950e2d31d6daee2 [4] Wang S J, Wang X D, Yu J B, Ma S, Liu M. Bi-objective identical parallel machine scheduling to minimize total energy consumption and makespan. Journal of Cleaner Production, 2018, 193: 424-440 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=eb7bc4ea618ba7c377ab7388475f30e3 [5] Wu X Q, Che A D. A memetic differential evolution algorithm for energy-efficient parallel machine scheduling. Omega, 2019, 82: 155-165 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=a20a2c052677b71255873c01b1ffd8d8 [6] Zheng X L, Wang L. A collaborative multiobjective fruit fly optimization algorithm for the resource constrained unrelated parallel machine green scheduling problem. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018, 48(5): 790-800 http://ieeexplore.ieee.org/document/7605452 [7] Liang P, Yang H D, Liu G S, Guo J H. An ant optimization model for unrelated parallel machine scheduling with energy consumption and total tardiness. Mathematical Problems in Engineering, 2015, 2015: Article No. 907034 [8] Li Z T, Yang H D, Zhang S Q, Liu S Q. Unrelated parallel machine scheduling problem with energy and tardiness cost. The International Journal of Advanced Manufacturing Technology, 2016, 84(1): 213-226 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=c055c9d705e004ac44af028f54031ce3 [9] Che A D, Zhang S B H, Wu X Q. Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs. Journal of Cleaner Production, 2017, 156: 688-697 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=d073310b588cea264bb80c94121662c0 [10] 雷德明, 潘子肖, 张清勇.多目标低碳并行机调度研究.华中科技大学学报(自然科学版), 2018, 46(8): 104-109 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=hzlgdxxb201808020Lei De-Ming, Pan Zi-Xiao, Zhang Qing-Yong. Researches on multi-objective low carbon parallel machines scheduling. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2018, 46(8): 104-109 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=hzlgdxxb201808020 [11] Guo Z X, Ngai E W T, Yang C, Liang X D. An RFID-based intelligent decision support system architecture for production monitoring and scheduling in a distributed manufacturing environment. International Journal of Production Economics, 2015, 159: 16-28 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=df53b2567919bf7afc9a0e70cc824e01 [12] Lee C K, Shen Y A, Yang T, Tang A L. An effective two-phase approach in solving a practical multi-site order scheduling problem. Journal of the Chinese Institute of Industrial Engineers, 2011, 28(7): 543-552 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=10.1080/10170669.2011.637579 [13] Gnoni M G, Iavagnilio R, Mossa G, Mummolo G, Di Leva A. Production planning of a multi-site manufacturing system by hybrid modelling: A case study from the automotive industry. International Journal of Production Economics, 2003, 85(2): 251-262 http://www.sciencedirect.com/science/article/pii/S0925527303001130 [14] Timpe C H, Kallrath J. Optimal planning in large multi-site production networks. European Journal of Operational Research, 2000, 126(2): 422-435 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=5bcdacd526ebaf6e7dbfd1e00c3c92c5 [15] Behnamian J, Fatemi Ghomi S M T. A survey of multi-factory scheduling. Journal of Intelligent Manufacturing, 2016, 27(1): 231-249 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=e98c9e9ebb9852aba68e057b1b492b85 [16] 王凌, 邓瑾, 王圣尧.分布式车间调度优化算法研究综述.控制与决策, 2016, 31(1): 1-11 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=kzyjc201601001Wang Ling, Deng Jin, Wand Sheng-Yao. Survey on optimization algorithms for distributed shop scheduling. Control and Decision, 2016, 31(1): 1-11 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=kzyjc201601001 [17] Chen Z L, Pundoor G. Order assignment and scheduling in a supply chain. Operations Research, 2006, 54(3): 555-572 http://dl.acm.org/citation.cfm?id=1246577 [18] Terrazas-Moreno S, Grossmann I E. A multiscale decomposition method for the optimal planning and scheduling of multi-site continuous multiproduct plants. Chemical Engineering Science, 2011, 66(19): 4307-4318 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=52e76902534a683e4ca757e03e50bc3a [19] Behnamian J, Fatemi Ghomi S M T. The heterogeneous multi-factory production network scheduling with adaptive communication policy and parallel machine. Information Sciences, 2013, 219: 181-196 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=283e7956c2449a0f11d78199dee4914f [20] Behnamian J. Decomposition based hybrid VNS-TS algorithm for distributed parallel factories scheduling with virtual corporation. Computers & Operations Research, 2014, 52: 181-191 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=f25e3e0042841ec15565128b12cd35e5 [21] Behnamian J, Fatemi Ghomi S M T. Minimizing cost-related objective in synchronous scheduling of parallel factories in the virtual production network. Applied Soft Computing, 2015, 29: 221-232 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=f9cebf0fa53df4bc4f147bc6748eff9e [22] Deb K, Agrawal S, Pratap A, Meyarivan T. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-Ⅱ. In: Proceedings of the 6th International Conference on Parallel Problem Solving From Nature. Paris, France: Springer, 2000. 849-858 [23] Wang Y, Zhang J, Assogba K, Liu Y, Xu M Z, Wang Y H. Collaboration and transportation resource sharing in multiple centers vehicle routing optimization with delivery and pickup. Knowledge-Based Systems, 2018, 160: 296-310 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=3715dbf73dfa30fc4a3c51ec5813aaec [24] Vahdani B, Veysmoradi D, Shekari N, Mousavi S M. Multi-objective, multi-period location-routing model to distribute relief after earthquake by considering emergency roadway repair. Neural Computing and Applications, 2018, 30(3): 835-854 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=7e2dfdf089a6235c7258ca4f74ab5d18 [25] Nedjati A, Izbirak G, Arkat J. Bi-objective covering tour location routing problem with replenishment at intermediate depots: Formulation and meta-heuristics. Computers & Industrial Engineering, 2017, 110: 191-206 http://www.sciencedirect.com/science/article/pii/S0360835217302565 [26] Camara M V O, Ribeiro G M, Tosta M D C R. A pareto optimal study for the multi-objective oil platform location problem with NSGA-Ⅱ. Journal of Petroleum Science and Engineering, 2018, 169: 258-268 http://www.sciencedirect.com/science/article/pii/S0920410518304297 [27] Sun Y, Lin F H, Xu H T. Multi-objective optimization of resource scheduling in fog computing using an improved NSGA-Ⅱ. Wireless Personal Communications, 2018, 102(2): 1369-1385 doi: 10.1007/s11277-017-5200-5 [28] Afzalirad M, Rezaeian J. A realistic variant of bi-objective unrelated parallel machine scheduling problem: NSGA-Ⅱ and MOACO approaches. Applied Soft Computing, 2017, 50: 109-123 [29] Sofia A S, GaneshKumar P. Multi-objective task scheduling to minimize energy consumption and makespan of cloud computing using NSGA-Ⅱ. Journal of Network and Systems Management, 2018, 26(2): 463-485 doi: 10.1007/s10922-017-9425-0 [30] Wang H F, Fu Y P, Huang M, Huang G O, Wang J W. A NSGA-Ⅱ based memetic algorithm for multiobjective parallel flowshop scheduling problem. Computers & Industrial Engineering, 2017, 113: 185-194 [31] Yang Y, Cao L C, Wang C C, Zhou Q, Jiang P. Multi-objective process parameters optimization of hot-wire laser welding using ensemble of metamodels and NSGA-Ⅱ. Robotics and Computer-Integrated Manufacturing, 2018, 53: 141-152 http://www.zhangqiaokeyan.com/academic-journal-foreign_other_thesis/0204112722649.html [32] Wang S, Ali S, Yue T, Liaaen M. Integrating weight assignment strategies with NSGA-Ⅱ for supporting user preference multiobjective optimization. IEEE Transactions on Evolutionary Computation, 2018, 22(3): 378-393 http://ieeexplore.ieee.org/document/8123878 [33] 陈志旺, 白锌, 杨七, 黄兴旺, 李国强.区间多目标优化中决策空间约束、支配及同序解筛选策略.自动化学报, 2015, 41(12): 2115-2124 doi: 10.16383/j.aas.2015.c150218Chen Zhi-Wang, Bai Xin, Yang Qi, Huang Xing-Wang, Li Guo-Qiang. Strategy of constraint, dominance and screening solutions with same sequence in decision space for interval multi-objective optimization. Acta Automatica Sinica, 2015, 41(12): 2115-2124 doi: 10.16383/j.aas.2015.c150218 [34] 乔俊飞, 韩改堂, 周红标.基于知识的污水生化处理过程智能优化方法.自动化学报, 2017, 43(6): 1038-1046 doi: 10.16383/j.aas.2017.c170088Qiao Jun-Fei, Han Gai-Tang, Zhou Hong-Biao. Knowledge-based intelligent optimal control for wastewater biochemical treatment process. Acta Automatica Sinica, 2017, 43(6): 1038-1046 doi: 10.16383/j.aas.2017.c170088 [35] Wang J J, Wang L. A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020, 50(5): 1805-1819 [36] Wang L, Zheng X L. A knowledge-guided multi-objective fruit fly optimization algorithm for the multi-skill resource constrained project scheduling problem. Swarm and Evolutionary Computation, 2018, 38: 54-63 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=4d6268ff7cda6f1d66bebc9b2ce848ee [37] Karimi H, Rahmati S H A, Zandieh M. An efficient knowledge-based algorithm for the flexible job shop scheduling problem. Knowledge-Based Systems, 2012, 36: 236-244 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=c36d7e479c958023975a2ee40f793983 [38] Gao J Q, He G X, Wang Y S. A new parallel genetic algorithm for solving multiobjective scheduling problems subjected to special process constraint. The International Journal of Advanced Manufacturing Technology, 2009, 43(1-2): 151-160 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=5bd04960a3def4f838355a47fc3ba1d8 [39] Knowles J, Corne D. On metrics for comparing nondominated sets. In: Proceedings of the 2002 Congress on Evolutionary Computation. Honolulu, USA: IEEE, 2002. 711-716 [40] Lei D M. Pareto archive particle swarm optimization for multi-objective fuzzy job shop scheduling problems. The International Journal of Advanced Manufacturing Technology, 2008, 37(1-2): 157-165 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=2fc7730d349fa83780e3e8c9e79c6c13 [41] Wang L, Wang S Y, Zheng X L. A hybrid estimation of distribution algorithm for unrelated parallel machine scheduling with sequence-dependent setup times. IEEE/CAA Journal of Automatica Sinica, 2016, 3(3): 235-246 [42] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm. In: Proceedings of Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Lausanne, Switzerland, 2001. 95-100 [43] Lin S W, Ying K C, Wu W J, Chiang Y I. Multi-objective unrelated parallel machine scheduling: A Tabu-enhanced iterated Pareto greedy algorithm. International Journal of Production Research, 2016, 54(4): 1110-1121 期刊类型引用(7)
1. 卢弘，王耀南，乔非，方遒. 面向可持续生产中多任务调度的双重增强模因算法. 自动化学报. 2024(04): 731-744 . 
本站查看2. 王聪，余佳英，张宏立. 基于混合离散状态转移算法的多目标节能无等待流水车间调度. 系统仿真学报. 2024(10): 2345-2358 . 百度学术3. 耿凯峰，叶春明. 考虑多时间因素的绿色可重入混合流水车间调度问题. 计算机集成制造系统. 2023(01): 75-90 . 百度学术4. 荀洪凯，陶翼飞，张源，何李. 多目标启发式狼群算法求解不相关并行机分批调度问题. 信息与控制. 2023(01): 93-103+114 . 百度学术5. 李瑞，龚文引. 改进的基于分解的多目标进化算法求解双目标模糊柔性作业车间调度问题. 控制理论与应用. 2022(01): 31-40 . 百度学术6. 缪燕，王和平. 基于访问一体化算法的分布式实时数据库研究. 电子设计工程. 2022(21): 127-130+135 . 百度学术7. 曹劲松，熊福力. 基于离散教与学算法的分布式预制流水车间调度研究. 计算机测量与控制. 2021(12): 166-171+183 . 百度学术其他类型引用(11)
-
下载:
计量
- 文章访问数: 1783
- HTML全文浏览量: 223
- PDF下载量: 149
- 被引次数: 18
