超启发式三维EDA求解绿色双边装配线平衡问题

doi:10.16182/j.issn1004731x.joss.21-1134

摘要/Abstract

摘要：

针对绿色机器人的第I类双边装配线平衡问题(green robotic two-sided assembly line balancing problem of type-I， GRTALBP-I），建立问题模型并提出一种超启发式三维分布估计算法(hyper-heuristic three dimensional estimation of distribution algorithm， HH3DEDA)进行求解。在HH3DEDA中，结合问题特征，设计基于工序选择因子的组合编码，进而设计高低分层结构的HH3DEDA。在高层，采用三维概率矩阵学习优质高层个体中块结构及其分布信息，后通过采样该矩阵以生成新的高层个体，其中高层个体由结合问题特点设计的12种启发式操作的排列构成；在低层，将高层每个个体所确定启发式操作排列作为一种新的启发式算法对GRTALBP-I解空间执行较深入搜索。同时，引入机器人开关机节能策略，进一步提升所获取非支配解的质量。通过仿真对比实验，验证了所提算法的有效性。

关键词: 双边装配线平衡, 超启发算法, 三维分布估计算法, 多目标优化, 节能降耗

Abstract:

This paper establishes a model for green robotic two-sided assembly line balancing problem of type-I, and a hyper-heuristic three dimensional estimation of distribution algorithm (HH3DEDA) is proposed for solving this problem. In HH3DEDA, a combinatorial encoding rule based on process selectors is designed via considering the characteristics of the problem. Then, HH3DEDA with a high and low layered structure is proposed. In the upper layer, the three-dimensional probability matrix is utilized to learn high-quality high individual block structure and its distribution information, and then the matrix is sampled to generate new high level individuals. Each high individual is composed by 12 heuristic operations, which are designed via considering the characteristics of the problem. In the lower layer, the high individual determined heuristic operation permutation is used as a new heuristic to perform a deep search for the GRTALBP-I solution space. Meanwhile, the energy saving strategy of robot switching machine is utilized to enhance the quality of obtaining the non-dominated individuals. Simulation experiments demonstrate the effectiveness of the proposed algorithm.

Key words: two-sided assembly balancing, hyper-heuristic, three-dimensional distribution estimation algorithm, muti-objective optimization, saving energy and reducing consumption

中图分类号:

TP391.9

胡蓉, 丁帅, 钱斌, 张长胜. 超启发式三维EDA求解绿色双边装配线平衡问题[J]. 系统仿真学报, 2023, 35(3): 454-469.

Rong Hu, Shuai Ding, Bin Qian, Changsheng Zhang. Hyper-heuristic Three Dimensional EDA for Solving Green Two-Sided Assembly Line Balancing Problem[J]. Journal of System Simulation, 2023, 35(3): 454-469.

图/表 14

图1

图2

表1

符号定义表

符号	定义
$I$	工序集合 $I = {1, 2, ⋯, N t}, i, l, p ∈ I$
$J$	成对工位集合 $J = {1, 2, ⋯, N m}, j, h ∈ J$
$R$	机器人类型集合 $R = 1, 2, ⋯, m}, m ∈ R$ 其中r为类型m的机器人
$N t$	工序数量
$N m$	成对的工位数量
$N R r$	机器人r的可用数量
$N R$	可用机器人数量
$t i 0$	工序i的作业时间， $i ∈ I$
$t i r$	工序i使用机器人r的作业时间 $, i ∈ I, r ∈ R$
$t i f$	工序i的完工时间
$C T$	节拍时间
$t o f f_r$	机器人r关机所需时间
$t o n_r$	机器人r开机所需时间
$w t i r$	工序i完工后机器人r的空载时间
$W T i r$	满足条件的 $w t i r$ 构成的集合
$T m i n_r$	机器人r空载时，执行开关机所需的最小时间
$N r$	机器人r可执行开关机次数
$E C r$	机器人r每单位时间的能耗
$S E C r$	机器人r每单位时间的待机能耗
$E C o f f - o n$	机器人r执行开关机所需能耗
$E C s a v e$	机器人r执行开关机所节省的能耗
$E C j k$	成对工位j的k侧的能耗
$T E C$	总能耗
$K (i)$	工序i优先装配方向集合
$C (i)$	工序i装配方向相反的集合
$P 0$	没有直接前序任务的工序集合
$P (i)$	工序i的直接前序任务集合
$P a (i)$	工序i的所有前序任务集合
$S a (i)$	工序i的所有后序任务集合
$S (i)$	工序i的直接后序任务集合
$μ$	足够大的正整数
$P C$	位置约束的工序集合
$P Z$	积极区域约束的工序集合
$N Z$	消极区域约束的工序集合
$S C$	同步约束的工序集合
$x i j k$	如果工序i分配到工位 $(j, k)$ ，则值取1；否则为0
$y r j k$	如果机器人r分配到工位 $(j, k)$ ，则值取1；否则为0
$z i p$	如果在同一个工位内工序i早于工序p分配，值取1；否则取0
$α i j k$	如果 $α i j k = 1$ ，机器人r关机；否则，保持开机

