欢迎访问《控制理论与应用》期刊网站！

考虑双资源约束多转速的绿色柔性作业车间调度研究

doi: 10.7641/CTA.2025.50031

王玉芳^1,2,3 ，章殿清¹ ，华晓麟¹ ，张毅¹ ，葛师语¹

1. 南京信息工程大学自动化学院, 江苏南京 210044

2. 南京信息工程大学大气环境与装备技术协同创新中心, 江苏南京 210044

3. 南京信息工程大学气象能源利用与控制工程技术研究中心, 江苏南京 210044

基金项目: 国家自然科学基金项目(51705260)资助.

详细信息

作者简介

王玉芳博士,副教授,研究生导师,研究方向为智能优化算法及生产车间调度,E-mail: wangyufang@nuist.edu.cn;

章殿清硕士研究生,研究方向为智能优化算法及生产车间调度,E-mail: 842101808@qq.com;

华晓麟硕士研究生,研究方向为智能优化算法及生产车间调度,E-mail: 1922163398@qq.com;

张毅硕士研究生,研究方向为智能优化算法及生产车间调度,E-mail: 874434253@qq.com;

葛师语硕士研究生,研究方向为智能优化算法及生产车间调度,E-mail: 2542033071@qq.com.

通信作者

章殿清，E-mail: 842101808@qq.com;Tel:+8613770289678.

Research on green flexible job-shop scheduling considering dual-resource constraints and multiple-speed

WANG Yu-fang^1,2,3 ， ZHANG Dian-qing¹ ， HUA Xiao-lin¹ ， ZHANG Yi¹ ， GE Shi-yu¹

1. School of Automation, Nanjing University of Information Science & Technology, Nanjing jiangsu 210044 , China

2. Collaborative Innovation Center of Atmospheric Environment and Equipment Technology (CICAEET), Nanjing University of Information Science & Technology, Nanjing jiangsu 210044 , China

3. Engineering Research Center on Meteorological Energy Using and Control (C-MEIC), Nanjing University of Information Science & Technology, Nanjing jiangsu 210044 , China

Funds: Supported by the National Natural Science Foundation of China (51705260).

摘要

考虑实际生产车间机器不同转速产生能耗差异及精工序的生产需求, 构建以最大完工时间和机器总能耗为优化目标的双资源约束多转速绿色柔性作业车间调度模型, 并提出一种动态学习人工蜂群算法进行求解. 采用混合初始化获取初始种群, 提升算法的进化起点.在雇佣蜂完成搜索之后, 引入新蜂种学习蜂, 学习优秀蜜源的基因, 降低搜索的随机性, 提高搜索精度, 并采用Q学习算子对学习概率进行自适应优化, 保证蜜源多样性的同时加强算法的全局搜索能力. 跟随蜂阶段设计一种动态邻域搜索策略, 加入基于变速及平衡工人工作时长的邻域结构, 提高跟随蜂的局部搜索能力. 通过不同算法对拓展算例的对比验证所提算法的优越性.

关键词

双资源约束 / 多转速 / 绿色柔性车间调度 / 多目标优化 / 人工蜂群算法 / Q学习

Abstract

Considering the energy consumption differences caused by different machine speeds in actual production workshops and the production requirements of fine processes, a dual-resource-constrained multi-speed green flexible jobshop scheduling model is constructed, with the optimization objectives of maximizing completion time and total machine energy consumption. A learning bee colony algorithm is proposed to solve the model. Using hybrid initialization to obtain the initial population and improve the evolutionary starting point of the algorithm. After the employment bees complete the search, a new bee species is introduced to learn the genes of excellent honey sources, reduce the randomness of the search and improve the search accuracy. Adaptive optimization of learning probabilities is carried out by using the Q-learning operator to ensure the diversity of nectar sources while enhancing the global search capability of the algorithm. A dynamic neighborhood search strategy is designed for the following-bee stage, and a neighborhood structure based on variable speed and balancing the working hours of workers is incorporated to enhance the local search ability of the following bees. The superiority of the proposed algorithm is verified by comparing different algorithms on the extended standard examples.

Keywords

dual-resource constraints / multi-speed / green flexible job-shop scheduling / multiobjective optimization / artificial bee colony algorithm / Q-learning

1 引言 2 数学模型 3 动态学习人工蜂群算法 3.1 编码与解码 3.2 混合初始化 3.3 雇佣蜂阶段 3.4 学习蜂阶段 3.4.1 学习操作 3.4.2 Q学习算子 3.5 跟随蜂阶段 3.6 算法复杂度 4 仿真实验 4.1 测试算例生成 4.2 模型有效性验证 4.3 策略有效性验证 4.4 算法性能验证 5 结论

1 引言

随着全球可持续发展战略的推进，绿色制造和柔性生产已成为现代制造业的重要发展趋势^[1-2] . 为了在减少环境污染的同时获得最大的经济社会效益，诸多学者对绿色柔性作业车间调度问题（green flexible job-shop scheduling problem，GFJSP）展开研究 ^[3-5] . 大部分GFJSP的研究只考虑了加工能耗与空闲能耗等因素，未考虑机器运转速度对完工时间以及能耗的影响. 而机器的运转速度显著影响生产效率、成本和能源消耗. 多数机器具备多档可调转速，加工时间与能耗随之变化. 合理选择转速有助于提升效率，降低成本并保证质量. 因此，在制定调度策略时应考虑多转速约束，以优化生产调度性能. 在航空结构件等高精度产品的生产过程中，部分工件包含精工序，需分配工人操作辅助机器完成加工，因此，须在机器约束的基础上考虑精工序加工的工人选择约束. 双资源约束多转速绿色柔性车间调度问题（dual-resource-constrained multi speed GFJSP，DRCMSGFJSP）作为柔性车间调度的拓展，需要同时考虑机器和工人两种关键资源的可用性 ^[6] .

