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

混合离散蛙跳算法求解柔性装配系统调度问题

doi: 10.7641/CTA.2023.30331

李晓玲^1,2 ，冯彦翔² ，张广辉³ ，段浩浩¹

1. 长安大学电子与控制工程学院, 陕西西安 710064

2. 西安交通大学机械制造系统工程国家重点实验室, 陕西西安 710049

3. 河北农业大学信息科学与技术学院, 河北保定 071001

基金项目: 国家自然科学基金项目(62103062, 62003258), 长安大学中央高校基本科研业务费专项资金项目(300102322101)资助.

详细信息

作者简介

李晓玲博士,讲师,目前研究方向为柔性制造系统控制与优化调度、智能仿真优化与调度等,E-mail: xiaolingli@chd.edu.cn;

冯彦翔博士,副教授,目前研究方向为自动制造系统死锁控制与优化调度等,E-mail: fengyanxiang@xjtu.edu.cn;

张广辉博士,副教授,目前研究方向为人工智能、分布式生产调度与控制等,E-mail: ghzhang@hebau.edu.cn;

段浩浩硕士研究生,目前研究方向为车间优化调度、车辆路径优化等,E-mail: 2357876237@qq.com.

通信作者

李晓玲，E-mail: xiaolingli@chd.edu.cn;Tel.:+8615529569712.

Hybrid discrete shuffled frog leaping algorithm for the scheduling problem of flexible assembly systems

LI Xiao-ling^1,2 ， FENG Yan-xiang² ， ZHANG Guang-hui³ ， DUAN Hao-hao¹

1. School of Electronics and Control Engineering, Chang’an University, Xi’an Shaanxi 710064 , China

2. The State Key Laboratory for Manufacturing Systems Engineering, Xi’an Jiaotong University, Xi’an Shaanxi 710049 , China

3. College of Science and Technology, Hebei Agricultural University, Baoding Hebei 071001 , China

Funds: Supported by the National Natural Science Foundation of China (62103062, 62003258) and the Fundamental Research Funds for the Central Universities, CHD (300102322101).

摘要

本文主要研究不含中间缓冲区的柔性装配系统(FAS)的优化调度问题, 其中当工件竞争使用有限的生产资源时, 不合理的资源分配会导致系统死锁 (deadlock). 针对易死锁 (deadlock-prone)FAS的优化调度问题, 本文采用 Petri网建模, 提出了一种混合离散蛙跳算法(HDSFLA)以最小化最大完工时间(makespan). 首先, 提出了一种新的编码解码方法, 其中一个个体编码为一个包含全部工件加工信息的变迁序列, 可解码为一个工件–工序序列; 其次, 为了保证种群中个体的可行性, 提出了一个个体修正算法和基于最早引发时间的改进个体修正算法, 从而将不可行个体修复为可行个体; 然后, 结合编码特征设计了用于生成新个体的交叉操作; 最后, 为了平衡算法的全局搜索和局部开发能力, 设计了一个基于交换和插入算子的局部搜索策略. 通过不同规模算例上的仿真实验和算法对比分析, 验证了HDSFLA的有效性.

关键词

柔性装配系统 / 死锁 / Petri网 / 调度 / 混合离散蛙跳算法

Abstract

This paper addresses the scheduling problem in flexible assembly systems (FAS) without intermediate buffers. In such systems, deadlock may occur when multiple jobs compete for limited shared resources under inappropriate allocation. To solve the scheduling problem of deadlock-prone FAS, Petri nets are used to model it, and a hybrid discrete shuffled frog leaping algorithm (HDSFLA) is proposed to minimize the maximum completion time, i.e., makespan. Firstly, a novel encoding and decoding method is proposed, in which an individual is encoded as a complete transition sequence and can be decoded into a sequence of jobs and operations. Then, in order to guarantee the feasibility of each individual, an individual modification method and an improved individual modification method based on the-earliest-firing-time are developed, through which an unfeasible solution can be repaired into a feasible one. Furthermore, based on the characteristics of the encoding method, a crossover operation is designed to generate new individuals for the next generation. In addition, to balance the global exploration and local exploitation capabilities of the proposed algorithm, a local search method based on swap and insert operators is developed and imbedded into the algorithm. Experimental tests on different instances and comparisons with other algorithms are conducted to demonstrate the effectiveness of HDSFLA.

Keywords

flexible assembly systems / deadlock / Petri nets / scheduling / hybrid discrete shuffled frog leaping algorithm

1 引言 2 问题描述 2.1 柔性装配系统 2.2 FAS的Petri网调度模型 2.2.1 Petri网基本定义 2.2.2 FAS的Petri网模型 2.2.3 基于Petri网模型计算完工时间 3 混合离散蛙跳算法 3.1 个体生成与修正 3.1.1 编码 3.1.2 个体修正 3.2 解码 3.3 模因组划分 3.4 模因组内搜索 3.4.1 新个体生成 3.4.2 模因组内个体更新 3.5 局部搜索 3.6 算法流程 4 实验仿真与分析 4.1 实验算例 4.2 算法有效性验证 4.2.1 算法各模块有效性验证 4.2.2 HDSFLA与其他算法对比 5 结论

1 引言

生产调度对于提升制造企业的运行效率起着至关重要的作用. 装配制造系统的调度问题，也称装配调度问题（assembly scheduling problem，ASP），由于其在实际生产中的广泛应用成为近年来的研究热点 ^[1-3] . 不同类型的ASP，如装配流水车间调度问题（assembly flowshop scheduling problem，AFSP）^[4-6]、分布式装配流水车间调度问题（distributed AFSP，DAFSP）^[7-10]、装配作业车间调度问题（assembly jobshop scheduling problem，AJSP）^[11-12]、柔性装配作业车间调度问题（flexible AJSP，FAJSP）^[13-15] 等，吸引了研究者们的广泛关注和研究. 相较于一般的车间调度问题，ASP不仅要考虑子组件或半成品的加工，还要考虑产品的组装，其求解更为复杂.

现有关于ASP的研究通常假设两个相邻的加工机器之间存在着容量无限大的中间缓冲区，且研究成果主要集中于AFSP ^[4-6] 和DAFSP ^[7-10]，关于AJSP ^[11-12] 和FAJSP ^[13-15] 的研究还较少. Shi等 ^[11] 提出了一种混合遗传算法来解决以最小化makespan为目标的AJSP. Cheng等 ^[12] 针对一个考虑了材料完整性和装配顺序约束的AJSP，建立了一种增强模拟退火算法（enhanced simulated annealing，ESA），以最小化总完工时间和总库存时间. Zhang和Wang ^[13] 针对具有序列相关准备时间、工件共享和动态事件的FAJSP，提出了分别基于最早完工时间、工件最多剩余加工时间和最小工作量机器的调度规则，以解决调度和重调度问题来最小化makespan. Wu等 ^[14] 研究了一个以总提前/延迟时间和总花费为优化目标的分布式FAJSP，提出了一种改进差分进化模拟退火算法（improved differential evolution simulated annealing algorithm，IDESAA），其中设计了交叉、变异和选择算子用于种群更新，并设计了一种模拟退火算法用于搜索最佳Pareto解. Zhang 等 ^[15] 研究了一个多目标FAJSP，其中考虑了序列相关准备时间和工件在不同机器之间的传输时间，提出了一种多目标分布式蚁群方法（distributed ant colony system，DACS）来优化总工作量、总延迟和makespan. Xu 和Nagi ^[16] 研究了具有树结构和并行机的AJSP，并开发了一种拉格朗日松弛（lagrangian relaxation，LR）方法以最小化makespan.