表1

图3

图4

图5

图6

表2

不同类型机器人对应的效率和能耗

机器人类型	效率ε	能耗
R₁	$ε ∼ U (10, 30)$	$E C R 1 ∈ (0.5, 2.0)$
R₂	$ε ∼ U (20, 40)$	$E C R 2 ∈ (1.0, 2.5)$
R₃	$ε ∼ U (30, 50)$	$E C R 3 ∈ (1.5, 3.0)$

表2

表3

表4

表5

表6

图7

图8

参考文献 27

1	Salveson M E. The Assembly Line Balancing Problem[J]. Journal of Industrial Engineering (S2314-4882), 1955, 29(10): 55-101.
2	Li Zixiang, Kucukkoc Ibrahim, Mukund Nilakantan J. Comprehensive Review and Evaluation of Heuristics and Meta-Heuristics for Two-Sided Assembly Line Balancing Problem[J]. Computers and Operations Research (S0305-0548), 2017, 84: 146-161.
3	Muhammad Razif Abdullah Make, Mohd Fadzil Faisae Ab Rashid, Muhamad Magffierah Razali. A Review of Two-Sided Assembly Line Balancing Problem[J]. The International Journal of Advanced Manufacturing Technology (S0268-3768), 2017, 89: 1743-1763.
4	Li Zixiang, Tang Qiuhua, Zhang LiPing. Two-Sided Assembly Line Balancing Problem of Type I: Improvements, a Simple Algorithm and a Comprehensive Study[J]. Computers & Operations Research (S0305-0548), 2017, 79: 78-93.
5	Bartholdi J J. Balancing Two-Sided Assembly Lines: A Case Study[J]. International Journal of Production Research (S0020-7543), 1993, 31(10): 2447-2461.
6	Zhong Yuguang, Deng Zexiao, Xu Ke. An Effective Artificial Fish Swarm Optimization Algorithm for Two-Sided Assembly Line Balancing Problems[J]. Computers & Industrial Engineering (S0360-8352), 2019, 138: 106-121.
7	Zheng Xiaojun, Ning Shiduo, Sun Hao, et al. Solving Multi-objective Two-Sided Assembly Line Balancing Problems by Harmony Search Algorithm Based on Pareto Entropy[J]. IEEE Access (S2169-3536), 2021, 9: 121728-121742.
8	Li Dashuang, Zhang Chaoyong, Shao Xinyu, et al. A Multi-objective TLBO Algorithm for Balancing Two-Sided Assembly line with Multiple Constraints[J]. Journal of Intelligent Manufacturing (S0956-5515), 2016, 27(4): 725-739.
9	吴尔飞, 金烨, 汪峥. 双边装配线第二类平衡问题研究[J]. 计算机集成制造系统, 2005, 4(11): 1604-1608.
	Wu Erfei, Jin Ye, Wang Zheng. Study on the Second Kind of Balance Problem of Bilateral Assembly Line[J]. Computer Integrated Manufacturing Systems, 2005, 4(11): 1604-1608.
