浙江理工大学机械工程学院，浙江 杭州

收稿日期：2023年2月26日；录用日期：2023年5月1日；发布日期：2023年5月8日

摘要

在实际的柔性作业车间调度中，考虑工件运输时间和机器可选速度的影响，建立了优化最大完工时间、机器总负载和加工过程总能耗的多目标优化模型，并提出了一种改进的多目标Jaya算法用于求解该模型。结合问题的特点，采用了一种包含工序、机器和速度的三层编码和考虑运输时间和机器速度的插入式解码，并采用多种规则的混合策略的初始化种群方法以提高种群质量，然后根据不同情况设计多种不同的离散个体更新方式，并基于问题的特点设计了5种邻域结构，以提高算法的搜索能力。最后，在对基准算例改造并进行对比实验，验证了所提算法的可行性与有效性。

关键词

柔性作业车间调度，Jaya算法，运输时间，机器速度，多目标

Multi-Objective Jaya Algorithm for Solving Energy-Saving Flexible Job Shop Scheduling Problem

Deshang Zhang, Renwang Li

School of Mechanical Engineering, Zhejiang Sci-Tech University, Hangzhou Zhejiang

Received: Feb. 26^th, 2023; accepted: May 1^st, 2023; published: May 8^th, 2023

ABSTRACT

In the actual flexible job shop scheduling, considering the influence of transportation time and machine speed, a multi-objective optimization model is established to optimize the maximum completion time, machine tool load and total energy consumption of the machining process, and an improved multi-objective Jaya algorithm is proposed for solving the model, considering the effects of workpiece transport time and machine optional speed on the scheduling results. Combining the characteristics of the problem, a three-level coding containing process, machine and speed and an insertion decoding considering transport time and machine speed, and a hybrid strategy of multiple rules are used to initialise the population approach to improve the population quality, and then a variety of different discrete individual update methods are designed according to different situations, and five neighbourhood structures are designed based on the characteristics of the problem to improve the search capability of the algorithm. Finally, the feasibility and effectiveness of the proposed algorithm is verified after modifying the benchmark algorithm and conducting comparison experiments.

Keywords:Flexible Job Shop Scheduling, Jaya Algorithm, Transportation Time, Machine Speed, Multi-Objective

Copyright © 2023 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem, FJSP)是制造领域内广泛存在的调度问题，自其在1990年被Brucker和Schlie提出以来，大多数文献聚焦于完工时间、机器负载、成本、拖期等生产经济目标 [1] [2] ，而忽视了环境上的目标。近年来，能源消耗和环境污染问题日益严峻，学者们已经逐渐重视能耗、碳排放等绿色生产目标。针对绿色低碳的FJSP，包哲人等 [3] 以能耗、完工时间、生产成本和质量为目标，提出了一种改进的离散蝙蝠算法。Jiang等 [4] 设计了一种改进的非洲水牛算法。上述考虑能耗的FJSP的研究，对企业生产节能有一定的指导价值，但是并没有考虑工件运输时间和机器可选加工速度以及它们造成的能耗影响。

实际生产过程中，每个工件存在着多道工序，而各道工序往往需要在不同的机器上加工，因此在加工过程中需要对工件进行运输，考虑工件运输的FJSP研究是有意义的。针对考虑工件运输时间的FJSP，Karimi等 [5] 提出了一种基于模拟退火的局部搜索与帝国主义竞争算法相结合的自适应算法进行求解。陈魁等 [6] 将离散粒子群算法中引入邻域搜索策略和竞争学习策略。在实际车间中，机器可以根据实际情况设置不同的加工速度进行处理，对应着不同的时间和能耗。针对考虑速度的FJSP研究，李益兵等 [7] 提出了一种改进的人工蜂群算法进行求解。Luo等 [8] 设计了引入交叉和变异算子的灰狼优化算法求解可变加工速度的FJSP。

