An IMBOA Based Collaborative Sequencing Method for Automotive Multi Associated Workshops

doi:10.3969/j.issn.1004-132X.2025.08.015

Abstract

Abstract:

To meet the different body production sequence requirements of the automotive body welding， painting and final assembly workshops while aiming to minimize production line downtime and costs， a mathematical model for collaborative car sequencing optimization of multi-related workshops was established， and a collaborative sequencing method was proposed based on the IMBOA. To efficiently obtain the collaborative sequencing scheme for multiple associated workshops that aligned with individual migratory birds， a decoding strategy was designed based on heuristic scheduling rules. Addressing the limitation of a single neighborhood structure in IMBOA， a leading bird evolution strategy relying on multiple neighborhood structures was developed. To improve the global optimization ability of the algorithm， a bird following evolution strategy combining crossover and neighborhood search was designed. Finally， taking a new energy vehicle production line as an example， a simulation analysis platform for collaborative sequencing of multiple associated workshops for the entire vehicle was developed to verify the proposed sequencing method. Simulation experimental results show that compared with methods such as improved genetic algorithm （IGA） and improved ant colony algorithm （IACOA）， the designed IMBOA may obtain a better solution set.

Key words: car sequencing problem, improved migrating bird optimization algorithm（IMBOA）, automotive assembly, automotive welding, automotive painting

摘要：

为了满足汽车整车焊装、涂装及总装车间不同的车身排产序列需求，以最小化产线停产时间和成本为综合优化目标，建立了整车多关联车间协同排产优化数学模型，并设计了一种基于改进候鸟优化算法的协同排产方法。为了快速获取候鸟个体对应的多关联车间协同排产方案，设计了基于启发式排产规则的解码策略；针对传统候鸟优化算法邻域结构单一导致算法收敛速度慢的缺陷，设计了基于多种邻域结构的领飞鸟进化策略；为了提升算法的全局寻优能力，设计了融合交叉与邻域搜索的跟飞鸟进化策略。最后以某新能源汽车生产线为实例，开发了整车多关联车间协同排产仿真分析平台以验证所提排产方法。仿真实验结果表明，与改进的遗传算法、改进的蚁群算法等方法相比，所设计的改进候鸟优化算法能够获得更优的解集。

关键词: 汽车排产问题, 改进候鸟优化算法, 汽车总装, 汽车焊装, 汽车涂装

CLC Number:

TP278

Haining XIAO, Huihui SUN, Minghua PENG, Jianzhou WANG. An IMBOA Based Collaborative Sequencing Method for Automotive Multi Associated Workshops[J]. China Mechanical Engineering, 2025, 36(8): 1796-1810.

肖海宁, 孙慧慧, 彭明花, 王健洲. 基于改进候鸟优化算法的整车多关联车间协同排产方法[J]. 中国机械工程, 2025, 36(8): 1796-1810.

Figures/Tables 20

Fig.1 A new energy vehicle production line using a stereoscopic warehouse as the car body buffer area

Tab. 1 Symbol definition