10	Ibrahim Kucukkoc, Zhang David Z. Type-E Parallel Two-Sided Assembly Line Balancing Problem: Mathema-Tical Model and Ant Colony Optimisation Based Approach with Optimized Parameters[J]. Computers and Industrial Engineering (S0360-8352), 2015, 84: 56-69.
11	Li Zixiang, Dey Nilanjan, Ashour Amira S, et al. Discrete Cuckoo Search Algorithms for Two-Sided Robotic Assembly Line Balancing Problem[J]. Neural Comput & Applic (S0941-0643), 2018, 30: 2685-2696.
12	Li Zixiang, Mukund Nilakantan Janardhanan, Tang Qiuhua, et al. Model and Metaheuristics for Robotic Two-Sided Assembly Line Balancing Problems with Setup Times-ScienceDirect[J]. Swarm and Evolutionary Computation (S2210-6502), 2019, 50: 567-583.
13	Wang Kaipu, Li Xinyu, Gao Liang. A Multi-objective Discrete Flower Pollination Algorithm for Stochastic Two-Sided Partial Disassembly Line Balancing Problem[J]. Computers & Industrial Engineering (S0360-8352), 2019, 130: 634-649.
14	Li Zixiang, Tang Qiuhua, Zhang Liping. Minimizing Energy Consumption and Cycle Time in Two-Sided Robotic Assembly Line Systems Using Restarted Simulated Annealing Algorithm[J]. Journal of Cleaner Production (S0959-6526), 2016, 135: 508-522.
15	Lin Jian. Backtracking Search Based Hyper-Heuristic for the Flexible Job-Shop Scheduling Problem with Fuzzy Processing Time[J]. Engineering Applications of Artificial Intelligence (S0952-1976), 2019, 77(1): 186-196.
16	Song Hongbo, Lin Jian. A Genetic Programming Hyper-Heuristic for the Distributed Assembly Permutation Flow-Shop Scheduling Problem with Sequence Dependent Setup Times[J]. Swarm and Evolutionary Computation (S2210-6502), 2021, 60: 100807.
17	钱斌, 佘明哲, 胡蓉, 等. 超启发式交叉熵算法求解模糊分布式流水线绿色调度问题[J]. 控制与决策, 2021, 36(6): 1387-1396.
	Qian Bin, She Mingzhe, Hu Rong, et al. Hyper-Heuristic Cross-Entropy Algorithm for Green Distributed Permutation Flow-Shop Scheduling Problem with Fuzzy Processing Time[J]. Journal of Control and Decision, 2021, 36(6): 1387-1396.
18	杨海军, 李建武, 李敏强. 进化算法的模式、涌现与困难性研究[M]. 北京: 科学出版社, 2012.
	Yang Haijun, Li Jianwu, Li Minqiang. Evolutionary Algorithms: Schema, Emergence and Hardness[M]. Beijing: Science Press, 2012.
19	李大双, 张超勇, 邵新宇, 等. 基于殖民竞争算法的多约束双边装配线平衡[J]. 机械工程学报, 2015, 51(2): 183-189.
	Li Dashuang, Zhang Chaoyong, Shao Xinyu, et al. Hybrid Colonial Competitive Algorithm for the Two-Sided Assembly Line Balancing Problem with Multiple Constraints[J]. Journal of Mechanical Engineering, 2015, 51(2): 183-189.
20	李大双, 张超勇, 邵新宇, 等. 基于多目标殖民竞争算法的随机型双边装配线[J]. 计算机集成制造系统, 2014, 20(11): 2774-2787.
	Li Dashuang, Zhang Chaoyong, Shao Xinyu, et al. Balancing Stochastic Two-Sided Assembly Line with Multi-objective Colonial Competitive Algorithm[J]. Computer Integrated Manufacturing Systems, 2014, 20(11): 2774-2787.
21	张子凯, 唐秋华, 张利平. 多重资源约束下的多目标U型装配线平衡[J]. 计算机集成制造系统, 2017, 23(11): 2431-2441.
	Zhang Zikai, Tang Qiuhua, Zhang Liping. Multi-objective U-Shaped Assembly Line Balancing under Multi-resource Restriction[J]. Computer Integrated Manufacturing Systems, 2017, 23(11): 100-110.
22	杨晓林, 胡蓉, 钱斌, 等. 增强分布估计算法求解低碳分布式流水线调度[J]. 控制理论与应用, 2019, 36(5): 803-815.
	Yang Xiaolin, Hu Rong, Qian Bin, et al. Enhanced Distribution Estimation Algorithm for Low Carbon Distributed Pipeline Scheduling[J]. Control Theory & Applications, 2019, 36(5): 803-815.