综上所述，很多学者研究了考虑工件运输时间或者机器可选速度的FJSP，但是同时考虑工件运输时间和机器加工速度的节能FJSP的研究仍然较少，而考虑这些因素更为符合实际生产环境。因此，本文针对此类问题，构建多目标节能调度模型，优化最大完工时间、机器总负载和加工过程总能耗，并提出了一种改进的多目标Jaya算法(Improved Multi-Objective Jaya Algorithm, IMOJA)用于求解该模型。

2. 问题描述与数学模型

2.1. 问题描述

本文所研究的调度问题描述：有n个工件集 $J=\left\{J_1,J_2,\cdots ,J_n\right\}$ 需要合理安排在m台机器集 $M=\left\{M_1,M_2,\cdots ,M_m\right\}$ 上加工，每个工件均有 $n_i$ 道并确定顺序的工序集 $O_{Ji}=\left\{O_{J1},O_{J2},\cdots ,O_{Jini}\right\}$ ，机器选择可以有多个。每台机器有q种不同的速度档位 $v=\left\{v_1,v_2,\cdots ,v_q\right\}$ 可供选择，选择的速度档位越大，加工时间越短，但相应的机器能耗也越大，即对机器 $M_k$ 的两个加工速度 $v_{ka}$ 和 $v_{kb}$ ，如果 $v_{ka}>v_{kb}$ ，则加工时间 $T_{vka}<T_{vkb}$ ，单位时间内平均加工能耗 $P{L}_{vka}>P{L}_{vkb}$ 。同一工件的两道相邻工序在不同的机器上加工时存在运输时间，运输时间已知且可以不同。同时，本文针对该问题做出如下假设：

1) 各工件和机器在零时刻即可用。

2) 一台机器一次只能加工一个工件。

3) 一个工件在同时不能被多台机器加工。

4) 工序加工时不能被停止。

5) 每道工序只能被一台机器加工一次。

6) 同一工件的工序顺序固定，不同工件的工序之间不相关。

7) 一旦机器启动，直到机器上的所有操作都完成后才能关闭。

8) 工序在机器上开始加工后，速度不可调整。

9) 所有工件的第一道工序之前和最后一道工序之后不计算运输时间，运输资源不作限制。

2.2. 模型建立

本文所涉及的变量符号及其含义如表1所示。

表1. 变量符号及其含义

2.2.1. 优化目标

1) 最大完工时间( $C_{\max }$ )：是车间生产效率的直观体现。

$\min C_{\max }\text{}=\text{}\max \text{}\text{}\left\{C_i|1\le i\le n\right\}$ (1)

2) 机器总负载(TL)：是车间机器资源利用率的体现。

$\min TL=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}\underset{j=1}{\overset{n_i}{{\displaystyle \sum }}}\underset{k=1}{\overset{m}{{\displaystyle \sum }}}\underset{e=1}{\overset{q}{{\displaystyle \sum }}}{T}_{ijkve}{X}_{ijkve}$ (2)

3) 总能耗(E)：是车间节能生产，绿色效益的目标，本文研究所研究的能耗包括加工能耗(E_l)、空载能耗(E_n)和运输能耗(E_t)。

$\min E\text{}=\text{}{E}_l+E_n+E_t$ (3)

$El=\underset{i=1}{\overset{n}{{\displaystyle \sum }}}\underset{j=1}{\overset{n_i}{{\displaystyle \sum }}}\underset{k=1}{\overset{m}{{\displaystyle \sum }}}\underset{e=1}{\overset{q}{{\displaystyle \sum }}}{T}_{ijkve}{X}_{ijkve}P{L}_{kve}\text{}$ (4)

$E_n=\underset{k=1}{\overset{m}{{\displaystyle \sum }}}\left(T{C}_k\text{}-\text{}T{S}_k\text{}-\text{}\underset{i=1}{\overset{n}{{\displaystyle \sum }}}\underset{j=1}{\overset{n_i}{{\displaystyle \sum }}}\underset{e=1}{\overset{q}{{\displaystyle \sum }}}{T}_{ijkve}{X}_{ijkve}\text{}\right)P{N}_k$ (5)

