An efficient migrating birds optimization algorithm with idle time reduction for Type-I multi-manned assembly line balancing problem

doi:10.23919/JSEE.2021.000025

Journal of Systems Engineering and Electronics ›› 2021, Vol. 32 ›› Issue (2): 286-296.doi: 10.23919/JSEE.2021.000025

• INTELLIGENT OPTIMIZATION AND SCHEDULING • Previous Articles Next Articles

An efficient migrating birds optimization algorithm with idle time reduction for Type-I multi-manned assembly line balancing problem

Zikai ZHANG^1,²(), Qiuhua TANG^1,^2,*(), Zixiang LI^1,²(), Dayong HAN^1,²()

¹ Key Laboratory of Metallurgical Equipment and Control Technology, Wuhan University of Science and Technology, Wuhan 430081, China
² Hubei Key Laboratory of Mechanical Transmission and Manufacturing Engineering, Wuhan University of Science and Technology, Wuhan 430081, China

Received:2020-10-15 Online:2021-04-29 Published:2021-04-29
Contact: Qiuhua TANG E-mail:zhangzikai0703@gmail.com;tangqiuhua@wust.edu.cn;zixiangliwust@gmail.com;Wust_han@163.com
About author:|ZHANG Zikai was born in 1994. He received his B.S. degree in industrial engineering from Wuhan University of Science and Technology, in 2016, where he is currently pursuing his Ph.D. degree in mechanical engineering. His research interests include assembly line balancing, assembly flow shop scheduling and optimization algorithms. E-mail: zhangzikai0703@gmail.com||TANG Qiuhua was born in 1970. She received her B.S. degree in process and equipment of machinery manufacturing from Northeastern University, in 1992, master’s degree in mechanical design and theory and Ph.D. degree from Wuhan University of Science and Technology. Since 1992, she has been working with Wuhan University of Science and Technology, and was promoted to professor, in 2009. Her research interests include production process planning and scheduling, manufacturing process monitoring and control, and modern optimization methods and algorithms. She has published more than 100 papers in academic journals and conferences. E-mail: tangqiuhua@wust.edu.cn||LI Zixiang was born in 1990. He received his Ph.D. degree from Wuhan University of Science and Technology in 2018. He is currently a lecturer at Wuhan University of Science and Technology, China. His research interests include assembly line balancing, scheduling and metaheuristics. E-mail: zixiangliwust@gmail.com||HAN Dayong was born in 1990. He received his master’s degree in mechanical design and theory from Wuhan University of Science and Technology, in 2017, where he is currently pursuing his Ph.D. degree in mechanical engineering. His research interests include intelligent optimization algorithms and exact algorithms within flow-shop scheduling problems. E-mail: Wust_han@163.com
Supported by:
This work was supported by the National Natural Science Foundation of China (51875421; 61803287);This work was supported by the National Natural Science Foundation of China (51875421; 61803287)

Abstract

Abstract:

Multi-manned assembly line, which is broadly utilized to assemble high volume products such as automobiles and trucks, allows a group of workers to assemble different tasks simultaneously in a multi-manned workstation. This additional characteristic of parallel operators increases the complexity of the traditional NP-hard assembly line balancing problem. Hence, this paper formulates the Type-I multi-manned assembly line balancing problem to minimize the total number of workstations and operators, and develops an efficient migrating birds optimization algorithm embedded into an idle time reduction method. In this algorithm, a new decoding mechanism is proposed which reduces the sequence-dependent idle time by some task assignment rules; three effective neighborhoods are developed to make refinement of existing solutions in the bird improvement phases; and temperature acceptance and competitive mechanism are employed to avoid being trapped in the local optimum. Comparison experiments suggest that the new decoding and improvements are effective and the proposed algorithm outperforms the compared algorithms.

Key words: multi-manned, assembly line balancing, migrating birds optimization, meta-heuristics