DRCMSGFJSP需要综合考虑工序排序、机器选择、机器转速选择以及精工序工人选择4个子问题，相较于GFJSP具有更高的复杂度. 考虑到转速变化带来的加工时间与能耗可变性及绿色调度的多目标优化特性，本文采用全局搜索能力强、参数设置简单、鲁棒性强的人工蜂群算法（artificial bee colony，ABC）来求解DRCMSGFJSP. ABC算法通过模拟蜜蜂采蜜的行为，利用信息共享和局部搜索等策略，在较短的时间内找到全局最优解，并且具有较高的鲁棒性和可靠性，因此在许多优化问题中被广泛应用，尤其适合解决DRCMSGFJSP这类复杂且目标多样的问题. 然而，经典ABC算法虽然具有出色的全局搜索能力，但收敛速度慢，搜索精度低 ^[7] . 因此，近年来诸多学者针对上述问题对ABC算法进行了改进. 王移民和雷德明 ^[8]针对考虑工厂适用性和附加资源的分布式两阶段混合流水车间调度问题，提出了一种反馈人工蜂群算法求解该问题. Li等 ^[9] 将强化学习与ABC算法结合，通过强化学习解决批量流柔性车间调度问题中的子批划分问题. Liao等 ^[10] 为解决多资源约束的柔性车间调度问题提出一种结合了自适应大邻域和局部搜索的结构化ABC算法. 上述文献主要改进了ABC算法局部搜索能力，但在求解离散问题时依赖大量随机搜索，信息交流具有随机性，导致收敛慢，搜索缺乏引导. 针对该问题，本文引入学习蜂，提出一种动态学习人工蜂群算法（dynamic learning ABC，DLABC）求解DRCMSGFJSP.

2 数学模型

DRCMSGFJSP描述如下: n个工件在m台机器上加工，每个工件均包含n_i道工序，其中包含了h_i道精工序; 工序之间遵循工艺约束，每道工序均可在一台或多台机器上加工，并且在不同机器上所需的加工时间不同; 工件中特定的精工序需工人操作机器进行加工，工人不影响工序的加工时间. 每一台机器的运转速度均有v个速度挡位，同一机器在不同挡位下的加工时间与单位能耗不同. 理论上，同一工序在某一台机器上加工时，高速度挡位加工时间短，单位能耗大. 当出现紧急的任务时，可以通过提升转速以加快生产，确保订单及时交付; 当没有紧急任务时，通过降低转速实现能耗的降低. 每台机器都有一个或者多个能够操作该机器的工人. 由此可见，求解DRCMSGFJSP即为求解4个子问题: 确定工序加工顺序、为工序选择加工机器、为加工机器选择合适的速度挡位、为加工精工序的机器选择工人. 为便于描述，表1列出DRCMSGFJSP模型的符号定义.

本文优化目标为最大完工时间f₁、总能耗f₂，如式（1）所示:

m i n f = m i n \{f_{1}, f_{2}\},

(1)

f_{1} = C_{m a x} = \overset{n}{\underset{i = 1}{m a x}} \{C_{i}\},

(2)

f_{2} = T E C = P E + I E

(3)

其中: PE为加工能耗，IE为空闲能耗，计算公式如下:

P E = \sum_{i = 1}^{n} \sum_{j = 1}^{n_{i}} \sum_{k = 1}^{m} \sum_{v}^{v \in L_{k}} t_{i j k v} \times X_{i j k v} \times e_{k v},

(4)