上述文献虽然考虑了多种生产约束，但都没有考虑阻塞约束，即所研究的AJSP和FAJSP均假设相邻的两个加工机器之间存在着容量无限大的中间缓冲区. 而在许多实际生产系统中，如电子制造车间、自动化生产单元、钢铁工业、化工和制药厂等，由于生产环境的空间约束或产品生产技术要求，中间缓冲区是容量有限的或者不存在的，因此含有阻塞约束（零中间缓冲区）的制造调度问题近年来也吸引了越来越多研究者的关注 ^{[7-9，17-22]} .

阻塞装配作业车间调度问题（blocking AJSP，BAJSP）可以在实际工业生产中找到许多原型，如电子制造工厂、汽车制造厂等，然而，目前围绕BAJSP的研究成果是极少的 ^[17] . 这是因为在BAJSP中，由于生产资源（如加工机器、运输设备等）是有限的，如果资源得不到合理分配，则可能出现死锁现象，即系统是易死锁的（deadlock-prone），死锁将会导致整个或部分系统处于无限期的阻塞，无法完成加工任务 ^[23-24] . 死锁通常会导致系统长时间停工、一些关键或昂贵资源的低使用率以及生产效率低等结果，使得系统的关键性能指标受到严重影响. 在求解易死锁BAJSP时，需要同时考虑死锁避免和调度目标的优化，这使得调度算法的设计变得更加复杂. 现阶段只有文献 ^[17] 研究了一类BAJSP的变体，提出了一种混合粒子群优化算法（hybrid particle swarm opitimization，HPSO），以最小化makespan.

文献 ^[17] 虽然针对一类易死锁BAJSP进行了研究，但是并没有考虑工件具备柔性加工路径的情况. 因此，为此类问题设计可行且高效的调度算法仍有待研究. 本文针对一个FAJSP的变体，即一类含有并行机和批量工件、不含中间缓冲区、工件具备柔性加工路径的易死锁制造装配系统，简称易死锁柔性装配系统（flexible assembly systems，FAS），进行建模和调度问题求解的研究. 在建模方面，考虑到通过数学公式很难描述死锁且建立不等式约束来避免死锁是很困难的，以及Petri网在为制造系统建模、表征死锁、分析系统运行行为等方面表现出的优异性能 ^[23-24]，本文采用Petri网对FAS建模; 在问题求解方面，考虑到蛙跳算法（shuffled frog leaping algorithm，SFLA）具有参数少、结构简单、易实现等特点，同时具备局部搜索和全局信息交换等特点 ^[25]，本文采用了SFLA并结合问题特征设计了混合离散蛙跳算法（hybrid discrete SFLA，HDSFLA）来使其能够有效地求解易死锁柔性装配系统的调度问题. 仿真实验和算法比较验证了HDSFLA的有效性.

2 问题描述

2.1 柔性装配系统

本文研究的FAS可描述为: FAS包含

R

类机器，记作

R = \{r_{m} ∣ m \in Z_{R}\};

能够完成

N

类工件的加工，记作

J = \{J_{n} ∣ n \in Z_{N}\} ，

其中为方便起见，

Z_{R} 和 Z_{N}

分别代表

Z_{R} = {1，2 ， \dots ， R}

和

Z_{N} = {1，2 ， \dots ， N} ，

下同. 令C（r_m）表示r_m的容量，即具有相同加工能力的机器r_m的个数. 令φ_n表示待加工的J_n类工件的个数，系统中待加工工件的总数为

Φ = \sum_{n \in Z_{R}} φ_{n} .

此外，J₁ 类工件的工件序号表示为1，2，· · ·，φ₁; J₂ 类工件表示为φ₁+ 1，φ₁+2，· · ·，φ₁+φ₂; J₃类工件表示为φ₁+φ₂ + 1，φ₁ + φ₂ + 2，· · ·，φ₁+ φ₂ + φ₃; 等.

在FAS中，一个产品是由多个工件经过一系列的加工和组装操作之后完成生产的. 在一个加工操作中，工件只是利用机器进行加工; 而在组装操作中，两个或多个工件组装成一个新的半成品或最终产品. J_n 类工件的一条加工路径可以表示为一个操作序列，工件可能有多条加工路径，即加工路径具有柔性. 令Ω_n表示 J_n类工件的加工路径集合，其中: ω_i = o_i_，1o_i_，2 · · · o_i_，_l · · ·

O_{i ， L_{i}}

（ω_i ∈ Ω_n）为J_n类工件的一条加工路径，o_i_，_l为ω_i上的第l个操作，L_i为ω_i的长度. 本文中只考虑了同类工件加工路径长度相同的情况. 令R（o_i_，_l）表示完成操作o_i_，_l所需要的资源，于是一条加工路径与一个资源序列对应，ω_i可以由资源序列R（o_i_，1）R（o_i_，2）· · · R（

O_{i ， L_{i}}

）决定. 对于同类工件不同加工路径上的两个操作，例如，o_i_，_l和o_i_′，_l，如果R（o_i_，_l）=R（o_i_′，_l），那么 o_i_，_l和o_i_′，_l表示同样的操作，即ω_i和ω_i_′上的第l个操作是相同的. 在本文中，假设FAS中所有操作所需的加工时间是预先确定且已知的，令d_i_，_l表示完成o_i_，_l所需的加工时间.

FAS中其他约束条件为: 1）不存在中间缓冲区; 2）所有机器在0时刻可用，所有工件在0时刻可开始加工; 3）每个机器同一时刻至多只能加工1个工件; 4）每个工件任一时间最多只能在1个机器上加工; 5）任一操作一旦开始不允许中断; 6）机器的准备时间忽略不计（或包含在加工时间内）.

2.2 FAS的Petri网调度模型

2.2.1 Petri网基本定义

Petri网是一个三元组N =（P，T，F），其中: P是库所集合，T是变迁集合，F ⊆（P × T）∪（T × P）为有向弧集，分别由圆圈、方框和带箭头的连接线表示; 且有

P \neq \emptyset ， T \neq \emptyset ， P \cap T = \emptyset .