Zikai ZHANG, Qiuhua TANG, Zixiang LI, Dayong HAN. An efficient migrating birds optimization algorithm with idle time reduction for Type-I multi-manned assembly line balancing problem[J]. Journal of Systems Engineering and Electronics, 2021, 32(2): 286-296.

Figures/Tables 12

Table 1

Fig.1

Fig.2

Table 2

Fig.3

Fig.4

Fig.5

Table 3

Table 4

Table 5

Fig.6

Fig.7

References 34

1	BOYSEN N, FLIEDNER M A classification of assembly line balancing problems. European Journal of Operational Research, 2007, 183 (2): 674- 693. doi: 10.1016/j.ejor.2006.10.010
2	EREL E, SARIN S A survey of the assembly line balancing procedures. Production Planning & Control, 1998, 9 (5): 414- 434.
3	AKAGI F, OSAKI H, KIKUCHI S A method for assembly line balancing with more than one worker in each station. International Journal of Production Research, 1983, 21 (5): 755- 770. doi: 10.1080/00207548308942409
4	CHEN Y Y, CHENG C Y, LI J Y Resource-constrained assembly line balancing problems with multi-manned workstations. Journal of Manufacturing Systems, 2018, 48 (Part A): 107- 119. doi: 10.1016/j.jmsy.2018.07.001
5	ZHANG Z K, TANG Q H, LI Z X, et al Modelling and optimisation of energy-efficient U-shaped robotic assembly line balancing problems. International Journal of Production Research, 2018, 57 (17): 5520- 5537.
6	GOKCEN H, AGPAK K A goal programming approach to simple U-line balancing problem. European Journal of Operational Research, 2006, 171 (2): 577- 585. doi: 10.1016/j.ejor.2004.09.021
7	SEWELL E C, JACOBSON S H A branch, bound, and remember algorithm for the simple assembly line balancing problem. INFORMS Journal on Computing, 2012, 24 (3): 433- 442. doi: 10.1287/ijoc.1110.0462
8	LI Z X, KUCUKKOC I, ZHANG Z K Branch, bound and remember algorithm for U-shaped assembly line balancing problem. Computers & Industrial Engineering, 2018, 124, 24- 35.
9	BALAKRISHNAN J, CHENG C H, HO K C, et al The application of single-pass heuristics for U-lines. Journal of Manufacturing Systems, 2009, 28 (1): 28- 40. doi: 10.1016/j.jmsy.2009.05.001
10	STERNATZ J Enhanced multi-Hoffmann heuristic for efficiently solving real-world assembly line balancing problems in automotive industry. European Journal of Operational Research, 2014, 235 (3): 740- 754. doi: 10.1016/j.ejor.2013.11.005
11	LI M, TANG Q H, ZHENG Q X, et al Rules-based heuristic approach for the U-shaped assembly line balancing problem. Applied Mathematical Modelling, 2017, 48, 423- 439. doi: 10.1016/j.apm.2016.12.031
12	YU J F, YIN Y H Assembly line balancing based on an adaptive genetic algorithm. The International Journal of Advanced Manufacturing Technology, 2009, 48 (1−4): 347- 354. doi: 10.1007/s00170-009-2281-7
13	RABBANI M, KAZEMI S M, MANAVIZADEH N Mixed model U-line balancing type-1 problem: a new approach. Journal of Manufacturing Systems, 2012, 31 (2): 131- 138. doi: 10.1016/j.jmsy.2012.02.002
14	FATHI M, ALVAREZ M J, RODRIGUEZ V A new heuristic-based bi-objective simulated annealing method for U-shaped assembly line balancing. European Journal of Industrial Engineering, 2016, 10 (2): 145- 169. doi: 10.1504/EJIE.2016.075849
15	BAYKASOGLU A Multi-rule multi-objective simulated annealing algorithm for straight and U type assembly line balancing problems. Journal of Intelligent Manufacturing, 2006, 17 (2): 217- 232. doi: 10.1007/s10845-005-6638-y
16	AYDOGAN E K, DELICE Y, OZCAN U, et al Balancing stochastic U-lines using particle swarm optimization. Journal of Intelligent Manufacturing, 2016, 30 (1): 97- 111.
17	SABUNCUOGLU I, EREL E, ALP A Ant colony optimization for the single model U-type assembly line balancing problem. International Journal of Production Economics, 2009, 120 (2): 287- 300. doi: 10.1016/j.ijpe.2008.11.017
18	DIMITRIADIS S G Assembly line balancing and group working: a heuristic procedure for workers’ groups operating on the same product and workstation. Computers & Operations Research, 2006, 33 (9): 2757- 2774.
19	KELLEGOZ T, TOKLU B An efficient branch and bound algorithm for assembly line balancing problems with parallel multi-manned workstations. Computers & Operations Research, 2012, 39 (12): 3344- 3360.
20	MICHELS A S, LOPES T C, SIKORA C G S, et al A Benders’ decomposition algorithm with combinatorial cuts for the multi-manned assembly line balancing problem. European Journal of Operational Research, 2019, 278 (3): 796- 808. doi: 10.1016/j.ejor.2019.05.001
21	CIL Z A, KIZILAY D Constraint programming model for multi-manned assembly line balancing problem. Computers & Operations Research, 2020, 124, 105069.
22	KELLEGOZ T, TOKLU B A priority rule-based constructive heuristic and an improvement method for balancing assembly lines with parallel multi-manned workstations. International Journal of Production Research, 2015, 53 (3): 736- 756. doi: 10.1080/00207543.2014.920548
23	LOPES T C, PASTRE G V, MICHELS A S, et al Flexible multi-manned assembly line balancing problem: model, heuristic procedure, and lower bounds for line length minimization. Omega, 2020, 95, 102063. doi: 10.1016/j.omega.2019.04.006
24	FATTAHI P, ROSHANI A, ROSHANI A A mathematical model and ant colony algorithm for multi-manned assembly line balancing problem. The International Journal of Advanced Manufacturing Technology, 2010, 53 (1−4): 363- 378. doi: 10.1007/s00170-010-2832-y
25	ROSHANI A, ROSHANI A, ROSHANI A, et al A simulated annealing algorithm for multi-manned assembly line balancing problem. Journal of Manufacturing Systems, 2013, 32 (1): 238- 247. doi: 10.1016/j.jmsy.2012.11.003
26	KELLEGOZ T Assembly line balancing problems with multi-manned stations: a new mathematical formulation and Gantt based heuristic method. Annals of Operations Research, 2016, 253 (1): 377- 404. doi: 10.1007/s10479-016-2156-x
27	CHEN Y Y A hybrid algorithm for allocating tasks, operators, and workstations in multi-manned assembly lines. Journal of Manufacturing Systems, 2017, 42, 196- 209. doi: 10.1016/j.jmsy.2016.12.011
28	SAHIN M, KELLEGOZ T A new mixed-integer linear programming formulation and particle swarm optimization based hybrid heuristic for the problem of resource investment and balancing of the assembly line with multi-manned workstations. Computers & Industrial Engineering, 2019, 133, 107- 120.
29	JANARDHANAN M N, LI Z X, BOCEWICZ G, et al Metaheuristic algorithms for balancing robotic assembly lines with sequence-dependent robot setup times. Applied Mathematical Modelling, 2019, 65, 256- 270. doi: 10.1016/j.apm.2018.08.016
30	ZHANG Z K, TANG Q H, HAN D Y, et al Enhanced migrating birds optimization algorithm for U-shaped assembly line balancing problems with workers assignment. Neural Computing and Applications, 2018, 31 (11): 7501- 7515. doi: 10.1007/s00521-018-3596-9
31	SIOUD A, GAGNE C Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times. European Journal of Operational Research, 2018, 264 (1): 66- 73. doi: 10.1016/j.ejor.2017.06.027
32	ZHANG B, PAN Q K, GAO L, et al An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming. Applied Soft Computing, 2017, 52, 14- 27. doi: 10.1016/j.asoc.2016.12.021
33	OTTO A, OTTO C, SCHOLL A Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing. European Journal of Operational Research, 2013, 228 (1): 33- 45. doi: 10.1016/j.ejor.2012.12.029
34	QIAN X W, FAN Q F. Solving multi-manned assembly line balancing problem by a heuristic-mixed genetic algorithm. Proc. of the International Conference on Information Management, Innovation Management and Industrial Engineering, 2011: 320−323.