$E_t\underset{i=1}{\overset{n}{{\displaystyle =\sum }}}\underset{j=1}{\overset{n_i}{{\displaystyle \sum }}}\underset{k=1}{\overset{m}{{\displaystyle \sum }}}\underset{l=1}{\overset{m}{{\displaystyle \sum }}}T{t}_{kl}{Z}_{ijkl}PT$ (6)

2.2.2. 约束条件

1) 一台机器同时至多加工一道工序。

$C_{ijk}\text{}\le \text{}{S}_{ghk}\text{}+\text{}P\text{}\times \text{}\left(1\text{}-\text{}{Y}_{ijghk}\right)\text{,}\text{}\forall i,j,g,h,k$ (7)

2) 同一工件的工序顺序约束。

$S_{ijl}\text{}\ge \text{}{C}_{i\left(j-1\right)k}\text{}+\text{}T{t}_{kl}{Z}_{ijkl},\text{}\forall i,j>1,k,l$ (8)

3) 工序加工不可被停止。

$C_{ijk}\text{}-\text{}{S}_{ijk}\text{}=\text{}{T}_{ijkve},\text{}\forall i,j,k$ (9)

4) 工序在机器上不同速度档位的加工时间。

$T_{ijkve}\text{}=\text{}{t}_{ijk}\text{}/v_e,\forall i,j,k,e$ (10)

5) 每道工序有且仅有一台机器加工一次。

$\underset{k=1}{\overset{m_{ij}}{{\displaystyle \sum }}}\underset{e=1}{\overset{q}{{\displaystyle \sum }}}{X}_{ijkve}\text{}=\text{}1,\text{}\forall i,j$ (11)

6) 工序的紧前或紧后工序约束。

$\underset{i=1}{\overset{n}{{\displaystyle \sum }}}\underset{j=1}{\overset{n_i}{{\displaystyle \sum }}}\underset{k=1}{\overset{m_{ij}}{{\displaystyle \sum }}}{Y}_{ijghk}\text{}\le \text{}1,\text{}\forall g,h$ (12)

$\underset{g=1}{\overset{n}{{\displaystyle \sum }}}\underset{h=1}{\overset{n_g}{{\displaystyle \sum }}}\underset{k=1}{\overset{m_{gh}}{{\displaystyle \sum }}}{Y}_{ijghk}\text{}\le \text{}\text{}1,\text{}\forall i,j$ (13)

7) 每道工序至多被运输一次。

$\underset{k=1}{\overset{m}{{\displaystyle \sum }}}\underset{l=1}{\overset{m}{{\displaystyle \sum }}}{Z}_{ijkl}\text{}\le \text{}1,\text{}\forall i,j>1$ (14)

3. 改进的多目标Jaya算法求解FJSP

3.1. 传统Jaya算法

Jaya算法是由Rao [9] 在2016年提出的一种简单高效的新型元启发式算法。Jaya在梵文中是“胜利”的意思，因此，Jaya算法是基于击败最弱的对手并试图找到最好的获胜路径的想法而提出的。Jaya算法由于只需设置少量的公共参数，如种群规模和迭代次数，具有很强的适应性，很容易应用于求解各种复杂优化问题 [10] [11] [12] 。

Jaya算法控制个体趋优避劣，不断向最优解靠拢，而远离最劣解，其解的位置更新公式如下：

$V_i^{t+1}\text{}=\text{}{X}_i^t\text{}+\text{}{r}_1\cdot \left(X_{\text{Best}}^t\text{}-\text{}\left|X_i^t\right|\right)-\text{}{r}_2\cdot \left(X_{\text{Worst}}^t\text{}-\text{}\left|X_i^t\right|\right)$ (15)