23	Pan Quanke, Ruiz Rubén. An Estimation of Distribution Algorithm for Lot-Streaming Flow Shop Problems with Setup Times[J]. Omega: The International Journal of Management Science (S0305-0483), 2011, 40(2): 166-180.
24	Du Yu, Li Junqing, Luo Chao, et al. A Hybrid Estimation of Distribution Algorithm for Distributed Flexible Job Shop Scheduling with Crane Transportations[J]. Swarm and Evolutionary Computation (S2210-6502), 2021, 62: 861-885.
25	Hackman S T, Magazine M J, Wee T S. Fast, Effective Algorithms for Simple Assembly Line Balancing Problems[J]. Operation Researsh (S0030-364X), 1989, 37(6): 916-924.
26	郑逸凡, 钱斌, 胡蓉, 等. CE-GA协同进化算法求解人机共同作业的U形装配线平衡问题[J]. 机械工程学报, 2020, 56(9): 199-214.
	Zheng Yifan, Qian Bin, Hu Rong, et al. CE-GA Co-evolutionary Algorithm for Solving U-Shaped Assembly Line Balancing Problem with Man-Robot Cooperation[J]. Journal of Mechanical Engineering, 2020, 56(9): 199-214.
27	Hisao Ishibuchi, Tadashi Yoshida, Tadahiko Murata. Balance Between Genetic Search and Local Search in Memetic Algorithms for Multiobjective Permutation Flowshop Scheduling[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 2003, 7(2): 204-223.

n	CT/s	HHGA		HHEDA		HH3DEDA
n	CT/s	R_N	N_N	R_N	N_N	R_N	N_N
12	5	0.568 6	0.75	0.650 2	1.10	0.871 7	5.75
12	6	0.495 0	1.20	0.607 4	2.90	0.811 7	6.30
12	8	0.595 8	0.80	0.687 6	0.95	0.825 9	6.50
12	9	0.550 0	1.70	0.614 7	2.20	0.897 1	6.85
16	15	0.538 3	2.20	0.636 7	2.75	0.863 3	5.70
16	16	0.421 0	1.50	0.383 6	1.50	0.768 3	5.95
16	20	0.391 7	1.85	0.408 3	3.50	0.777 4	4.60
16	21	0.409 3	1.70	0.546 7	2.70	0.826 7	4.80
24	20	0.370 5	1.50	0.688 7	1.70	0.847 3	5.35
24	25	0.421 0	2.00	0.623 4	3.00	0.783 3	6.10
24	30	0.316 7	1.15	0.587 0	2.80	0.821 9	5.85
24	40	0.393 3	1.00	0.665 0	2.35	0.885 2	5.20
65	326	0.523 3	2.10	0.790 5	2.40	0.585 0	3.50
65	381	0.501 7	2.20	0.525 8	3.10	0.704 9	4.65
65	435	0.346 9	1.40	0.753 3	2.70	0.877 4	3.80
65	490	0.601 1	2.25	0.637 1	3.25	0.830 2	5.45
65	544	0.461 9	1.90	0.734 5	3.20	0.682 5	3.45
148	255	0.466 7	1.30	0.678 3	2.80	0.813 0	4.10
148	306	0.568 3	2.35	0.580 0	2.10	0.760 5	3.95
148	357	0.364 3	1.10	0.734 8	2.90	0.801 7	4.05
148	459	0.475 0	1.80	0.768 3	3.10	0.641 2	2.90
148	510	0.686 6	2.45	0.641 4	3.00	0.826 6	4.50
205	188 8	0.617 8	2.50	0.615 0	2.40	0.733 3	3.30
205	226 6	0.541 7	1.50	0.672 6	1.90	0.600 0	3.15
205	245 4	0.586 7	1.40	0.480 0	1.30	0.758 3	2.25
205	264 3	0.436 7	1.50	0.425 0	1.70	0.747 6	3.50
205	283 2	0.347 6	1.00	0.503 3	1.60	0.825 0	2.70

n	CT/s	ITLBO		IMMOGLS		HH3DEDA		n	CT/s	ITLBO		IMMOGLS		HH3DEDA
n	CT/s	R_N	N_N	R_N	N_N	R_N	N_N	n	CT/s	R_N	N_N	R_N	N_N	R_N	N_N
12	5	0.223 6	0.85	0.041 7	0.25	0.9272	6.25	65	435	0.140 7	0.70	0.070 4	0.25	0.960 8	5.75
12	6	0.020 0	0.15	0.156 7	0.75	0.966 7	7.65	65	490	0.116 3	0.40	0.086 7	0.25	0.933 7	5.25
12	8	0	0	0	0	1.000 0	6.65	65	544	0.151 7	0.45	0.095 1	0.40	0.849 1	6.05
12	9	0.083 3	0.35	0	0	0.971 4	6.30	148	255	0.154 2	0.55	0.112 8	0.60	0.916 3	7.45
16	15	0.223 8	0.90	0.044 6	0.25	0.962 8	7.45	148	306	0.170 4	0.45	0.092 5	0.40	0.965 6	6.55
16	16	0.098 2	0.55	0.125 6	0.45	0.887 1	6.30	148	357	0.186 7	0.60	0.223 2	1.00	0.891 7	6.05
16	20	0.075 0	0.10	0.035 0	0.10	0.947 5	6.35	148	459	0.191 8	0.90	0.111 7	0.40	0.940 8	7.95
16	21	0.202 1	0.50	0.666 7	0.20	0.962 6	8.40	148	510	0.148 0	0.60	0.114 3	0.45	0.925 1	7.15
24	20	0.154 6	0.65	0.215 4	0.60	0.883 3	6.40	205	188 8	0.033 8	0.20	0.477 1	2.00	0.849 2	3.85
24	25	0.104 5	0.50	0.162 1	0.60	0.907 6	6.10	205	226 6	0.006 3	0.05	0.326 7	0.65	0.858 3	3.45
24	30	0.076 7	0.30	0.023 8	0.10	0.990 0	5.70	205	245 4	0.112 5	0.15	0.277 5	1.05	0.915 0	3.55
24	40	0.018 3	0.10	0	0	1.000 0	5.35	205	264 3	0.050 0	0.10	0.104 2	0.25	0.969 1	4.20
65	326	0.161 7	0.65	0.128 0	0.40	0.971 7	6.10	205	283 2	0.050 0	0.05	0.079 2	0.25	1.000 0	4.85
65	381	0.070 8	0.30	0.071 2	0.35	0.973 3	6.85

[1]	王旭, 季伟东, 周国辉, 杨佳慧. 基于多指标精英个体博弈机制的多目标优化算法[J]. 系统仿真学报, 2023, 35(3): 494-514.
[2]	张朝阳, 徐莉萍, 李健, 赵义豪, 何奎. 基于改进狼群算法的柔性作业车间调度研究[J]. 系统仿真学报, 2023, 35(3): 534-543.
[3]	季伟东, 岳玉麒, 王旭, 林平. 基于降维和聚类的大规模多目标自然计算方法[J]. 系统仿真学报, 2023, 35(1): 41-56.
[4]	闫秀英, 党苗苗. 基于改进多目标粒子群算法的家庭用电时段优化[J]. 系统仿真学报, 2022, 34(1): 70-78.
[5]	张洪亮, 丁仁曼, 徐公杰. 考虑区间工时的多目标柔性作业车间节能调度[J]. 系统仿真学报, 2022, 34(09): 1976-1987.
[6]	冉险生, 杨静, 罗领, 陈凯. 多任务并行的摩托车悬架系统参数多目标优化[J]. 系统仿真学报, 2021, 33(5): 1216-1223.
[7]	汪润鸿, 王红军, 邹湘军, 曾泽钦, 李慧, 黄钊丰, 刘伟良. 基于混合粒子群算法的组合式变速箱传动比优化研究[J]. 系统仿真学报, 2021, 33(4): 825-836.
[8]	王洪峰, 张翼天, 陈景泽. 一种面向需求不确定性供应链的进化多目标仿真优化方法[J]. 系统仿真学报, 2021, 33(12): 2761-2770.
[9]	李霏, 苏中. 基于自适应免疫优化的污水处理过程控制[J]. 系统仿真学报, 2021, 33(12): 3012-3020.
[10]	魏乐, 李希金. 基于多目标的含风电场动态环境经济调度[J]. 系统仿真学报, 2020, 32(9): 1825-1830.
[11]	王晓锋, 陈阳, 张光杰, 陈建宇. 面向网络仿真拓扑的多目标优化映射方法[J]. 系统仿真学报, 2020, 32(8): 1436-1445.
[12]	张小雨, 邵春福. 城乡结合部道路交叉口多目标信号配时优化模型[J]. 系统仿真学报, 2020, 32(4): 709-717.
[13]	卿东升, 张晓芳, 李建军, 郭瑞, 邓巧玲. 基于蜂群-粒子群算法的天然林空间结构优化[J]. 系统仿真学报, 2020, 32(3): 371-381.
[14]	田红军, 汪镭, 吴启迪. 基于多目标进化算法混合框架的MOEA/D算法[J]. 系统仿真学报, 2020, 32(2): 201-216.
[15]	丁宇, 王艳, 纪志成. 柔性作业车间生产与能耗协同优化决策方法[J]. 系统仿真学报, 2020, 32(12): 2426-2437.