符号	定义
$N Q$	客户订单总数
$Q i = (D i, C i, O i, t i Q E)$	第 $i$ 个客户的订单信息
$N D$	可选车型的总数
$D i$	客户订单 $Q i$ 的车型编码， $D i ∈ A, B, C, ⋯$
$N C$	可选车身颜色总数
$C i$	客户订单 $Q i$ 的车身色编码， $C i ∈ 红, 白, 蓝, ⋯$
$O i ∈ H, M, L$	客户订单 $Q i$ 的配置编码，H：高配置，M：中配置，L：低配置
$t i Q E$	客户订单 $Q i$ 的合同约定交付时间
$t i Q K$	客户订单 $Q i$ 的实际交付时间
$λ$	订单拖期违约金支付系数
$Ω Q = {Q i \| i ∈ N 且$ $1 ≤ i ≤ N Q}$	客户订单的集合
$S W (Q i)$	客户订单 $Q i$ 在焊装车间的排产序号
$Ω W = S W (Q i) \| ∀ Q i ∈ Ω Q$	焊装车间排产序号集合
$S P (Q i)$	客户订单 $Q i$ 在涂装车间的排产序号
$Ω P = S P (Q i) \| ∀ Q i ∈ Ω Q$	所有客户订单在涂装车间的排产序号集合
$S A (Q i)$	客户订单 $Q i$ 在总装车间的排产序号
$Ω A = S A (Q i) \| ∀ Q i ∈ Ω Q$	所有客户订单在总装车间的排产序号集合
$T$	生产节拍
$a C$	涂装车间单次换色所需成本
$Ω J = {J j \| j ∈ N 且$ $1 ≤ j ≤ N J}$	关键重要零部件的集合
$N J$	关键重要零部件的种类数
$θ W$	焊装车间单次切换车型造成的停产时间
$μ W$	焊装车间单次切换车型增加的生产成本
$N W C$	焊装车间排产序列车型切换次数
$S i, j$	涂装车间相邻车身颜色是否不同，为1表示颜色不同，反之为0
$N W M I N$	焊装车间最小批量，每批次批量为 $N W M I N$ 的整数倍
$N C M A X$	在无需清洗喷枪的前提下，涂装车间能够连续喷涂的车身数
$θ C$	涂装车间单次切换颜色造成的停产时间
$N C C$	涂装车间连续喷涂相同颜色车身时的喷枪清洗次数
$T ¯ p r$	总装车间各工位工人所需的休息时间平均值
$T i a p$	总装车间某工位装配第 $i$ 辆车后产生的休息时间拖欠额
$T ¯ a p$	各订单装配后休息时间拖欠额的平均值
$T a s$	总装车间某工位装配作业所需工时
$a f$	总装车间各订单平均返修一次所需成本
$δ (T ¯ a p)$	总装车间订单平均返修率
$x n, j ∈ 0,1$	总装车间排产顺序编号为 $n$ 的车辆是否装关键重要零部件 $J j$ ，1：装，0：不选装
$V ¯ j$	总装车间所有客户订单对关键重要零部件 $J j$ 的平均消耗速率
$V ¯ j r$	总装车间前 $r$ 个排产序列对关键重要零部件 $J j$ 的平均消耗速率
$a V ¯$	总装车间平均物料供应成本
$N m a x V$	立体库车位容量
$N m a x T W$	立体库对白车身调序的最大范围
$N m a x T P$	立体库对彩车身调序的最大范围

Tab. 1 Symbol definition

符号	定义
$N Q$	客户订单总数
$Q i = (D i, C i, O i, t i Q E)$	第 $i$ 个客户的订单信息
$N D$	可选车型的总数
$D i$	客户订单 $Q i$ 的车型编码， $D i ∈ A, B, C, ⋯$
$N C$	可选车身颜色总数
$C i$	客户订单 $Q i$ 的车身色编码， $C i ∈ 红, 白, 蓝, ⋯$
$O i ∈ H, M, L$	客户订单 $Q i$ 的配置编码，H：高配置，M：中配置，L：低配置
$t i Q E$	客户订单 $Q i$ 的合同约定交付时间
$t i Q K$	客户订单 $Q i$ 的实际交付时间
$λ$	订单拖期违约金支付系数
$Ω Q = {Q i \| i ∈ N 且$ $1 ≤ i ≤ N Q}$	客户订单的集合
$S W (Q i)$	客户订单 $Q i$ 在焊装车间的排产序号
$Ω W = S W (Q i) \| ∀ Q i ∈ Ω Q$	焊装车间排产序号集合
$S P (Q i)$	客户订单 $Q i$ 在涂装车间的排产序号
$Ω P = S P (Q i) \| ∀ Q i ∈ Ω Q$	所有客户订单在涂装车间的排产序号集合
$S A (Q i)$	客户订单 $Q i$ 在总装车间的排产序号
$Ω A = S A (Q i) \| ∀ Q i ∈ Ω Q$	所有客户订单在总装车间的排产序号集合
$T$	生产节拍
$a C$	涂装车间单次换色所需成本
$Ω J = {J j \| j ∈ N 且$ $1 ≤ j ≤ N J}$	关键重要零部件的集合
$N J$	关键重要零部件的种类数
$θ W$	焊装车间单次切换车型造成的停产时间
$μ W$	焊装车间单次切换车型增加的生产成本
$N W C$	焊装车间排产序列车型切换次数
$S i, j$	涂装车间相邻车身颜色是否不同，为1表示颜色不同，反之为0
$N W M I N$	焊装车间最小批量，每批次批量为 $N W M I N$ 的整数倍
$N C M A X$	在无需清洗喷枪的前提下，涂装车间能够连续喷涂的车身数
$θ C$	涂装车间单次切换颜色造成的停产时间
$N C C$	涂装车间连续喷涂相同颜色车身时的喷枪清洗次数
$T ¯ p r$	总装车间各工位工人所需的休息时间平均值
$T i a p$	总装车间某工位装配第 $i$ 辆车后产生的休息时间拖欠额
$T ¯ a p$	各订单装配后休息时间拖欠额的平均值
$T a s$	总装车间某工位装配作业所需工时
$a f$	总装车间各订单平均返修一次所需成本
$δ (T ¯ a p)$	总装车间订单平均返修率
$x n, j ∈ 0,1$	总装车间排产顺序编号为 $n$ 的车辆是否装关键重要零部件 $J j$ ，1：装，0：不选装
$V ¯ j$	总装车间所有客户订单对关键重要零部件 $J j$ 的平均消耗速率
$V ¯ j r$	总装车间前 $r$ 个排产序列对关键重要零部件 $J j$ 的平均消耗速率
$a V ¯$	总装车间平均物料供应成本
$N m a x V$	立体库车位容量
$N m a x T W$	立体库对白车身调序的最大范围
$N m a x T P$	立体库对彩车身调序的最大范围