$X_i^{t+1}\text{}=\text{}\{\text{}\begin{array}{l}{X}_i^t,\text{if}F\left(X_i^t\right)\text{}<\text{}F\left(V_i^{t+1}\right)\hfill \\ V_i^{t+1},\text{else}\hfill \end{array}$ (16)

其中， $X_i^t$ 是第t次迭代种群中的第i个个体； $X_{\text{Best}}^t$ 和 $X_{\text{Worst}}^t$ 分别是第t次迭代种群中的最优解和最劣解； $r_1$ 和 $r_2$ 是[0, 1]中的均匀分布的两个随机数； $+r_1\cdot \left(X_{\text{Best}}^t-\left|X_i^t\right|\right)$ 表示解个体接近最优解； $-r_2\cdot \left(X_{\text{Worst}}^t-\left|X_i^t\right|\right)$ 表示解个体远离最劣解； $F(\cdot )$ 是目标函数适应度值，如果更新后解 $V_i^{t+1}$ 的目标值不劣于 $X_i^t$ ，则接受 $V_i^{t+1}$ 替换 $X_i^t$ ，反之则保留 $X_i^t$ 。

3.2. 编码与解码

本文所研究的调度问题包含了工序排序(Operation Sequencing, OS)、机器分配(Machine Allocation, MA)、速度选择(Speed Selection, SS)这三个子问题，因此，采用三层编码的方式，每层编码长度一致，均等于所有工件的工序数总和 ${{\displaystyle {\sum }_{i=1}^{n}n}}_i$ 。OS表示工序的编码，确定工件各工序的加工顺序；MA表示机器的编码，确定每个工序对应的加工机器。SS表示速度的编码，确定每个工序使用的机器速度等级。

以4个工件在3个机器上加工，每个工件均含2道工序的问题为例，图1为其中一个可行个体编码。在OS编码中，编码数字是工件序号，序号重复的次数表示该工件的所处的工序数。例如在图1的OS编码中的第一个“2”表示 $O_{21}$ ，第二个“2”表示 $O_{22}$ ，以此类推。在MA编码中，采用文献 [13] 中的编码方式，MA编码向量的顺序不是与OS编码的顺序对应，而是按照每个工件工序顺序，编码上的数字表示了对应工序的可选机器集中的索引，而非机器编号。例如在图1的MA编码中的第一个“1”表示工序 $O_{11}$ 在可选机器集 $\left\{M_1,M_2,M_3\right\}$ 索引为1的机器 $M_1$ 加工，以此类推。在SS中，编码顺序与MA编码一致，编码值即为对应工序在机器上的加工速度等级。由此可以确定工序排序、机器分配和速度选择，得到调度方案。

图1. 个体编码示例

对于解码方法，针对问题的特点，本文设计了一种插入式的主动解码方法，解码时考虑工件运输时间和机器速度下加工时间的约束。在满足对应机器速度下的工序加工时间和工件在不同机器间的运输时间的要求下，将同一机器上加工的工序左移插入合适的空隙时间，从而将每个工序从左往右尽可能紧凑地安排在机器上加工，从而减小加工时间空隙，提高机器效率和减小能耗。插入式解码的伪代码如算法1所示。

3.3. 种群初始化

一个良好的初始种群有助于群体智能优化算法产生良好的结果。为了获得多样化的初始种群，本文基于工序、机器和速度的三层编码设计了以下混合策略生成初始种群。对于OS编码，采取随机生成的方式。对于MA编码，在Zhang等 [14] 提出的全局搜索、局部搜索和随机选择的混合策略的基础上，考虑工件在不同机器上的运输时间，设计整体工作时间最小和随机分配策略来初始化机器编码。与全局搜索相似，整体工作时间最小策略在为工件各个工序按工艺路线安排加工机器时，综合工序在机器上的加工时间和在机器之间的运输时间择优选择机器安排加工。对于SS编码，设计了加工速度较小、较大和随机的策略。选择较小的加工速度有利于减小机器加工的能耗，而较大的速度缩短了工序的加工时间从而减小最大完工时间。

3.4. Pareto排序和外部档案

3.4.1. Pareto排序

不同于单目标问题可以直接比较解的适应度值确定解的优劣，在多目标优化问题中，需要对种群进行Pareto排序确定个体的非支配等级。Pareto支配可以描述为，当且仅当一个解x的所有优化目标值均不劣于另一个解y，且至少存在一个目标值优于y，则称x支配y。通过Pareto支配，评估不同个体之间的支配关系将种群逐级划分为若干个非支配等级。等级越小的个体越优秀，等级为1的所有个体组合成Pareto最优解集，对于同Pareto等级的个体，根据拥挤距离比较解的优劣，拥挤距离较大的解为优解。拥挤距离的计算公式如下式所示：

$Di={\displaystyle \underset{n=1}{\overset{N}{\sum }}\frac{f_n\left(i+1\right)-f_n\left(i-1\right)}{f_n\left(\max \right)-f_n\left(\min \right)}}$ (17)

其中，N是优化目标总个数； $f_n\left(\max \right)$ 和 $f_n\left(\min \right)$ 是第n个目标的最大值与最小值； $f_n\left(i+1\right)$ 和 $f_n\left(i-1\right)$ 是与第i个解相邻的两个位置在第n个目标值。

3.4.2. 外部档案

为了防止迭代过程中非支配解的丢失，构建一个固定数量的外部档案用于保存非支配解集。首先，对初始种群进行Pareto排序，将所有非支配解储存到外部档案中，之后在每次迭代过程中，将当前代的非支配解集与外部档案中的所有其他解混合，进行Pareto排序，形成新的非支配解集储存到外部档案中。

3.5. 个体更新

为了将传统Jaya算法适用于求解FJSP问题，本文根据问题的特点和个体不同的情况设计了以下的更新策略，从而获得新的个体。

1) 基于Jaya算法趋优避劣的思想，按照文献 [15] 的方法，通过删除 $X_i^t$ 与 $X_{\text{Worst}}^t$ 相同的序列，同时使用 $X_{\text{Best}}^t$ 相应的序列替换生成新的候选解 $X_{i,1}^t$ 。该方式的OS编码的更新如图2所示，MA和SS编码的更新如图3所示。