I E = \sum_{k = 1}^{m} \sum_{i = 1}^{n} \sum_{j = 1}^{n_{i}} \sum_{i^{'} = 1}^{n} \sum_{j^{'} = 1}^{n_{i^{'}}} (S_{i^{'} j^{'}} - C_{i j}) \times Y_{i j i^{'} j^{'} k} \times i e_{k}

(5)

模型约束如下:

\sum_{k = 1}^{m} \sum_{v}^{v \in L_{k}} X_{i j k v} = 1,

(6)

\sum_{k = 1}^{m} \sum_{g = 1}^{w} δ_{i h k g} = 1,

(7)

S_{i (j + 1) k} ⩾ C_{i j k},

(8)

C_{i (j - 1) k^{'}} ⩽ S_{i j k} + (2 - X_{i j k v} - X_{i (j - 1) k^{'} v^{'}}) \times B,

(9)

S_{i j k} + \sum_{i = 1}^{n} \sum_{j = 1}^{n_{i}} \sum_{k = 1}^{m} \sum_{v}^{v \in L_{k}} t_{i j k v} \times X_{i j k v} = C_{i j k},

(10)

C_{i} ⩽ C_{m a x}

(11)

S_{i j k} + t_{i j k v} ⩽ S_{i^{'} j^{'} k} + (1 - Y_{i j i^{'} j^{'} k}) \times B,

(12)

T_{k^{'} g} ⩾ T_{k g} - (1 - τ_{k k^{'} g}) \times B,

(13)

S_{i h k} + (2 - X_{i h k v} - δ_{i h k g}) \times B ⩽ C_{i h k},

(14)

其中: 式（6）表示每道工序仅能选择一台机器的一个速度挡位进行加工; 式（7）表示精工序只能选择一台机器及一个工人进行加工; 式（8）–（9）表示同一工件内的工序存在先后顺序; 式（10）–（11）表示工件的完工时间约束，即每一种工件的完工时间不可能超过总的完工时间; 式（12）表示工序O_ij和工序O_i′j′不能同一时刻在同一机器上加工，并确保所有机器在任何时刻只能以一个速度挡位加工一道工序; 式（13）表示一个工人在任意时刻只能操作一台机器; 式（14）表示一个工人同一时刻只能在一台机器上加工一道精工序.

表1DRCMSGFJSP模型符号定义

Table1Model symbol definitions of DRCMSGFJSP

3 动态学习人工蜂群算法

本文针对DRCMSGFJSP模型对ABC做出如下改进: 1）在初始化阶段，采用混合初始方式生成初始蜜源，以提高算法整体的收敛速度; 2）引入学习蜂，设计一种由优秀蜜源基因引导蜂群搜索的学习操作，减少冗余的随机搜索，提高收敛速度及搜索精度; 定义学习概率，在进化的过程中使用Q学习算子对学习概率进行自适应优化，保持蜜源多样性的同时提高学习蜂的搜索效率; 3）在跟随蜂阶段，设计一种动态邻域搜索策略，针对机器速度编码的特点，加入提速插空与降速补空两种基于变速的邻域结构，以及基于平衡工人工作时长的工人调整策略，从而提高跟随蜂的局部搜索能力; 4）在侦察蜂阶段，对于搜索次数超出最大邻域搜索次数的蜜源，侦察蜂将从非支配等级为1的蜜源中随机挑选一个蜜源代替，有利于提高种群整体的质量.

3.1 编码与解码

合理的编码方式能够有效地降低问题求解难度，加快算法求解的收敛速度. 本文针对DRCMSGFJSP 的工序排序、机器选择、挡位选择和工人选择4个子问题，设计了4层实数编码. 第1层为工序排序（operation sequencing，OS）编码，表示工序加工顺序，其元素值为工件序号，同一工件序号的出现次数代表该工件的工序数; 第2层为机器选择（machines selection，MS）编码，其元素值为各个工序所选择的机器序号，按照 J₁−J₂−J₃顺序排列; 第3层为速度挡位选择（velocity selection，VS）编码，其元素值表示每道工序所选择机器的速度挡位编号; 第4层为精工序工人选择（worker selection，WS）编码，其位置对应关系与MS相同，非零元素值为工人序号，0表示该工序不是精工序，不需要工人加工.4层编码的长度均等于工序总数. 解码是编码的逆过程，不同的解码方式会直接影响算法的运算结果，以及影响收敛速度. 本文在贪婪插入解码 ^[11] 的基础上，设计了综合考虑基于速度挡位的加工时间调整以及工人柔性的解码方式，通过全面分析机器和工人的可用性，优化工序至机器空闲期，旨在缩减机器空闲时间，提升生产效能，进而达到调度优化与资源高效利用的目的.

3.2 混合初始化

初始种群的质量直接影响群智能优化算法的收敛速度. 本文采用启发式和随机初始化混合方法，以确保初始种群的质量并同时保留种群的多样性. OS的初始化策略如下: 1）优先选取剩余工序较多的工件，如果有多个选择，则从候选工件中随机选取; 2）工序进行随机排序，这两种初始化策略各生成种群规模的 50%. MS 则使用 GLR初始化方法 ^[12]，包含全局选择（global selection，GS）、局部选择（local selection，LS）和随机选择（random selection，RS）3种策略，比例设置为6 : 3 : 1. VS的初始化策略如下: 1）随机选择速度挡位，以较大的概率选择高速挡位，使得最大完工时间尽可能小; 2）随机选择速度挡位，以较大的概率选择低速挡位，使得机器总能耗尽可能小; 3）随机选取速度挡位. VS 的3种初始化策略比例设置为4 : 4 : 2. WS 的初始化策略如下: 1）优先选取已分配工序数目较少的工人，如果有多个选择，那么从候选工人中随机选取; 2）优先选择工作负载时间较少的工人，如果有多个选择，则从候选工人中随机选取; 3）随机选取一名工人. WS的3种初始化策略比例也设置为6 : 3 : 1.

3.3 雇佣蜂阶段

DLABC算法的雇佣蜂主要负责全局搜索，采用交叉操作来寻找新的优秀蜜源. OS采用IPOX ^[13]（improved precedence operation crossover）交叉操作; MS，VS 和WS编码串采用 MPX（multiple points crossover）交叉. 雇佣蜂的蜜源更新过程如下: 在种群中随机选择两个蜜源作为父代x₁与x₂，针对不同的编码串采用不同的交叉方式. 将交叉后产生的子代蜜源与父代进行对比，若子代完全支配父代，则保留子代，删除父代; 若父代完全支配子代，则保留父代，删除子代; 若子代与父代互不支配，则在父代和子代中以50%的概率随机选择生成新蜜源.

3.4 学习蜂阶段

经典ABC算法求解复杂的离散问题时，雇佣蜂因其随机性过强且缺乏引导性，个体的适应度可能会在短期内大幅波动，导致算法的收敛速度变慢，搜索精度降低. 针对这一弊端，本文在算法的全局搜索阶段引入新的蜂种–—学习蜂，提炼已搜索到高质量蜜源的基因片段，根据这些基因片段有目的地寻找更优秀的新蜜源，有效提高新蜜源质量，加快收敛速度，提高搜索精度.

3.4.1 学习操作

学习蜂的学习操作主要分为优秀基因提取及优秀基因学习两个部分. 优秀基因提取部分，随机选取当前非支配等级为1的蜜源中的两个蜜源y₁ 与y₂，将y₁ 与y₂的4层编码串分别作对比，y₁与y₂元素值相同的部分及其对应位置记录下来，作为优秀信息串Y，其余不相同的部分用0代替. 重复上述过程，被选择过的蜜源将不会再被选择，直到所有蜜源都被选择过或者只有一个蜜源未被选择过，过程中生成的优秀信息串都会保留在优秀蜜源信息库中. 为避免产生非法解，4层编码分别采用不同的优秀基因学习方式. MS，VS 和 WS串的优秀基因学习方式如图1所示，Y为优秀信息串，X为学习蜂对应的蜜源编码串，newX为X学习Y 后生成的新蜜源编码串，将Y 中非0元素插入newX的对应位置中，再将newX剩下的位置用X中对应位置的元素补满. 由于OS串的对应工序顺序与其他编码串不同，为避免产生非法解，故OS串的优秀基因学习方式如图2所示，将信息串Y 中的非0元素插入newX 对应的位置中，删除X中与Y 非零元素相等且顺序相同的信息串，将剩余元素按顺序插入newX中.

对比学习前后的蜜源，计算二者的目标值，若新蜜源完全支配旧蜜源，则保留新蜜源，删除旧蜜源; 若旧蜜源完全支配新蜜源，则保留旧蜜源; 若二者互不支配，则在新旧蜜源中以50%的概率随机选择蜜源保留，从而实现学习蜂阶段蜜源的更新.

图1MS，VS和WS优秀基因学习

Fig.1Excellent gene learning in MS, VS and WS

图2优秀基因学习

Fig.2Excellent gene learning in OS

3.4.2 Q学习算子

若所有的雇佣蜂都转变为学习蜂，很容易产生相似蜜源，使算法陷入局部最优; 若转变的数量过少，则无法充分发挥学习蜂的作用. 故本文设置学习概率P_L，控制雇佣蜂转变到学习蜂的数量. 针对每一只雇佣蜂，随机生成一个0−1之间的随机数，若小于P_L，则雇佣蜂转变为学习蜂，随机从信息库中选择一套优秀信息串进行优秀基因学习; 否则不进行. 因此，在算法迭代的过程中，本文设计Q学习算子自适应优化P_L，Q学习算子通过行为价值来选取特定动作，通过与环境互动来自主决策动作策略. 学习迭代如式（15）所示 ^[14] .

\begin{matrix} Q (s_{t}, a_{t}) = Q (s_{t}, a_{t}) + χ [R_{t} + γ m a x (Q (s_{t + 1}, \\ a_{t + 1}) - Q (s_{t}, a_{t}))], \end{matrix}

(15)

其中: χ 为学习因子，γ 为折扣率，取值在 [0，1] 之间，R_t为即时奖励，s_t为状态，a_t为动作， Q（s_t，a_t）为行为价值函数，本文Q学习的参数设置见参考文献 ^[15] .

Q学习算子的状态合集、动作合集、奖励方式具体描述如下.

1）状态合集.

为了在蜜源更新迭代时保持蜜源的多样性，本文选用两代蜜源之间的解间距变化与熵变化表征状态合集，解间距与熵是用于评价种群多样性的指标，通过多样性的变化来控制P_L的自适应优化，解间距Sp 与熵H的评价指标公式如下:

a）解间距.

S p = \sqrt{\frac{1}{‖ G ‖ - 1} \sum_{i = 1}^{‖ G ‖ - 1} {(\bar{d} - d_{i})}^{2}},

(16)

式中:

‖ G ‖

为当前蜜源中前沿解的个数; d_i为第i个蜜源到解集中其余蜜源的最小距离;

\bar{d}

是d_i的均值; Sp越小，解集中蜜源的均匀性与多样性就越好.

b）熵.

设当前蜜源中有K个非支配等级，则蜜源在第k个等级中的概率如式（17）所示:

L_{k} = \frac{‖U_{k}‖}{popnum}, 1 ⩽ k ⩽ K,

(17)

其中: popnum是蜜源总数，

‖U_{k}‖

是在等级k中的蜜源数量.

熵的计算公式如（18）所示，熵值H越大，说明蜜源的多样性越好.

H = - \sum_{k = 1}^{K} L_{k} {l o g}_{2} L_{k}

(18)

相邻两代蜜源间的解间距变化 ∆Sp 与熵值变化 ∆H如式（19）–（20）所示，t表示迭代次数.

Δ S p = S p (t) - S p (t - 1),

(19)

Δ H = H (t) - H (t - 1) .

(20)

根据∆Sp与∆H的变化情况定义4个状态θ₁ ∼ θ₄，状态设置如表2所示.

表2状态设置

Table2Status settings

2）奖励方式.

根据4个状态θ₁ ∼ θ₄对应的蜜源多样性变化设置不同的奖励值. 状态为θ₁代表无论是解集还是种群，相较于上一代多样性均有所上升，此时奖励设置为最大; 状态为θ₂时，代表虽然解集中的蜜源多样性上升，但是种群全体蜜源的多样性却有所下降，此时设置较小的奖励值; 状态为θ₃时，虽然种群全体蜜源的多样性上升，但是解集中蜜源的多样性却有所下降，此时也应设置较小的奖励值; 状态为θ₄时，解集与种群的多样性均下降，此时奖励值设置为最小.

3）动作合集.

为确定学习概率P_L的变化，动作合集包含增大、减小与不变3种动作，式（21）表示P_L相邻两代蜜源变化情况，τ为变化幅度，t为迭代次数，初始参数设置为

P_{L}^{0} = 0.5 .

\begin{matrix} P_{L}^{t} = P_{L}^{t - 1} + τ, τ \in {- 0.05,0, 0.05}, \\ 0 ⩽ P_{L}^{t} ⩽ 1 . \end{matrix}

(21)

Q学习算子在算法迭代过程中，根据种群的多样性变化，自适应优化P_L的大小，在保证种群多样性的同时，有效提高学习蜂的搜索效率.

3.5 跟随蜂阶段

跟随蜂主要负责局部搜索. 本文采用锦标赛选择策略，每次随机选取1/P_w个蜜源，从中选出帕累托等级最高的对应蜜蜂转为跟随蜂进行局部搜索，P_w为跟随蜂比例.

为了充分发挥跟随蜂局部搜索的能力，本文使用动态邻域搜索（dynamic neighborhood search，DNS）机制来改进跟随蜂的搜索操作. 与传统 DNS不同的是，本文针对 DRCMSGFJSP的问题特性，为DNS设计了 5种邻域结构N₁−N₅，具体描述如下所示:

1）邻域结构N₁.

采用基于关键路径的邻域结构调整OS串 ^[16] : 若起始关键块包含两道及以上工序，交换其末尾相连的两道工序; 若尾关键块包含两道及以上工序，交换其块首相连的两道工序; 若中间关键块包含3道及以上工序，交换块首和倒数第2道工序，交换块尾和第2道工序; 若交换过程中两道工序为同一工件的不同工序，则不进行交换.

2）邻域结构N₂.

采用基于平衡机器负载方式调整MS串: 从具有最大负载的机器上随机选择一道工序，从该工序可选机器集中，随机选择其它机器.

3）邻域结构N₃.

采用基于提升速度挡位VS的插空操作: 找到完工时间最大的机器，寻找机器上最大空闲时段，向后遍历所有工序，选择第一道使用非最高速度挡位的工序，根据工件工序顺序，工人空闲等情况判断该工序是否可以插入空闲时段，若可以，则直接插入.

4）邻域结构N₄.

采用基于降低速度挡位VS的补空操作: 找到能耗最高的机器，遍历机器上的空闲时间段，选择该时段前非最低速挡位的工序. 根据工件工序顺序，工人空闲等情况判断这些工序降速的加工时段后是否可以补上空闲时段的一部分，若可以，则降速以减小能耗，补上空闲时段.

5）邻域结构N₅.

采用基于平衡工人工时方式调整WS串: 从具有最长工时的工人任务中随机选择一道精工序，得到加工该精工序的机器号，从该机器可选工人集中，随机选择其它工人.

跟随蜂蜜源更新过程如下: 每只跟随蜂都从N₁开始按照顺序进行邻域搜索，寻找新蜜源，执行每次邻域结构之后，都将新蜜源与旧蜜源作对比，若新蜜源不能支配旧蜜源，直接进行下一个邻域结构搜索; 若新蜜源能够完全支配旧蜜源，则直接替换旧蜜源，并结束DNS . 若同一蜜源经过N₁−N₅都没有被优化，则邻域搜索次数q = q + 1，当q大于最大邻域搜索次数时，跟随蜂转变为侦察蜂.

3.6 算法复杂度

DLABC算法的空间复杂度主要由蜜源存储、优秀蜜源信息库、Q表、邻域搜索缓存组成. 种群规模为 popnum，每个个体包含4层编码，每层编码长度为工序总数L，则单个个体空间为O（4L），蜜源存储总空间为O（popnum × 4L），即为O（popnum × L）. 优秀蜜源信息库用于存储非支配等级为1的蜜源，最坏情况下需存储 O（popnum）个蜜源，空间复杂度为 O（popnum × L）. Q 表的状态数为 4，动作数为 3，故 Q表的空间复杂度为O（4 × 3），即为O（1）. 跟随蜂阶段邻域搜索需存储邻域结构操作后的临时解，空间为O（popnum × q_max × L），其中q_max为最大邻域搜索次数. 算法的总空间复杂度为 O（popnum × L + popnum×q_max×L）= O（popnum×L×（1+q_max））. 因为 q_max为常数，故算法的总空间复杂度简化为 O（popnum × L）.

DLABC算法的时间复杂度计算主要体现在混合初始化、雇佣蜂、学习蜂、跟随蜂和适应度计算阶段. 混合初始化需遍历所有个体，每代的时间复杂度为 O（popnum × L），设算法迭代次数为iter，则初始化的总时间复杂度为O（iter × popnum × L）. 雇佣蜂阶段，每代交叉操作的时间复杂度为O（popnum × L），雇佣蜂阶段的总时间复杂度为O（iter×popnum×L）. 学习蜂阶段提取优秀基因并进行基因学习操作，每代时间复杂度为 O（popnum × L），总时间复杂度为 O（iter × popnum × L）. 跟随蜂阶段动态邻域搜索需遍历邻域结构，最坏情况下每只跟随蜂执行 q_max 次操作，单次操作复杂度为 O（L），总时间复杂度为 O（popnum × q_max × L）. 适应度计算的每代复杂度为 O（popnum × L），总时间复杂度为 O（iter × popnum ×L）. 综上，算法的总时间复杂度为O（iter× popnum×L+iter×popnum×L+iter×popnum× q_max×L+iter×popnum×L+iter×popnum×L）= O（iter×popnum×L×（1+q_max）），化简为 O（iter× popnum × L）.

4 仿真实验

本文所提的算法采用MATLAB 2019b软件编程，计算机处理器为Intel i7十代CPU，主频为2.9 GHz，内存为16 G，操作系统为Windows 11.

4.1 测试算例生成

由于本文模型尚未有标准数据集，故在Brandmarte测试集 ^[17] 的MK01−MK10算例的基础上进行拓展，生成 DRCMSGFJSP测试算例WVMK01−WVMK10. 工人数量由w = 0.8 × m 生成; 以50%的概率选择工序是否需要工人进行精加工; 每台机器对所有工人遍历，以50% 的概率选择工人作为该机器的可选工人，如存在机器没有可选工人，则随机选择一位工人. 机器转速信息参考文献 ^[18]，机器能耗信息参考文献 ^[19]，机器标准单位时间加工能耗 e_k ∈ [10，15] kW，机器单位空闲能耗ie_k ∈ [1，3] kW.

本文算法中包含4个参数，分别为种群规模 popnum、最大评价次数 Maxeval、跟随蜂局部搜索种群比例P_w和跟随蜂最大搜索次数q_max. 为了合理选择参数，采用田口试验来确定最恰当的参数组合为 popnum= 150，Maxeval= 150 000，P_w = 0.2，q_max = 10.

4.2 模型有效性验证

为验证本文混合整数规划模型DRCMSGFJSP的有效性与可靠性，本文采用ε-constraint算法将DRCMSGFJSP 转换为单目标问题，并采用Gurobi 求解器在小规模算例上进行求解，同时为了验证本文设计的 DLABC的有效性，在相同算例下将DLABC求解的结果与Gurobi求解的结果进行对比分析. 设置Gurobi的最大运行时间为3600 s，结果如表3所示，其中: Gap表示偏差值，—表示Gurobi在3600 s内无法得到最优解.

表3DLABC与Gurobi 的对比结果

Table3Comparison results of DLABC and Gurobi

由表3可知，对于算例WVMK01和WVMK02，Gurobi能够求出最优解，完工时间最大偏差为3.10%，总能耗最大偏差为 1.77%，在可接受的范围内. 对于算例WVMK03，Gurobi未能在设定时间内求出最优解，DLABC 求解得到的完工时间和总能耗分别为 230.8 和10279.76. 通过与 Gurobi 对比，验证了模型的准确性和DLABC的有效性.

4.3 策略有效性验证

为了验证DLABC算法中改进策略的有效性，对混合初始化、学习蜂、DNS 3个策略依次进行排列组合选择，得到如表4所示的8种算法.

✓

表示当前算法选择该策略，—表示当前算法无该策略.

选择中等规模的算例 WVMK05 作为测试算例，将8种算法分别独立运行，得出各算法每次评价后解集的并集，并将其Pareto非支配解集作为求解前沿面，计算随评价次数变化的IGD，绘制如图3所示的收敛曲线.

如图3所示，使用了混合初始化的算法的IGD值始终在未使用混合初始化的算法的下方，这说明混合初始化策略有效提供了高质量的初始蜜源，加快了算法的收敛速度. 比较DLABC-N与DLABC-L可以得出，评价早期两者IGD的差距并不大，甚至由于初始化的随机性，DLABC-L 的蜜源质量略低于 DLABC-N，在此情况下两种算法的蜜源质量普遍偏低，导致此时学习蜂无法充分发挥作用; 但随着算法迭代，优质蜜源的数量越来越多，学习蜂开始展现其优秀的定向寻优能力，使得在算法后期DLABC-L的蜜源质量远远高于DLABC-N，表明学习蜂可有效提高算法寻优精度.

表4选择不同策略的8种算法

Table4Eight algorithms for selecting different strategies

图3IGD收敛图

Fig.3IGD mean convergence graph

由 DLABC-N与DLABC-D的曲线的对比可知，DNS策略在进化过程中展现了优秀的局部搜索能力，即使初期时 DLABC-D的蜜源质量低于 DLABC-N，DNS策略也能快速的找到优秀蜜源，使得IGD值远远小于DLABC-N，这是由于DNS中包含的5种邻域结构能够根据个体的特征，引领跟随蜂寻找更优质的蜜源. 另一方面，融合了两种策略的算法寻优能力提升更加明显，如结合了混合初始化与学习蜂的DLABC-IL，其 IGD值一直小于DLABC-I与DLABC-L，这是因为混合初始化生成的初始蜜源给予了学习蜂良好的学习基础，使得算法的全局搜索能力得到很大的提升. 综合3种策略的DLABC算法具有最佳的性能，尤其在算法后期其IGD可以达到0，这是因为DLABC求解得到的非支配解集占据了整个前沿面. 综上所述，3种改进策略相辅相成，使DLABC具有最佳的收敛速度与寻优能力.

4.4 算法性能验证

为了验证DLABC算法性能，与已有研究中解决相似问题的 IABC ^[19]，ENSGA ^[20]，MOPSO ^[21]，NSGAII ^[22] 4种算法进行对比. 所有算法的共有参数设置相同，其余特有参数均来自文献本身.5种算法分别独立运行20次，得出各算法每次评价后解集的并集，并将其Pareto非支配解集作为求解前沿面，采用HV，IGD 和CR 3个多目标评价指标对算法的收敛性、分布性、多样性等综合性能进行评估 ^[23]，结果如表5所示，粗体表示5种算法的最优值.

表55种算法对比结果

Table5Comparison results of 5 algorithms

从表5可以看出，DLABC算法的HV，IGD，CR 3个指标在大部分算例上均为最优，说明DLABC算法的综合性能和解集质量优于其他算法. HV越大，代表算法的综合性能越好，由此可见，DLABC 算法的搜索效率明显优于其他算法; IGD 指标越小，说明算法生成的近似解集与理论 Pareto前沿的贴近程度越高，而 DLABC的IGD在所有算例中均取得最小值，说明DLABC求得的解集的综合质量越好; CR代表各算法生成的非支配解在全局最优解集中的分布比例，CR越高，表明算法生成的近似解集对理论Pareto前沿的覆盖越充分，即解集在目标空间中的分布越接近理论最优状态可以看出，除了WVMK01，DLABC算法的CR 值在所有算例中都是最大的，其中WVMK03，WVMK05与WVMK10的CR都为1，这两个算例的最优非支配解集全都被DLABC覆盖，为最终的非支配前沿做出了较大的贡献.

为了更直观地验证DLABC算法的优势，将表5中 HV与IGD 数据绘制如图4所示的箱线图. 可以看出，DLABC得到的HV的中位线最大，IGD的中位线最小，且两幅图中 DLABC的箱体范围均最小，说明 DLABC 相较于其他4种算法具有更好的稳定性.

图4HV和IGD的箱线图

Fig.4Box plot diagram of HV and IGD

为了更加直观地反映各算法非支配解的分布性，图5给出了8种算法在求解3种不同规模算例上的二维解平面分布图. 从分布图可

从分布图可以看出，DLABC求得的解在平面分布上相较于另外4种算法更加的均匀密集，能够在一个范围内最大限度的挖掘出更多的非支配解，说明DLABC挖掘解的能力更强. DLABC相比于其他在解在前沿线上的算法，得到的解分布更均匀，这是因为DLABC没有对目标进行单独优化，相反，使用了一些启发式全指标平衡策略代替单一进化方向使DLABC得到的解集的分布性更加均匀.

图5不同规模实例上解的二维分布图

Fig.5Two-dimensional distribution of solutions for different scale cases

5 结论

本文考虑实际生产中机器多转速及精工序加工的工人约束，建立了双资源约束多转速绿色柔性车间调度问题模型，并设计了一种动态学习人工蜂群算法. 采用混合初始化方式提高初始蜜源的质量; 全局搜索阶段引入学习蜂，设计学习操作以优秀蜜源基因引导蜂群搜索，提高搜索精度，并用Q学习算子对学习概率进行自适应优化，保持蜜源多样性的同时提高算法的全局搜索能力; 跟随蜂阶段设计动态邻域搜索策略，加入基于变速以及平衡工人时的邻域结构，提高跟随蜂的搜索能力. 使用Gurobi求解器对模型进行了有效性验证; 通过仿真实验，验证了算法性能，与其他算法的对比结果表明DLABC算法求解DRCMSGFJSP 具有显著优势. 后续研究将考虑大规模订单的多工厂协同生产，进一步探索多约束及多目标调度问题.

图1MS，VS和WS优秀基因学习

Fig.1Excellent gene learning in MS, VS and WS

下载: 全尺寸图片

图2优秀基因学习

Fig.2Excellent gene learning in OS

下载: 全尺寸图片

图3IGD收敛图

Fig.3IGD mean convergence graph

下载: 全尺寸图片

图4HV和IGD的箱线图

Fig.4Box plot diagram of HV and IGD

下载: 全尺寸图片

图5不同规模实例上解的二维分布图

Fig.5Two-dimensional distribution of solutions for different scale cases

下载: 全尺寸图片

表1DRCMSGFJSP模型符号定义

Table1Model symbol definitions of DRCMSGFJSP

下载: 全尺寸图片

表2状态设置

Table2Status settings

下载: 全尺寸图片

表3DLABC与Gurobi 的对比结果

Table3Comparison results of DLABC and Gurobi

下载: 全尺寸图片

表4选择不同策略的8种算法

Table4Eight algorithms for selecting different strategies

下载: 全尺寸图片

表55种算法对比结果

Table5Comparison results of 5 algorithms

下载: 全尺寸图片

图1MS，VS和WS优秀基因学习

Fig.1Excellent gene learning in MS, VS and WS

图2优秀基因学习

Fig.2Excellent gene learning in OS

图3IGD收敛图

Fig.3IGD mean convergence graph

图4HV和IGD的箱线图

Fig.4Box plot diagram of HV and IGD

图5不同规模实例上解的二维分布图

Fig.5Two-dimensional distribution of solutions for different scale cases

表1DRCMSGFJSP模型符号定义

Table1Model symbol definitions of DRCMSGFJSP

表2状态设置

Table2Status settings

表3DLABC与Gurobi 的对比结果

Table3Comparison results of DLABC and Gurobi

表4选择不同策略的8种算法

Table4Eight algorithms for selecting different strategies

表55种算法对比结果

Table5Comparison results of 5 algorithms

图(5) / 表(5)

引用本文

王玉芳, 章殿清, 华晓麟, 等. 考虑双资源约束多转速的绿色柔性作业车间调度研究. 控制理论与应用, 2025, 42(10): 2019 – 2027

复制

WANG Yufang, ZHANG Dianqing, HUA Xiaolin, et al. Research on green flexible job-shop scheduling considering dual-resource constraints and multiple-speeds. Control Theory & Application, 2025, 42(10): 2019 – 2027

Copy

计量

图1MS，VS和WS优秀基因学习

Fig.1Excellent gene learning in MS, VS and WS

图2优秀基因学习

Fig.2Excellent gene learning in OS

图3IGD收敛图

Fig.3IGD mean convergence graph

图4HV和IGD的箱线图

Fig.4Box plot diagram of HV and IGD

图5不同规模实例上解的二维分布图

Fig.5Two-dimensional distribution of solutions for different scale cases

表1DRCMSGFJSP模型符号定义

Table1Model symbol definitions of DRCMSGFJSP

表2状态设置

Table2Status settings

表3DLABC与Gurobi 的对比结果

Table3Comparison results of DLABC and Gurobi

表4选择不同策略的8种算法

Table4Eight algorithms for selecting different strategies

表55种算法对比结果

Table5Comparison results of 5 algorithms

WU Jie, YANG Junhua. Green energy and ecological environment control. Control Theory & Applications,2004,21(6):864-869.(吴捷, 杨俊华. 绿色能源与生态环境控制. 控制理论与应用,2004,21(6):864-869.)

LI Y B, HUANG W X, WU R,et al. An improved artificial bee colony algorithm for solving multi-objective low-carbon flexible job shop scheduling problem. Applied Soft Computing,2020,95:106543.

YAN Xuesong, ZHANG Junhua, HU Chengyu. Multi objective optimization method for green scheduling of distributed homogeneous hybrid flow shop. Control Theory & Applications, DOI:10.7641/CTA.2024.40443.(颜雪松, 张峻华, 胡成玉. 面向分布式同构混合流水车间绿色调度的多目标优化方法. 控制理论与应用, DOI:10.7641/CTA.2024.40443.)

YANG J, XU H, CHENG J,et al. A decomposition-based memetic algorithm to solve the objective green flexible job-shop scheduling problem with interval type-2 fuzzy processing time. Computers & Industrial Engineering,2023,183:109512.

LI Z, CHEN Y. Minimizing the makespan and carbon emissions in the green flexible job-shop scheduling problem with learning effects. Scientific Reports,2023,13(1):6368.

LUO Q, DENG Q, XIE G,et al. A Pareto-based two-stage evolutionary algorithm for flexible job shop scheduling problem with worker cooperation flexibility. Robotics and Computer-Integrated Manufacturing,2023,82:102534.

MA W, SUN Z, LI J,et al. An improved artificial bee colony algorithm based on the strategy of global reconnaissance. Soft Computing,2016,20(12):4825-4856.

WANG Yiming, LEI Deming. Feedback artificial bee colony algorithm for solving distributed two-stage hybrid flow job shop scheduling. Control Theory & Applications,2024,41(6):1137-1146.(王移民, 雷德明. 求解分布式两阶段混合流水车间调度的反馈人工蜂群算法. 控制理论与应用,2024,41(6):1137-1146.)

LI Y, LIAO C, WANG L,et al. A reinforcement learning-artificial bee colony algorithm for flexible job-shop scheduling problem with lot streaming. Applied Soft Computing,2023:110657.

LIAO X, ZHANG R, CHEN Y,et al. A new artificial bee colony algorithm for the flexible job-shop scheduling problem with extra resource constraints in numeric control centers. Expert Systems with Applications,2024,249:123555.

SUN J H, ZHANG G H, LU J,et al. A hybrid many-objective evolutionary algorithm for flexible job-shop scheduling problem with transportation and setup times. Computers & Operations Research,2021,132:105263.

ZHANG G, GAO L, SHI Y. An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications,2011,38(4):3563-3573.

ZHANG Chaoyong, RAO Yunqing, LIU Xiangjun,et al. Solving Jobshop scheduling problem using POX crossover based genetic algorithm. China Mechanical Engineering,2004,15(23):2149-2153.(张超勇, 饶运清, 刘向军, 等. 基于POX交叉的遗传算法求解Jobshop调度问题. 中国机械工程,2004,15(23):2149-2153.)

LU Xinyi, HAN Xiaolong. Improved NSGA-II based on reinforcement learning for solving energy-saving scheduling problem in flexible job-shop. Modern Manufacturing Engineering,2023,8:22-35.(陆心屹, 韩晓龙. 基于强化学习的改进NSGA-II求解柔性作业车间节能调度问题. 现代制造工程,2023,8:22-35.)

LI R, GONG W, LU C. A reinforcement learning based RMOEA/D for bi-objective fuzzy flexible job-shop scheduling. Expert Systems with Applications,2022,233:117380.

WANG Yufang, ZHANG Dianqing, HUA Xiaolin,et al. Research on dual resource distributed flexible scheduling for aviation structure. Journal of System Simulation,2024,36(11):2722-2740.(王玉芳, 章殿清, 华晓麟, 等. 面向航空结构件的双资源分布式柔性调度研究. 系统仿真学报,2024,36(11):2722-2740.)

BRANDIMARTE P. Routing and scheduling in a flexible job-shop by tabu search. Annals of Operations Research,1993,41(3):157-183.

WEI Z, LIAO W, ZHANG L. Hybrid energy-efficient scheduling measures for flexible job-shop problem with variable machining speeds. Expert Systems with Applications,2022,197:116785.

LI Yibing, HUANG Weixing, WU Rui. Research on multi-objective green flexible job shop scheduling based on improved artificial bee colony algorithm. China Mechanical Engineering,2020,31(11):1344-1350,1385.(李益兵, 黄炜星, 吴锐. 基于改进人工蜂群算法的多目标绿色柔性作业车间调度研究. 中国机械工程,2020,31(11):1344-1350,1385.)

TAN W, YUAN X, WANG J,et al. A fatigue-conscious dual resource constrained flexible job-shop scheduling problem by enhanced NSGA-II: An application from casting workshop. Computers & Industrial Engineering,2021,160:107557.

SHI J, CHEN M, MA Y,et al. A new boredom-aware dual-resource constrained flexible job-shop scheduling problem using a two-stage multi-objective particle swarm optimization algorithm. Information Sciences,2023,643:119141.

WEI Z, LIAO W, ZHANG L. Hybrid energy-efficient scheduling measures for flexible job-shop problem with variable machining speeds. Expert Systems with Applications,2022,197:116785.

TIAN Y, CHENG R, ZHANG X,et al. PlatEMO: A MATLAB platform for evolutionary multi-objective optimization[educational forum]. IEEE Computational Intelligence Magazine,2017,12(4):73-87.