对于x∈P ∪ T，•x = {y ∈ P ∪ T|（y，x）∈ F}表示x所有输入元素的集合，x• = {y ∈ P ∪T|（x，y）∈ F}表示x所有输出元素的集合.

N的状态是一个映射M : P → Z = {0，1，2，3，· · · }. 给定库所p ∈ P和状态M，M（p）表示在M下p 中托肯（token）的个数. N的任意一个状态M可以表示为

M = \sum_{p \in P} M （ p ） \cdot p

一个具有初始状态M₀的Petri 网称为标记Petri网，记作（N，M₀）.

变迁t在状态M下是使能的（enabled），当且仅当∀p ∈ •t，M（p）>0，记作M[t >. 在状态M下的使能变迁t可以引发，使得系统到达新状态M′，记作M[t >M′，其中 M′（p）= M（p）− 1，∀p ∈ •t\t•; M′（p）= M（p）+ 1，∀p ∈ t• \ •t; 否则M′（p）= M（p）. 一个变迁序列β =t₁t₂ ∑t_K如果满足M_k[t_k >M_k₊₁，k∈Z_K，且M₁ = M，则称其在M下是可行（feasible）的.

2.2.2 FAS的Petri网模型

为了建立FAS的Petri网模型，需要先后为FAS中的加工路径、资源的请求和释放建模. 读者可参考文献 ^[26] 来更好的了解Petri网建模.

首先，J_n类工件的一条加工路径ω_i = o_i，1o_i，2 · · · o_i，l· · ·

O_{i ， L_{i}}

可以建模为Petri网中的一条库所变迁路径（place transition path，PT–路径），记作PT_i =

p_{n ， 0} t_{i ， 1} p_{i ， 1} t_{i ， 2} \dots t_{i ， l} p_{i ， l} t_{i ， l + 1} \dots p_{i ， L_{i}} t_{i ， L_{i} + 1} p_{n ， L_{i} + 1}

，其中p_i，l（l ∈ ZL_i）是一个操作库所，o_i，l的加工在p_i，l上进行，且p_i，l中托肯的个数表示正在加工的工件个数，变迁 t_i，l的引发表示p_i，l−1中操作的结束和p_i，l中操作的开始. 方便起见，对每类工件J_n引入两个虚拟的操作库所，分别用于存储等待加工的工件和已完成加工的工件，记作p_n，0和

p_{n ， L_{i} + 1}

，称为开始库所和结束库所. 工件在存储位置、加工位置之间的移动用库所到变迁以及变迁到库所的有向弧表示. 对于一个操作库所p_i，l，如果

|p_{i ， l}^{∙}| > 1 ，

即p_i，l有两个及以上的输出元素，则称 p_i，l为分支库所，其中

|p_{i ， l}^{∙}|

表示

p_{i ， l}^{∙}

中元素的个数. 给定一个变迁t_i，l，令（p）t_i，l表示

^{∙} t_{i ， l}

中的操作库所构成的集合. 如果

|^{（ p ）} t_{i ， l}| > 1 ，

即

^{（ p ）} t_{i ， l}

中包含的元素个数大于 1，则称t_i，l为组装变迁. 一个组装变迁的引发表示系统中相应组装操作的开始. 由于FAS中不同的加工路径可能共享一些相同的操作，相应的，其对应的PT–路径会共享对应的库所、变迁和有向弧.

在FAS的Petri网模型中， r_m类机器用一个资源库所r_m表示. 资源库所r_m中托肯的个数表示可用机器的数量，在系统的初始状态M₀下，r_m中托肯的个数 M₀（r_m）即为系统中r_m类机器的总个数. 当操作库所 p_i_，_l上的加工需要使用资源r_m，则添加从r_m到t_i_，_l=

^{∙} p_{i ， l}

和从

t_{i ， l + 1} = p_{i ， l}^{∙}

到r_m的有向弧表示资源的需求和释放.

整个 FAS 的Petri网模型为（N，M₀）=（P，T，F，M₀）=（P_O ∪P_S∪P_E∪ P_R，T，F，M₀），其中 P_O，P_S，P_E和P_R表示操作库所、开始库所、结束库所和资源库所的集合. 初始状态 M₀ 定义为 M₀（p_n_，0）= φ_n，∀p_n_，0 ∈ P_S; M₀（p）= 0，∀p ∈ P_O ∪ P_E; M₀（r_m）= C（r_m），∀r_m ∈ PR.

对于操作库所p_i_，_l中的任意一个托肯，其在p_i_，_l中的停留时间至少为d_i_，_l，即完成o_i_，_l所必需的加工时间. 当FAS完成加工后，其Petri 网模型对应地到达终止状态，记作 M_f，且有M_f（p）= 0，∀p ∈ P_O∪ P_S; M_f（

p_{n ， L_{i} + 1} ，

）= M₀（p_n_，0），∀

p_{n ， L_{i} + 1} ，

∈ P_E; M_f（r_m）= C（r_m），∀r_m ∈ P_R.

给定一个FAS及其Petri网模型，一个满足M₀[α >M_f的变迁序列α称为该FAS的一个调度序列. 本文所研究的FAS调度问题为寻找一个调度序列并使得其对应的完工时间尽可能地小.

2.2.3 基于Petri网模型计算完工时间

给定一个FAS及其Petri网模型（N，M₀），令π=π₁，π₂，· · ·，π_H₋₁，π_H表示一个满足M₀[π >M_f的变迁序列，其中H为π中变迁的个数. 对于该调度序列中任意一个变迁π_h（h ∈ Z_H），假设π_h= t_i_，_l且其为π中第 a个t_i_，_l，为表示更清楚，π_h也可记为

π_{h} [t_{i ， l}^{a}] ， π_{h}

的最早引发时间记作

f (π_{h}) = f (π_{h} [t_{i ， l}^{a}]) .

根据π中变迁的顺序，π_h的引发时间不能早于π_h₋₁的引发时间，因此有

f (π_{h}) ⩾ f (π_{h - 1}) .

假设π_h₋₁对应于π中的第a′个

t_{i^{'} ， l^{'}} ，

那么

f (π_{h}) ⩾ f (π_{h - 1})

可进一步表示为

f (π_{h} [t_{i, l}^{a}]) ⩾ f (π_{h - 1} [t_{i^{'}, l^{'}}^{a^{'}}]),

此外，鉴于t_i_，_l的引发对应于操作o_i_，_l的开始，当t_i_，_l不是组装变迁时，即

|^{（ p ）} t_{i ， l} ∣ = 1 ， π_{h} = t_{i ， l}

还必须在o_i_，_l的前一个操作o_i_，_l₋₁完成之后才能引发，即π_h的引发时间还需满足

f (π_{h} [t_{i ， l}^{a}]) ⩾ f (π_{h^{'}} [t_{i ， l - 1}^{a}]) + d_{i ， l - 1} .

因此对于一个非组装变迁，

\int (π_{h} [l_{i ， l}^{a}]) = m a x \{\int (π_{h - 1} [t_{i^{'} ， l^{'}}^{a^{'}}]) ， f (π_{h^{'}} [t_{i ， l - 1}^{a}]) + d_{i ， l - 1}\} ， |^{（ p ）} t_{i ， l}| = 1 .

其中由于 t_i_，0和 o_i_，0在FAS的Petri网调度模型中不存在，故有

f (π_{h^{'}} [t_{i, 0}^{a}]) = 0, d_{i, 0} = 0

当π_h =t_i_，_l为组装变迁时，即

|^{（ p ）} t_{i ， l}| > 1 ，

它只有在（p）t_i_，_l中所有操作库所中的工件准备好组装时才能引发，即π_h的引发时间需满足

\begin{matrix} f (π_{h} [t_{i, l}^{a}]) ⩾ \\ m a x \{f (π_{q} [t_{x^{'}, y^{'}}^{a}]) + d_{x, y} ∣ p_{x, y} \in^{(p)} t_{i, l}, t_{x^{'}, y^{'}} \in^{∙} p_{x, y}\} \end{matrix}

其中

t_{x^{'} ， y^{'}}^{a}

为π中满足

t_{x^{'} ， y^{'}} \in ∙ p_{x ， y}

的第a个同时，π_h的引发时间不能早于π_h₋₁的引发时间，故有同时，π_h的引发时间不能早于π_h₋₁的引发时间，故有

\begin{matrix} f (π_{h} [t_{i, l}^{a}]) = \\ m a x \{f (π_{h - 1} [t_{i^{'}, l^{'}}^{a^{'}}]), m a x \{f (π_{q} [t_{x^{'}, y^{'}}^{a}]) + \\ d_{x, y} ∣ p_{x, y} \in^{(p)} t_{i, l}, t_{x^{'}, y^{'}} \in p_{x, y}\}\} . \end{matrix}

综上，π_h最早引发时间的计算公式为

(1)

π中最后一个变迁π_H的引发时间即为该调度序列对应的完工时间，记为C_max（π）= f（π_H）.

例 1 考虑一个机器集为R = {r_m|m ∈ Z₅}，工件集为J = {J₁，J₂}的FAS，其简单示意图见图1，其中每类资源的容量为C（r_m）= 1， m ∈ Z₅，待加工的工件数量为φ₁ = φ₂ = 5.

在该FAS中，J₁类工件有一条加工路径，ω₁ = o_1，1 o_1，2o_1，3，各操作使用的机器分别为r₁，r₂和r₅; J₂类工件有两条加工路径，ω₂= o_2，1o_2，2o_2，3和ω₃ = o_3，1o_3，2 o_3，3，ω₂（ω₃）上各操作使用的机器分别为 r₁，r₄ 和r₅（r₃，r₄和r₅）. 由于o_2，2和o_3，2使用的机器满足R（o_2，2）= R（o_3，2）= r₄，因此o_2，2 = o_3，2，在Petri网模型中用同一个操作库所p_2，2表示. 另外，由于系统中存在将J₁类工件和J₂类工件组装成最终产品的组装操作，因此，o_1，3，o_2，3和o_3，3表示同一个操作，在Petri网模型中用 p_1，3表示. 系统的Petri网模型如图1所示.

图1FAS示意图及其Petri网模型

Fig.1Example of an FAS and its Petri net model

3 混合离散蛙跳算法

为了解决FAS的调度问题，本文提出了HDSFLA 以最小化完工时间，主要包含5个模块: 个体生成与修正、个体解码、模因组划分、模因组内搜索和局部搜索.

3.1 个体生成与修正

3.1.1 编码

给定一个FAS及其Petri网模型，算法中的一个个体S编码为一个具有重复变迁的完整变迁序列S =s₁，s₂，· · ·，s_H，即S包含从M₀到达M_f所需的变迁. H的值取决于系统中待加工的每类工件的个数以及其加工路径（PT–路径）的长度.

由于系统中存在组装操作，不同类型工件的PT–路径可能拥有相同的子PT–路径，为了避免该子PT–路径上的变迁出现的次数多于一个可行S所需要的次数，为PT_i定义了一个用于编码的有效（valid）PT–路径（VPT–路径），记为VPT_i . 即，通过删减一些PT–路径上的相同子PT–路径以保证Petri网模型中的变迁在V– PT_i中都只出现一次. 令T_i表示一个集合，由VPT_i上的变迁构成. 令Θ_n表示由J_n类工件的VPT–路径上的变迁构成的集合，

Θ_{n} = \cup_{ω_{i} \in Ω_{n}} T_{i} .

给定一个含有

N

类工件的FAS及其Petri网模型，J_n类工件的VPT–路径的长度记为λ_n，那么一个调度序列的长度为

H = \sum_{n = 1}^{N} φ_{n} \times λ_{n} .

令算法种群的大小为 POP，本文采用随机方式生成初始种群中的个体，记作算法1，详细步骤如下:

步骤 1 令

Λ = \emptyset ， Λ_{n} = \emptyset (n \in Z_{N}) .

对于J_n类工件，如果该类工件只有一条VPT–路径，设为VPT_i，则令Λ_n = Λ_n ∪ T_i; 否则，在该类工件的VPT–路径中任意选择一条，设为VPT_i_′，并令Λ_n= Λ_n∪ T_i′; 重复以上操作φ_n次. 令

Λ = ⋃_{n \in Z_{N}} Λ_{n}

步骤 2 令h = 1，S = s₁，s₂，· · ·，s_H.

步骤 3 随机选择Λ中的一个元素，如t_i_，_l，令 s_h=t_i_，_l，Λ = Λ\{t_i_，_l}，h = h + 1.

步骤 4 若Λ = ∅，则输出S; 否则返回步骤3.

为方便读者理解，提供一个编码示例见附录.

3.1.2 个体修正

由于算法1得到的S是随机生成的，没有考虑系统中的各种生产约束，如工序的先后顺序和资源容量约束，以及死锁状态，因此S 可能是不可行的. 为了得到一个可行的调度序列，需对 S 进行修正使得S满足 M₀[S >M_f，为此，本文提出一种个体修正（individual modification，IM）方法，记作算法2（见表1）.

给定一个个体S，修正开始于初始标识M₁ = M₀ 和S中的第1个变迁. 在算法2的第h个修正步骤中，首先检测s_h是否可行（s_h称为M_h下的可行变迁，当且仅当s_h在M_h下使能且s_h是安全变迁; s_h引发后得到的新标识M_h₊₁是安全的，则称s_h为安全变迁），如果可行则直接引发，更新标识，并开始下一步修正; 否则将 s_h₊₁，s_h₊₂，· · ·，s_H中的第1个可行变迁s_h₊_d（d>0）移到s_h之前，在M_h下引发s_h₊_d并开始下一步修正. 由于本文考虑的FAS中存在路径柔性，因此可能出现这样一种情况: 待检测的变迁s_h₊_d是不可行的（即s_h₊_d不使能或者s_h₊_d不安全），但是

s_{h + d} \in p_{i ， j}^{∙} ， |p_{i ， j}^{∙}| > 1 ，

且存在

t \in p_{i ， j}^{∙}

是可行的，则称以上这种现象为路径冲突，即对于正在加工的、具有路径柔性的工件而言，其当前选择的加工路径是不可行的，但是存在其他的可行路径，这时通过更改工件的加工路径可完成第h步的修正. 为了快速地判定一个变迁 t 在一个给定标识M 下是否安全，算法 2中采用了一种具有多项式复杂度的死锁避免策略（deadlock avoidance policy，DAP）^[27] 来进行判定.

表1算法 2 IM算法

Table1Algorithm 2 IM algorithm

在IM算法的第h个修正步骤中，算法只是在s_h，s_h₊₁，s_h₊₂，· · ·，s_H中寻找第1个可行变迁s_h₊_d，或通过改变工件的加工路径使得s_h₊_d为可行变迁，并没有利用与变迁引发时间相关的信息，因此得到的个体性能可能不佳. 为了保证修正后得到的个体具有良好的性能，本文还提出了一种改进后的个体修正（improved IM，IIM）算法. 在IIM的第h个修正步骤中，建立了一种最早引发时间（earliest firing time，EFT）策略来选择 M_h下具有最早引发时间的可行变迁. 具体过程为: 首先，计算M_h下具有最早引发时间的变迁t（当有多个变迁时，随机选择一个）; 然后，在s_h，s_h₊₁，s_h₊₂，· · ·，s_H中寻找t，并将s_y = t 移动到 s_h之前. 如果 s_h，s_h₊₁，s_h₊₂，· · ·，s_H中不存在t，即发生路径冲突，则在修改工件路径后重新执行寻找和移动操作. EFT策略的具体实现为: 通过将IM中第12和15行中的“d + 1”替换为“执行EFT策略”，即可得到IIM（EFT策略见表2）.

表2EFT策略

Table2EFT strategy

3.2 解码

对于一个可行的变迁序列S，可以将其解码为一个由工件序号和工序组成的序列，记作JO（S）= jo₁，jo₂，· · ·，jo_H，其中 jo_h= JN_h[o_i_，_l]，JN_h∈ [1，Φ] 为工件的序号，o_i_，_l为该工件的第l个工序. 解码的详细步骤如下，记作算法3.

步骤 1 令h = 1，JO（S）= jo₁，jo₂，· · ·，jo_H.

步骤 2 将s_h解码为相应的工件序号和工序;

步骤 2.1 如果s_h ∈Θn且

|Ω_{n}| = 1 ，

即s_h是J_n类工件VPT–路径上的变迁，且J_n类工件只有一条VPT– 路径，若s_h=t_i_，_l是S中第y个t_i_，_l，则

{J N}_{h} = \sum_{a \in Z_{n - 1}} φ_{a} + y ， {j o}_{h} = {J N}_{h} [o_{i ， l}];

否则转至步骤2.2.

步骤 2.2 如果

s_{h} \in Θ_{n} 且 |Ω_{n}| > 1 ，

即s_h是J_n类工件VPT–路径上的变迁，且J_n类工件有多条VPT–路径;

步骤 2.2.1 若

s_{h} = t_{i ， l} ，

|（^（^p^）t_i_，_l）^•|>1，且^•（^（^p^）t_i_，_l）= ∅，即s_h是J_n类工件分支库所的输出变迁且分支库所为一个开始库所，如果满足t∈（^（^p^）t_i_，_l）^•的变迁在s₁，s₂，· · ·，s_h₋₁中出现的次数为y，则

{J N}_{h} = \sum_{a \in Z_{n - 1}} φ_{a} + y + 1 ， {j o}_{h} = {J N}_{h} [o_{i ， l}]

; 否则转至步骤2.2.2;

步骤 2.2.2 若

s_{h} = t_{i ， l} ，

|（^（^p^）ti，l）^•|>1，且^•（^（^p^）ti，l）≠ ∅，即s_h是J_n类工件分支库所的输出变迁且分支库所不是开始库所，如果满足t∈（^（^p^）ti，l）^•的变迁在s₁，s₂，· · ·，s_h₋₁中出现的次数为 y，将s₁，s₂，· · ·，s_h₋₁中第 y+1个满足t∈^•（^（^p^）ti，l）元素的位置记为x，则JN_h= JN_x，jo_h = JN_h[o_i_，_l]; 否则转至步骤2.2.3;

步骤 2.2.3 若

s_{h} = t_{i ， l}

，|（^（^p^）t_i_，_l）^•|=1，|^•（^（^p^）t_i_，_l）|=1 且s_h=t_i_，_l是S 中第y个t_i_，_l，将s₁，s₂，· · ·，s_h₋₁中第 y个t=^•（^（^p^）t_i_，_l）的位置记为x，则JN_h = JN_x，jo_h= JN_h[o_i_，_l]; 否则转至步骤2.2.4;

步骤 2.2.4 若

s_{h} = t_{i ， l} ，

|（^（^p^）t_i_，_l）^•|=1，|^•（^（^p^）t_i_，_l）|>1，且s_h=t_i_，_l是S中第y个t_i_，_l，将s₁，s₂，· · ·，s_h₋₁中第 y 个满足t∈^•（^（^p^）t_i_，_l）的变迁位置记为 x，则JN_h= JN_x，jo_h = JN_h[o_i_，_l].

步骤 3 h=h + 1，若h=H + 1，则输出JO（S）; 否则返回步骤2.

例 2 考虑一个可行个体S = t_1，1，t_1，2，t_3，1，t_1，1，t_3，2，t_1，3，t_1，4，t_1，2，t_2，1，t_2，2，t_1，3，t_1，4. 根据算法3解码后得到的JO（S）如图2所示.

3.3 模因组划分

以个体的完工时间为适应度值，则可根据公式（1）计算种群中每个个体的适应度值，记作F（S），并将种群个体按适应度值大小进行升序排序. 假设HDSFLA 包含Meme个模因组，则将排在第1（Meme + 1，2Meme + 1，3Meme + 1，等）的青蛙分配到第1个模因组，排在第 2（Meme + 2，2Meme + 2，3Meme + 2，等）的青蛙分配到第2个模因组，将排在第3（Meme + 3，2Meme + 3，3Meme + 3，等）的青蛙分配到第3个模因组，以此类推，直至将所有青蛙划分完毕.

图2一个可行个体S及其解码序列JO（S）

Fig.2A feasible individual S and its JO (S)

3.4 模因组内搜索

3.4.1 新个体生成

文中将采用两点交叉（two point crossover，TPX）操作来实现新个体的生成，TPX操作示意图如图3所示，其中P₁和P₂为选定进行交叉的个体，S_new为新生成的个体. 根据P₁和P₂中工件的路径信息要考虑两种情况，TPX具体步骤如下:

步骤 1 随机生成h₁和h₂，h₁和h₂分别为交叉操作的起点和终点并满足 h₁ ∈（1，H），h₂ ∈（1，H）和h₂>h₁; 本文令交叉段的长度在个体长度的1/6到1/3 之间随机生成.

步骤 2 判定P₁中交叉段的元素是否在P₂中都有对应元素，如果是，则将P₁的交叉段复制到S_new中相应位置，把P₂中与交叉段相同的元素删除后，将剩余的元素按先后顺序复制到S_new的剩余位置，见图3（a）; 否则，将P₁交叉段中满足对应关系的元素依次复制到 S_new中相应位置，将P₂中相应元素删除后，将剩余的元素按先后顺序复制到S_new的剩余位置，见图3（b）.

图3交叉操作产生新个体

Fig.3New individual generated from P₁ and P₂

3.4.2 模因组内个体更新

对于每一个模因组，模因组内的搜索执行N_M次. 在每次搜索中，首先将模因组内的最优个体（记作P_b）与最差个体（记作P_w）进行交叉，得到新个体P_n1. 然后，对P_n1 进行修正，如果修正后P_n1的适应度值优于 P_w，则P_n1替换P_w; 否则，将种群的最优个体（记作P_g）与P_w进行交叉，得到新个体P_n2. 如果修正后P_n2的适应度值优于P_w，则P_n2替换P_w; 否则，随机生成一个新个体，修正使其可行并替换P_w.

3.5 局部搜索

为了提升算法的局部搜索能力，本文中采用了基于交换和插入算子的变邻域搜索方法（variable neighborhood search，VNS）对种群中的最优个体进行改进，基于交换算子的VNS，记作S-VNS，其执行步骤如下:

步骤 1 确定初始解S及其适应度值F（S），设k = 0，重复步骤2–步骤4直到k = LS;

步骤 2 在（1，H）内生成两个不同的随机数h₃和 h₄，交换S中第h₃个和第h₄个元素，得到的新个体记作S′，k = k + 1;

步骤 3 采用IIM修正S′，计算F（S′）;

步骤 4 如果F（S′）<F（S），则S := S′.

基于插入算子的VNS（记作I-VNS）的执行步骤与 S-VNS类似，唯一不同是在步骤 2中将S中第h₄个元素插入到第h₃个元素之前. LS为S-VNS（I-VNS）中执行交换（插入）操作的次数.

3.6 算法流程

HDSFLA流程见图4，主要由种群初始化、解码、模因组划分、模因组内搜索及局部搜索5个模块构成.

4 实验仿真与分析

为了测试HDSFLA解决FAS调度问题的性能，进行了算例测试和算法对比实验，所有的测试算法均用 Visual Studio C++ 2019编程实现，运行环境为AMD Ryzen 7 4800HS CPU处理器，主频2.9 GHz，16 GB RAM的PC.

4.1 实验算例

由于没有可供参考的基准算例，因此以文献 ^[17，24] 中的制造装配系统（工件不具备柔性路径）作为参考，并对其进行扩充，得到如下一个 FAS: 资源集为 R = {m₁，m₂，· · ·，m₆}∪ {r₁，r₂，· · ·，r₆}，工件集为 J ={J₁，J₂，J₃}，其中: {m₁，m₂，· · ·，m₆}为一组机器，负责工件的加工; {r₁，r₂，· · ·， r₆}为一组机器人，负责工件在相邻两个机器间的传送，其对应的Petri网模型如图5所示. 分别在[5，25]和[5，10]之间随机生成机器和机器人上操作的加工时间，记录在表3中.

图4HDSFLA流程图

Fig.4Flowchart of HDSFLA

图5测试FAS的Petri网模型

Fig.5Petri net model of the test FAS

表3工件的加工时间

Table3Processing time of operations

基于该FAS生成20个具有不同工件数量和资源配置的测试算例，记作FAS01-FAS20. 根据各算例中的资源配置将FAS01-FAS20划分为4组，每组包含5个算例，5 个算例中工件的个数（φ₁，φ₂，φ₃）分别为（20，20，20），（30，30，30），（50，50，50），（80，80，80）和（100，100，100）. 每个算例中的资源数量分别为:

\begin{matrix} F A S 01 - F A S 05 : C (m_{n}) = 1, C (r_{n}) = 1, n \in Z_{6}; \\ F A S 06 - F A S 10 : C (m_{n}) = 2, C (r_{n}) = 2, n \in Z_{6}; \\ F A S 11 - F A S 15 : C (m_{n}) = 3, C (r_{n}) = 2, n \in Z_{6}; \\ F A S 16 - F A S 20 : C (m_{n}) = 4, C (r_{n}) = 2, n \in Z_{6} . \end{matrix}

HDSFLA中有4个关键参数: 种群规模POP，模因组个数Meme，模因组内搜索次数N_M，局部搜索中的搜索次数LS. 本文采用实验设计方法（design of experiment，DOE）来确定算法的参数设置. 首先，给每个参数设置3个水平，然后，采用正交表L₉（4=）进行实验设置，并用FAS09做测试算例. 参数的水平设置如表4所示（参数组合及对应结果见附录）. 算法在每种参数组合下独立运行20 次，20次运行的平均完工时间结果作为响应值（response variable，RV），基于各参数在不同水平下的平均RV，HDSFLA的参数设置为POP = 60，Meme = 4，N_M= 12和LS = 0.06H.

表4算法参数水平设置

Table4Parameters and their factor levels

4.2 算法有效性验证

对于每个算例，每种算法的终止条件都设置为 T_CPU =Φ×C_R×0.05 s，且算法单独运行20次. 算法在 20次运行中的最好完工时间结果和平均完工时间结果分别记作BST和AVG（小数保留两位），每个算例对应的最优结果标记为粗体.

4.2.1 算法各模块有效性验证

为了验证本文中提出的编码、IIM以及局部搜索模块的有效性，本文测试了HDSFLA和其他3种DSFLA（表示为DSFLA1，DSFLA2和DSFLA3）的性能. DSFLA1是将HDSFLA中局部搜索的IIM改为IM获得的，DSFLA2是将HDSFLA中的局部搜索模块除去后获得的，DSFLA3是将DSFLA2的编码改为现有文献 ^[17，28] 中的基于工件序号的编码方法后获得的. 为了保证比较的公正性，不同DSFLA都采用相同的参数设置. 实验结果如表5所示.

表5HDSFLA和其他3种DSFLA的实验结果

Table5Experimental results of HDSFLA and 3 other DSFLA

从表5中可以看出，HDSFLA的表现优于其他3种 DSFLA算法，表明了HDSFLA在求解FAS调度问题时的有效性. 同时，HDSFLA 优于DSFLA₁的表现验证了IIM的有效性，HDSFLA优于DSFLA₂的结果验证了局部搜索模块的有效性，DSFLA₂远优于DSFLA₃ 的结果表明了本文提出的编码方式对于提升算法求解质量有着显著的效果. 此外，算法性能还存在统计意义上的差异，也说明了HDSFLA中不同模块的有效性，实验结果和分析见附录.

4.2.2 HDSFLA与其他算法对比

由于FAS的生产特点以及死锁的存在，目前无可用的调度算法能够解决其调度问题，故选用几种尽可能相关的调度算法以及几种著名的算法作对比实验. 以HPSO ^[17]，GA ^[28]，GA₂，灰狼算法（grey wolf optimizer，GWO）^[29]，基于成功历史的自适应差分进化算法（success-history based adaptive differential evolution，SHADE）^[30] 和jSO ^[31] 为对比算法，其中HPSO是用于求解不含柔性路径FAS调度问题的算法，GA用于求解含有柔性路径、不含装配操作的柔性制造系统调度问题，GA₂由GA改进得到，GWO，SHADE和jSO为近年来群智能和进化计算领域较为著名的算法. 由于这些算法无法直接用于解决FAS调度问题，故做以下调整: 同时考虑文献 ^[17，28] 中基于工件序号的编码方式，修改为适用于 FAS 调度问题，应用到 HPSO，GA，GWO，SHADE 和jSO中; 将文献 ^[28] 中的个体修复方法与文献 ^[27] 中的DAP结合来修正 HPSO，GA，GWO，SHADE和jSO中的不可行个体. GA₂是将GA中的编码、个体修复、解码、交叉操作更换为本文提出的编码、个体修正、解码和交叉操作后得到. 比较算法的其他方面与来源参考文献保持一致. 实验结果如表6所示.

表6HDSFLA和6种比较算法的实验结果

Table6Experimental results of HDSFLA and 6 comparison algorithms

由表6可知，HDSFLA在各算例上的BST和AVG结果均优于其他比较算法，表明了HDSFLA在求解FAS 调度问题时具有优异的性能. 同时，GA₂算法优于GA，不仅表明了本文所设计的编码和交叉操作也适用于设计其他算法，还表明了其有效性.

5 结论

本文研究了易死锁柔性装配系统的调度问题，以完工时间为优化目标，提出了HDSFLA. 首先，建立了系统的Petri网模型; 然后，基于Petri网模型建立了HDSFLA，包括编码方法、个体修正方法、改进的个体修正方法、解码方法、生成新个体的交叉操作和局部搜索方法; 最后，设计了对比实验验证了HDSFLA中所设计的不同模块的有效性，与其他算法的对比表明了 HDSFLA在求解易死锁柔性装配系统调度问题方面有着较强的优势.

鉴于针对柔性装配系统调度问题的研究尚处于初步阶段，在后续研究中将继续关注以下几个方面: 1）探索在优化能力和计算效率方面具有更好表现的求解算法，如研究建立具有更低复杂度的个体修正方法、基于问题特征知识的搜索策略等; 2）进一步关注具有其他生产约束的柔性装配系统，如准备时间、不确定加工时间、零等待和随机事件等; 3）考虑其他性能指标的优化，如能耗、总提前/延迟时间、总流经时间等.

附录

附件 https: //pan.baidu.com/s/1QLIUPzCM3gJhK0mY9 JhJkQ; 提取码: 0331

图1FAS示意图及其Petri网模型

Fig.1Example of an FAS and its Petri net model

下载: 全尺寸图片

图2一个可行个体S及其解码序列JO（S）

Fig.2A feasible individual S and its JO (S)

下载: 全尺寸图片

图3交叉操作产生新个体

Fig.3New individual generated from P₁ and P₂

下载: 全尺寸图片

图4HDSFLA流程图

Fig.4Flowchart of HDSFLA

下载: 全尺寸图片

图5测试FAS的Petri网模型

Fig.5Petri net model of the test FAS

下载: 全尺寸图片

表1算法 2 IM算法

Table1Algorithm 2 IM algorithm

下载: 全尺寸图片

表2EFT策略

Table2EFT strategy

下载: 全尺寸图片

表3工件的加工时间

Table3Processing time of operations

下载: 全尺寸图片

表4算法参数水平设置

Table4Parameters and their factor levels

下载: 全尺寸图片

表5HDSFLA和其他3种DSFLA的实验结果

Table5Experimental results of HDSFLA and 3 other DSFLA

下载: 全尺寸图片

表6HDSFLA和6种比较算法的实验结果

Table6Experimental results of HDSFLA and 6 comparison algorithms

下载: 全尺寸图片

图1FAS示意图及其Petri网模型

Fig.1Example of an FAS and its Petri net model

图2一个可行个体S及其解码序列JO（S）

Fig.2A feasible individual S and its JO (S)

图3交叉操作产生新个体

Fig.3New individual generated from P₁ and P₂

图4HDSFLA流程图

Fig.4Flowchart of HDSFLA

图5测试FAS的Petri网模型

Fig.5Petri net model of the test FAS

表1算法 2 IM算法

Table1Algorithm 2 IM algorithm

表2EFT策略

Table2EFT strategy

表3工件的加工时间

Table3Processing time of operations

表4算法参数水平设置

Table4Parameters and their factor levels

表5HDSFLA和其他3种DSFLA的实验结果

Table5Experimental results of HDSFLA and 3 other DSFLA

表6HDSFLA和6种比较算法的实验结果

Table6Experimental results of HDSFLA and 6 comparison algorithms

图(5) / 表(6)

引用本文

李晓玲, 冯彦翔, 张广辉, 等. 混合离散蛙跳算法求解柔性装配系统调度问题. 控制理论与应用, 2025, 42(4): 816 – 826

复制

LI Xiaoling, FENG Yanxiang, ZHANG Guanghui, et al. Hybrid discrete shuffled frog leaping algorithm for the scheduling problem of flexible assembly systems. Control Theory & Applications, 2025, 42(4): 816 – 826

Copy

计量

图1FAS示意图及其Petri网模型

Fig.1Example of an FAS and its Petri net model

图2一个可行个体S及其解码序列JO（S）

Fig.2A feasible individual S and its JO (S)

图3交叉操作产生新个体

Fig.3New individual generated from P₁ and P₂

图4HDSFLA流程图

Fig.4Flowchart of HDSFLA

图5测试FAS的Petri网模型

Fig.5Petri net model of the test FAS

表1算法 2 IM算法

Table1Algorithm 2 IM algorithm

表2EFT策略

Table2EFT strategy

表3工件的加工时间

Table3Processing time of operations

表4算法参数水平设置

Table4Parameters and their factor levels

表5HDSFLA和其他3种DSFLA的实验结果

Table5Experimental results of HDSFLA and 3 other DSFLA

表6HDSFLA和6种比较算法的实验结果

Table6Experimental results of HDSFLA and 6 comparison algorithms

FRAMINAN J M, GONZALEZ P P, VIAGAS V F. Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures. European Journal of Operational Research,2019,273(2):401-417.

KOMAKI G M, SHEIKH S, MALAKOOTI B. Flow shop scheduling problems with assembly operations: A review and new trends. International Journal of Production Research,2020,57(10):2926-2955.

CHEN Yaling, LEI Deming. An imperialist competition and cooperation algorithm for distributed two-stage assembly flow shop scheduling. Control Theory & Applications,2021,38(12):1957-1967.(陈雅玲, 雷德明. 求解分布式两阶段装配流水车间调度的帝国竞争-—协作算法. 控制理论与应用,2021,38(12):1957-1967.)

WU C C, CHEN J Y, LIN W C,et al. A two-stage three-machine assembly flow shop scheduling with learning consideration to minimize the flowtime by six hybrids of particle swarm optimization. Swarm and Evolutionary Computation,2018,41:97-110.

KOMAKI G M, TEYMOURIAN E, KAYVANFAR V,et al. Improved discrete cuckoo optimization algorithm for the three-stage assembly flowshop scheduling problem. Computers & Industrial Engineering,2017,105:158-173.

ZHANG Z K, TANG Q H, CHICA M. Maintenance costs and makespan minimization for assembly permutation flow shop scheduling by considering preventive and corrective maintenance. Journal of Manufacturing Systems,2021,59:549-564.

SHAO Z S, SHAO W S, PI D C. Effective constructive heuristic and metaheuristic for the distributed assembly blocking flow-shop scheduling problem. Applied Intelligence,2020,50(12):4647-4669.

ZHAO F Q, SHAO D Q, WANG L,et al. An effective water wave optimization algorithm with problem-specific knowledge for the distributed assembly blocking flow-shop scheduling problem. Knowledge-Based Systems,2022,243:108471.

ZHAO F Q, DI S L, WANG L,et al. A self-learning hyper-heuristic for the distributed assembly blocking flow shop scheduling problem with total flowtime criterion. Engineering Applications of Artificial Intelligence,2022,116:105418.

ZHANG Z Q, HU R, QIAN B,et al. A matrix cube-based estimation of distribution algorithm for the energy-efficient distributed assembly permutation flow-shop scheduling problem. Expert Systems With Applications,2022,194:116484.

SHI F, ZHAO S K, MENG Y. Hybrid algorithm based on improved extended shifting bottleneck procedure and GA for assembly job shop scheduling problem. International Journal of Production Research,2020,58(9):2604-2625.

CHENG L X, TANG Q H, ZHANG L P,et al. Inventory and total completion time minimization for assembly job-shop scheduling considering material integrity and assembly sequential constraint. Journal of Manufacturing Systems,2022,65:660-672.

ZHANG S C, WANG S Y. Flexible assembly job-shop scheduling with sequence-dependent setup times and part sharing in a dynamic environment: Constraint programming model,mixed-integer programming model,and dispatching rules. IEEE Transactions on Engineering Management,2018,65(3):487-504.

WU X L, LIU X J, ZHAO N. An improved differential evolution algorithm for solving a distributed assembly flexible job shop scheduling problem. Memetic Computing,2019,11(4):335-355.

ZHANG S C, LI X, ZHANG B W,et al. Multi-objective optimisation in flexible assembly job shop scheduling using a distributed ant colony system. European Journal of Operational Research,2020,283(2):441-460.

XU J Y, NAGI R. Solving assembly scheduling problems with treestructure precedence constraints: A lagrangian relaxation approach. IEEE Transactions on Automation Science and Engineering,2013,10(3):757-771.

LI X L, XING K Y, LU Q C. Hybrid particle swarm optimization algorithm for scheduling flexible assembly systems with blocking and deadlock constraints. Engineering Applications of Artificial Intelligence,2021,105:104411.

ZHANG G H, XING K Y, CAO F. Discrete differential evolution algorithm for distributed blocking flowshop scheduling with makespan criterion. Engineering Applications of Artificial Intelligence,2018,76:96-107.

MIYATA H H, NAGANO M S. The blocking flow shop scheduling problem: A comprehensive and conceptual review. Expert Systems With Applications,2019,137:130-156.

LIU S Q, KOZAN E, MASOUD M,et al. Job shop scheduling with a combination of four buffering constraints. International Journal of Production Research,2018,56(9):3274-3293.

LE C V, PANG C K. Robust total energy optimization of flexible manufacturing systems based on renyi mean-entropy criterion. IEEE Transactions on Automation Science and Engineering,2016,13(1):355-367.

MEJIA G, CABALLERO-VILLALOBOS J P, MONTOYA C. Petri nets and deadlock-free scheduling of open shop manufacturing systems. IEEE Transactions on Systems, Man,and Cybernetics: Systems,2018,48(6):1017-1028.

LI Z W, WU N Q, ZHOU M C. Deadlock control of automated manufacturing systems based on petri nets-a literature review. IEEE Transactions on Systems, Man,and Cybernetics Part C-Applications and Reviews,2012,42(4):437-462.

XING K Y, WANG F, ZHOU M C,et al. Deadlock characterization and control of flexible assembly systems with petri net. Automatica,2018,87:358-364.

EUSUFF M M, LANSEY K E, PASHA F. Shuffled frog-leaping algorithm: A memetic meta-heuristic for discrete optimization. Engineering Optimization,2006,38(2):129-154.

MURATA T. Petri nets: Properties,analysis and applications. Proceedings of the IEEE,1989,77(4):541-580.

LUO J C, LIU Z Q, ZHOU M C. A petri net-based deadlock avoidance policy for flexible manufacturing systems with assembly operations and multiple resource acquisition. IEEE Transactions on Industrial Informatics,2019,15(6):3379-3387.

LI X L, XING K Y, WU Y C,et al. Total energy consumption optimization via genetic algorithm in flexible manufacturing systems. Computers & Industrial Engineering,2017,104(C):188-200.

MIRJALILI S, MIRJALILI S M, LEWIS A. Grey wolf optimizer. Advances In Engineering Software,2014,69:46-61.

TANABE R, FUKUNAGA A. Success-history based parameter adaptation for differential evolution. Proceedings of 2013 IEEE Congress on Evolutionary Computation. Cancún: IEEE,2013:71-78.

BREST J, MAUCEC M S, BOSKOVIC B. Single objective realparameter optimization: Algorithm jSO. Proceedings of 2017 IEEE Congress on Evolutionary Computation. San Sebastian: IEEE,2017:1311-1318.