图2. 方式(1)的OS编码更新

图3. 方式(1)的MA和SS编码更新

2) 保留 $X_i^t$ 与 $X_{\text{Best}}^t$ 相同的序列，删除两者不同的序列，再使用不同于 $X_{\text{Worst}}^t$ 相应的序列插入删除的部分，生成新的候选解 $X_{i,2}^t$ 。该方式的OS编码的更新如图4所示，MA和SS编码的更新如图5所示。

3) 为了提高算法解的多样性，将当前解 $X_i^t$ 与外部档案中的随机选择的解 $X_{\text{Archive}}^t$ 进行交叉操作，生成新的候选解 $X_{i,3}^t$ , $X_{i,4}^t$ 。OS编码使用POX交叉，MA和SS编码使用MPX交叉，该方式的OS编码的更新如图6所示，MA和SS编码的更新如图7所示。

图4. 方式(2)的OS编码更新

图5. 方式(2)的MA和SS编码更新

图6. OS编码POX交叉更新

图7. MA和SS编码MPX交叉更新

运用上述方式更新时，存在当前解 $X_i^t$ 与最优解 $X_{\text{Best}}^t$ 或者最劣解 $X_{\text{Worst}}^t$ 完全相同的情况，会生成相同的解导致陷入局部最优，因此，对完全相同的情况重新初始化生成新的候选解。对以上新生成的候选解 $X_{i,1}^t$ ， $X_{i,2}^t$ ， $X_{i,3}^t$ ， $X_{i,4}^t$ ，以及原解 $X_i^t$ ，选择最优解作为下一代的个体 $X_i^{t+1}$ 。

3.6. 邻域搜索

为了更好地提升个体的质量，本文引入邻域搜索策略用于每次迭代种群的前20%的个体。本文设计以下5种邻域结构获得新解，如果新解优于原解，则进行替换。1) 随机选择工序编码中一段不完全相同的序列，进行逆序操作，生成新解。2) 随机选择负载较大的机器上的一道工序移动到别的可选机器上，生成新解。3) 随机选择运输时间较长的两道相邻工序，为后一道工序选择运输时间较小的机器，生成新解。4) 随机选择速度较大的一道工序降低速度，生成新解。5) 随机选择速度较小的一道工序增大速度，生成新解。