Notation	Description
i, h	Index of task
j	Index of workstation
k	Index of operator
I	Set of all the tasks
J	Set of all the workstations
K	Set of all the operators in each workstation
P⁰	Set of tasks that have no immediate predecessors
P(i)	Set of immediate predecessors of task i
n	The total number of tasks
u_max	The admitted maximum number of operators in each workstation
CT	Cycle time
M	A very large positive number
t_i	The processing time of task i
W_ih	Binary variable. 1: if tasks i and h are assigned to the same operator and task iis performed immediately before task h; 0: otherwise.
X_ijk	Binary variable. 1: if task i is operated by operator k at workstation j; 0: otherwise.
Y_jk	Binary variable. 1: if operator k is employed in workstation j; 0: otherwise.
Z_j	Binary variable. 1: if workstation j is opened; 0: otherwise.
FT_i	Continuous variable. The finishing time of task i.

Algorithm	Parameter	Range	Selected value
EMBO/EMBO1/ MBO_CPT/ MBO_ACT	α	9, 11, 13	9
	β	5, 6, 7	7
	χ	2, 3, 4	4
	γ	50, 100, 150	150
	T	0.4, 0.5, 0.6	0.6
EMBO2	α	9, 11, 13	13
	β	5, 6, 7	7
	χ	2, 3, 4	4
	γ	50, 100, 150	100
	T	0.4, 0.5, 0.6	0.5