Fig.2 Flowchart of the IMBOA based collaborative sequencing method

Tab.2 Customer order information list

$Q i$	$C i$ 对应车型	$C i$ 对应颜色	$O i$	$t i Q E$ /月/日
1	A	白	H	6/1
2	B	黑	L	6/2
3	C	白	M	6/3
4	A	红	L	6/3
5	A	红	M	6/2
6	C	白	H	6/3
7	A	黑	L	6/1
8	B	白	L	6/2
9	C	红	L	6/1
10	A	红	M	6/2
11	A	白	H	6/1
12	C	黑	M	6/3
13	A	白	L	6/2
14	B	红	L	6/3
15	C	红	M	6/1
16	A	白	L	6/2
17	B	黑	M	6/1
18	C	白	M	6/2

Tab.2 Customer order information list

$Q i$	$C i$ 对应车型	$C i$ 对应颜色	$O i$	$t i Q E$ /月/日
1	A	白	H	6/1
2	B	黑	L	6/2
3	C	白	M	6/3
4	A	红	L	6/3
5	A	红	M	6/2
6	C	白	H	6/3
7	A	黑	L	6/1
8	B	白	L	6/2
9	C	红	L	6/1
10	A	红	M	6/2
11	A	白	H	6/1
12	C	黑	M	6/3
13	A	白	L	6/2
14	B	红	L	6/3
15	C	红	M	6/1
16	A	白	L	6/2
17	B	黑	M	6/1
18	C	白	M	6/2

Tab.3 The number， batch and lot information of the car bodies to be produced for each car model

车型	所需数量	批量 $N W M I N$	批次数
A	8	3	3
B	4	3	2
C	6	3	2

Tab.3 The number， batch and lot information of the car bodies to be produced for each car model

车型	所需数量	批量 $N W M I N$	批次数
A	8	3	3
B	4	3	2
C	6	3	2

Fig.3 The decoding and evaluation process of the migrating birds based on heuristic rules

Tab.4 Each pre-sort result of the customer order collection

预排序次数	客户订单每次预排序后的订单编号序列
第一次	1，7，9，11，15，17，2，5，8，10，13，16，18，3，4，6，12，14
第二次	1，7，11，5，10，13，16，4，17，2，8，14，9，15，18，3，6，12
第三次	1，11， 13，16，7，5，10，4，17，2，8，14，9，15，18，3，6，12
第四次	13，1，16，11，7，4，5，10，2，17，8，14，15，9，18，3，6，12

Fig.4 Schematic diagram of production sequence decision in welding workshop

Fig.5 Schematic diagram of paint shop production sequence decision

Fig.6 Schematic diagram of production sequence decision in the final assembly workshop

Fig. 7 Schematic diagram of the migrating birds in the neighborhood based on reverse sorting

Fig.8 Schematic diagram of the migrating birds in the neighborhood based on single-point mutation

Fig.9 Schematic diagram of the migrating birds in the neighborhood based on a right ring shift of 1 bit

Fig. 10 Schematic diagram of generating new migrating birds by crossing with following birds

Fig.11 IGD values corresponding to each approximate Pareto optimal migratory bird set of each algorithm at each time

Fig.12 HV values corresponding to each approximate Pareto optimal migratory bird set of each algorithm at each time