3.7. IMOJA整体流程

本文针对所研究FJSP问题特点，设计的多目标Jaya算法伪代码如算法2所示。

4. 仿真实验与结果分析

4.1. 测试用例

本研究选择Brandimarte数据集算例(MK01~MK10)，并对其进行了拓展以满足本研究问题的要求。分别为每个机器设置了5个离散速度选择 $v=\left\{1.0,1.5,2.0,2.5,3.0\right\}$ ，将原始基准中定义的加工时间作为最低速度下的正常加工时间。机器 $M_k$ 的在速度 $v_e$ 时的单位时间内平均加工能耗 $P_{kve}=r\cdot v{e}^2$ ，单位时间内平均空载能耗 $P{N}_k=r/4$ ，其中 $r\in \left[3,6\right]$ 。机器间的工件运输时间 $T{t}_{kl}\in \left[1,5\right]$ ，运输产生的单位能耗 $PT=2$ 。

4.2. 评价指标

为了衡量算法的性能，本文使用覆盖率指标C [16] 和反世代距离指标IGD [17] ，计算公式如下。

$C\left(S_1,\text{}{S}_2\right)\text{}\text{}=\text{}\frac{\left|\text{}\left\{x\text{}\in \text{}{S}_2|\exists y\text{}\in \text{}{S}_1,y\text{}\prec \text{}x\right\}\right|}{\left|S_2\right|}$ (18)

其中， $S_1,S_2$ 是两个算法所得的Pareto最优解集； $\left|S_2\right|$ 是S₂中解的数量； $y\text{}\prec \text{}x$ 表示y支配x。C(S₁, S₂)越大，代表S₂中的解被S₁中至少一个解支配的越多，即得到S₁的算法越优质。

$IGD\left(S,\text{}{S}^{*}\text{}\right)\text{}=\text{}\frac{1}{\left|S^{*}\right|}{\displaystyle \underset{i=1}{\overset{\left|S^{*}\right|}{\sum }}{D}_i}$ (19)

其中，S是算法所得的Pareto最优解集， $S^{*}$ 是真正的Pareto最优解集； $\left|S^{*}\right|$ 是真实解集 $S^{*}$ 中解的数量；D_i为 $S^{*}$ 中第i个解到算法所得解集S中最短的欧氏距离，在计算D_i时，因为三个目标函数的量级不同，需要先将三个目标值归一化处理， $F_i=\left(f_i-f_i\min \right)/\left(f_i\max -f_i\min \right),i=1,2,3$ ，其中 $f_i\max$ 和 $f_i\min$ 是 $S^{*}$ 中对应目标的最大值和最小值。IGD越小，代表算法收敛性和多样性的综合性能越优秀。因为 $S^{*}$ 实际上是未知的，所以本文研究中 $S^{*}$ 由实验时各算法的S综合形成。

4.3. 对比实验

本文以著名的NSGA-II [18] 、SPEA2 [19] 进行实验对比以验证本文算法的可行性与有效性。三个算法均采用Matlab2020b编程实现，各算例在3.20 GHz处理器，8.0 GB内存的电脑上进行操作。所有算法的种群规模设为50，最大迭代次数设为100；IMOJA和SPEA2的外部档案规模设为50；NSGA-II和SPEA2的交叉率和变异率分别设置为0.8和0.1。每个算例均重复独立运行10次。

表2是不同算法在三个优化目标最优值的结果对比，最优值加粗显示。从表2可以看出，在这10个算例上，IMOJA在最大完工时间、机器总负载、总能耗三个优化目标函数值上，最优值结果均要优于NSGA-II和SPEA2，在各个方向的寻优都取得了更好的效果，说明了IMOJA具有更好的收敛性，可以取得更好的解。

表2. 不同算法的各优化目标最优值结果对比