HGA	Population size	30, 40, 50	30
	Crossover rate	Crossover on all the solutions	1.0
	Mutation rate SA1/SA2	Mutation on all the solutions	1.0
	The initial temperature	100, 1000, 10 000	10 000
	Cooling rate	0.85, 0.90, 0.97	0.90
	Number of iterations for each temperature level	100, 150, 200	200
GanttSA/SA3	Press based insert move tabu length	3, 4, 5	4
	Probability of selecting move type	0.3, 0.4, 0.5	0.5
	Cooling rate	0.85, 0.90, 0.97	0.97
	Number of iterations for each temperature level	100, 150, 200	100

Algorithm	p=10		p=20
Algorithm	Minimum	Average	Minimum	Average
HGA	0.53	1.03	0.07	0.46
GanttSA	6.27	15.08	3.45	10.60
SA1	0.02	0.45	0.01	0.18
SA2	10.91	12.29	8.13	9.43
EMBO	0.00	0.29	0.00	0.15

Algorithm	p=10		p=20
Algorithm	Minimum	Average	Minimum	Average
HGA	0.97	2.16	0.36	1.10
GanttSA	3.97	9.59	2.60	6.01
SA1	0.83	1.47	0.54	0.92
SA2	5.37	7.90	2.69	4.41
EMBO	0.27	0.94	0.09	0.61

Algorithm	p=10		p=20
Algorithm	Minimum	Average	Minimum	Average
HGA	1.63	3.04	0.02	0.03
GanttSA	3.87	8.39	0.03	0.08
SA1	1.10	1.50	0.01	0.01
SA2	27.95	31.49	0.06	0.07
EMBO	0.05	0.31	0.00	0.01

An efficient migrating birds optimization algorithm with idle time reduction for Type-I multi-manned assembly line balancing problem

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 12

References 34

Related Articles 0

Recommended Articles

Metrics

Comments