Fig.13 Approximate Pareto optimal migratory bird set corresponding to the optimal IGD of each algorithm

Fig.14 IGD values corresponding to the approximate Pareto solution set of each algorithm at each time

Fig.15 HV values corresponding to the approximate Pareto solution set of each algorithm at each time

Fig.16 Approximate Pareto optimal solutions corresponding to the optimal IGD of each algorithm

References 28

[1]	LU Chao， XIAO Shengqiang， LI Xinyu， et al. An Effective Multi-objective Discrete Grey Wolf Optimizer for a Real-world Scheduling Problem in Welding Production［J］. Advances in Engineering Software， 2016， 99（C）：161-176.
[2]	孟磊磊，张超勇，邵新宇，等. 基于约束规划的焊接车间多资源约束调度研究［J］. 华中科技大学学报（自然科学版）， 2018， 46（6）：1-7.
	MENG Leilei， ZHANG Chaoyong， SHAO Xinyu， et al. Constraint Programming for Multi-resource Constrained Welding Shop Scheduling［J］. Journal of Huazhong University of Science and Technology （Natural Science Edition）， 2018， 46（6）：1-7.
[3]	WANG Jingjing， WANG Ling， XIU Xia. A Cooperative Memetic Algorithm for Energy-aware Distributed Welding Shop Scheduling Problem［J］. Engineering Applications of Artificial Intelligence， 2023， 120：105877.
[4]	WANG Cuiyu， ZHAO Li， LI Xinyu， et al. An Improved Grey Wolf Optimizer for Welding Shop Inverse Scheduling［J］. Computers & Industrial Engineering， 2022， 163：107809.
[5]	RAO Yunqing， MENG Ronghua， ZHA Jing， et al. Bi-objective Mathematical Model and Improved Algorithm for Optimisation of Welding Shop Scheduling Problem［J］. International Journal of Production Research， 2020， 58（9）：2767-2783.
[6]	KRYSTEK J， BYSKO S. The Follow-up Control of the Body Sequencing Process at the Paint Shop［J］. Mechanik， 2019（7）：462-464.
[7]	WINTER F， MUSLIU N. Constraint-based Scheduling for Paint Shops in the Automotive Supply Industry［J］. ACM Transactions on Intelligent Systems and Technology， 2021， 12（2）：1-25.
[8]	CHUTIMA P， SUCHANUN T. Productivity Improvement with Parallel Adjacent U-shaped Assembly Lines［J］. Advances in Production Engineering & Management， 2019， 14（1）：51-64.
[9]	THIRUVADY D， MORGAN K， AMIR A， et al. Large Neighbourhood Search Based on Mixed Integer Programming and Ant Colony Optimisation for Car Sequencing［J］. International Journal of Production Research， 2020， 58（9）：2696-2711.
[10]	李燚，唐倩，刘联超，等. 基于改进蚁群算法的汽车混流装配调度模型求解［J］. 中国机械工程， 2021， 32（9）： 1126-1133.
	LI Yi， TANG Qian， LIU Lianchao， et al. An Improved ACO Algorithm for Automobile Mixed-flow Assembly Scheduling Problems［J］. China Mechanical Engineering， 2021， 32（9）：1126-1133.
[11]	ZHANG Beikun， XU Liyun， ZHANG Jian. A Multi-objective Cellular Genetic Algorithm for Energy-oriented Balancing and Sequencing Problem of Mixed-model Assembly Line［J］. Journal of Cleaner Production， 2020， 244：118845.
[12]	LOUIS A， ALPAN G， PENZ B， et al. Mixed-model Sequencing versus Car Sequencing： Comparison of Feasible Solution Spaces［J］. International Journal of Production Research， 2023， 61（10）：3415-3434.
[13]	SHI Xiaolin， TIAN Xitian， GU Jianguo， et al. A Hybrid Approach of Case- and Rule-based Reasoning to Assembly Sequence Planning［J］. The International Journal of Advanced Manufacturing Technology， 2023， 127（1）：221-236.
[14]	GUO Kai， LIU Rui， DUAN Guijiang， et al. Research on Dynamic Decision-making for Product Assembly Sequence Based on Connector-linked Model and Deep Reinforcement Learning［J］. Journal of Manufacturing Systems， 2023， 71：451-473.
[15]	沈振宇，唐倩，黄涛，等. 面向均衡生产的多级流水车间调度模型求解［J］. 计算机集成制造系统， 2019， 25（11）：2743-2752.
	SHEN Zhenyu， TANG Qian， HUANG Tao， et al. Solution of Multistage Flow Shop Scheduling Model for Leveling Production［J］. Computer Integrated Manufacturing Systems， 2019， 25（11）：2743-2752.