不同算法的C指标和IGD指标的对比结果如表3和表4所示。表3中对覆盖率为1和0的数据进行加粗显示，表4中IGD最优值加粗显示。从表3可以看出，C(IMOJA, NSGA-II)在6个算例上等于1，在其它4个算例上很接近1，而C(NSGA-II, IMOJA)在7个算例上等于0，在其它3个算例上很接近0，这说明IMOJA获得的非支配解集可以覆盖NSGA-II绝大多数的解，而NSGA-II获得的解集难以覆盖IMOJA；C(IMOJA, SPEA2)在4个算例上等于1，在剩余的算例上很接近1，都大于0.9，而C(SPEA2, IMOJA)在7个算例上等于0，在剩余算例上很接近0，都小于0.007，这说明IMOJA获得的非支配解集可以覆盖SPEA2绝大多数的解，而SPEA2获得的解集难以覆盖IMOJA。从表4可以看出，IMOJA的IGD值在所有算例上都取得比NSGA-II和SPEA2更小的值，在数量级上远远小于NSGA-II和SPEA2的IGD值，且在4个算例上等于0，这说明IMOJA具有更优秀的收敛性和多样性。

表3. 不同算法的C指标的对比结果

表4. 不同算法的IGD指标的对比结果

图8展示了MK09算例下各算法运行综合所得的Pareto最优前沿以及三视图。图8中，“*”表示IMOJA取得的Pareto前沿，“◊”表示NSGA-II，“◁”表示SPEA2，可以看出，IMOJA所得Pareto最优前沿在三个坐标轴方向都取得了比NSGA-II和SPEA2更好的结果，说明IMOJA可以获得更优的Pareto最优前沿。图9~11展示了求解MK05算例时，三种算法取得最优完工时间时的甘特图，MK05有15个工件4台机器106道工序组成。从图9~11中可以看出，IMOJA取得的调度方案机器间空隙更少，尽管NSGA-II和SPEA2使用了本文所提的种群初始化方法和插入式解码方法，但是它们的调度方案机器间的空隙更多，完工时间还是要比IMOJA的大，这说明了IMOJA可以获得更好的调度方案。IMOJA取得的解(C_max, TL, E)为(74.73, 274.73, 7897.61)，NAGA-II为(80.00, 281.07, 8160.74)，SPEA2为(83.37, 300.27, 7491.87)，在最小完工时间的调度方案上，IMOJA取得了更小的完工时间的方案，且在三个目标上都优于NSGA-II的结果，说明了IMOJA算法更具优势。

图8. MK09的各算法Pareto前沿图与三视图

图9. IMOJA求解MK05的甘特图

图10. NSGA-II求解MK05的甘特图

图11. SPEA2求解MK05的甘特图

5. 结语

本文针对传统的柔性车调度问题，考虑了工件运输时间和机器可选速度的实际因素，建立了以最小化最大完工时间、机器总负载和加工过程总能耗为优化目标的多目标优化模型，并提出了一种改进的多目标Jaya算法用于该模型。在该算法中，采用了工序、机器和速度的三层编码和考虑运输时间与机器速度的插入式解码方法，采用了多种策略混合生成初始种群，设计了多种不同的个体更新方式，并设计了5种邻域结构，以提高算法的局部搜索能力。最后，对传统的FJSP算例进行改造，通过对比实验，验证了了本文提出的IMOJA的有效性，可以为车间生产提供指导。

在未来的研究中，将考虑更多实际生产环境因素，如机器故障、新工件插入、运输资源限制等进行研究；以及考虑交货期、生产成本等其他优化目标进行研究。

基金项目

浙江省2023年度“尖兵”“领雁”研发攻关计划(2022C01SA111123)，国家自然科学基金资助项目(51475434)。

文章引用

张德尚,李仁旺. 多目标Jaya算法求解节能柔性作业车间调度问题
Multi-Objective Jaya Algorithm for Solving Energy-Saving Flexible Job Shop Scheduling Problem[J]. 建模与仿真, 2023, 12(03): 1850-1865. https://doi.org/10.12677/MOS.2023.123171

参考文献