Hyper-heuristic Three Dimensional EDA for Solving Green Two-Sided Assembly Line Balancing Problem

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

Abstract

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

CLC Number:

TP391.9

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.

Figures/Tables 14

Fig. 1

Fig. 2

Table 1

Symbol definition

符号	定义
$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关机；否则，保持开机

Table 1

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Table 2

Corresponding efficiency and energy consumption of different types of robots

机器人类型	效率ε	能耗
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)$

Table 2

Table 3

Table 4

Table 5

Table 6

Fig. 7

Fig. 8

References 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