[16]	杜宝钗. 多车间多产线工厂布局下的汽车关联排序问题［D］. 北京：北京交通大学， 2022.
	DU Baochai. Car Linkage Sequencing Problem for Multi Mixed-Assembly Lines in Multi Workshops ［D］. Beijing： Beijing Jiaotong University， 2022.
[17]	李聪波，赵德，杨秒，等. 汽车整车多级生产线协同排序优化方法［J］. 计算机集成制造系统， 2024， 30（6）：2025-2035.
	LI Congbo， ZHAO De， YANG Miao， et al. Collaborative Sequencing Optimization Method for Automobile Multi-stage Production Line［J］. Computer Integrated Manufacturing Systems， 2024， 30（6）：2025-2035.
[18]	WU Jiaxi， DING Yongkang， SHI Leyuan. Mathematical Modeling and Heuristic Approaches for a Multi-stage Car Sequencing Problem［J］. Computers & Industrial Engineering， 2021， 152：107008.
[19]	YANG Miao， LI Congbo， TANG Ying， et al. A Collaborative Resequencing Approach Enabled by Multi-core PREA for a Multi-stage Automotive Flow Shop［J］. Expert Systems with Applications， 2024， 237：121825.
[20]	王秋莲，段星皓. 基于高维多目标候鸟优化算法的柔性作业车间调度［J］. 中国机械工程， 2022， 33（21）：2601-2612.
	WANG Qiulian， DUAN Xinghao. Scheduling of Flexible Job Shop Based on High-dimension and Multi-objective Migrating Bird Optimization Algorithm［J］. China Mechanical Engineering， 2022， 33（21）：2601-2612.
[21]	ZHANG Zikai， TANG Qiuhua， HAN Dayong， et al. Multi-manned Assembly Line Balancing with Sequence-dependent Set-up Times Using an Enhanced Migrating Birds Optimization Algorithm［J］. Engineering Optimization， 2023， 55（7）：1243-1262.
[22]	FU Yaping， MA Xiaomeng， GAO Kaizhou， et al. Multi-objective Migrating Birds Optimization for Solving Stochastic Home Health Care Routing and Scheduling Problems Considering Caregiver Working Time Constraints［J］. Swarm and Evolutionary Computation， 2024， 85：101484.
[23]	肖海宁，楼佩煌，武星，等. 多载量自动导引车系统防死锁任务调度方法［J］. 计算机集成制造系统， 2022， 28（11）：3325-3339.
	XIAO Haining， LOU Peihuang， WU Xing， et al. Deadlock-free Dispatching Method for Multiple-load Automatic Guided Vehicle System［J］. Computer Integrated Manufacturing Systems， 2022， 28（11）：3325-3339.
[24]	ZITZLER E， THIELE L， LAUMANNS M， et al. Performance Assessment of Multiobjective Optimizers： an Analysis and Review［J］. IEEE Transactions on Evolutionary Computation， 2003， 7（2）：117-132.
[25]	GUERREIRO A P， FONSECA C M， PAQUETE L. The Hypervolume Indicator： Computational Problems and Algorithms［J］. ACM Computing Surveys， 2021， 54（6）：1-42.
[26]	KOUKA N， BENSAID F， FDHILA R， et al. A Novel Approach of Many-objective Particle Swarm Optimization with Cooperative Agents Based on an Inverted Generational Distance Indicator［J］. Information Sciences， 2023， 623：220-241.
[27]	SHANG Ke， ISHIBUCHI H， HE Linjun， et al. A Survey on the Hypervolume Indicator in Evolutionary Multiobjective Optimization［J］. IEEE Transactions on Evolutionary Computation， 2021， 25（1）：1-20.
[28]	王洪，吴立辉，陈达，等.基于孪生人工蜂鸟算法的多作业模式半导体封测环节调度［J］.中国机械工程，2024，35（2）：260-267.
	WANG Hong， WU Lihui， CHEN Da， et al. Scheduling in SAT in Multi-operation Mode Based on Artificial Hummingbird Algorithm with Twin Population［J］. China Mechanical Engineering， 2024， 35（2）：260-267.