A multi-pass heuristic for multi-skilled worker scheduling in aircraft final assembly line with variable duration

doi:10.23919/JSEE.2025.000120

Journal of Systems Engineering and Electronics ›› 2025, Vol. 36 ›› Issue (6): 1532-1547.doi: 10.23919/JSEE.2025.000120

• SYSTEMS ENGINEERING • Previous Articles

A multi-pass heuristic for multi-skilled worker scheduling in aircraft final assembly line with variable duration

Meng LIU¹(), Linman LI¹(), Xinyi LIU²(), Ershun PAN¹^,*()

¹ School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
² Shanghai Aircraft Manufacturing Company, Ltd., Shanghai 201324, China

Received:2025-05-05 Accepted:2025-07-30 Online:2025-12-18 Published:2026-01-07
Contact: Ershun PAN E-mail:liumeng2022@sjtu.edu.cn;foreverivy@sjtu.edu.cn;liuxinyi@comac.intra;pes@sjtu.edu.cn
About author:
LIU Meng was born in 2000. She received her B.S. degree in industrial engineering from Northeast Forestry University, Harbin, China, in 2022. She is currently pursuing her M.S. degree in industrial engineering with the Department of Industrial Engineering and Management, Shanghai Jiao Tong University, Shanghai. China. Her research interests include operation research, production and operations management, and aircraft final assembly scheduling. E-mail: liumeng2022@sjtu.edu.cn

LI Linman was born in 1997. She received her B.S. and M.S. degrees in industrial engineering and management from Shanghai Jiao Tong University, Shanghai, China, where she is pursuing her Ph.D. degree in industrial engineering and management. Her research interests are port operations optimization and optimization modeling and algorithm. E-mail: foreverivy@sjtu.edu.cn

LIU Xinyi was born in 1992. She received her B.S. and M.S. degrees in industrial engineering from Tongji University, Shanghai, China, in 2015 and 2018 respectively. She is an industrial engineering engineer at Shanghai Aircraft Manufacturing Co., Ltd. Her research interests include project scheduling and lean improvement. E-mail: liuxinyi@comac.intra

PAN Ershun was born in 1972. He received his B.S. and M.S. degrees in mechanical design and manufacturing from Northeastern University, Shenyang, China, in 1997, and Ph.D. degree in mechanical engineering from Shanghai Jiao Tong University, Shanghai, China, in 2000. He is currently a professor and the Head of the Department of Industrial Engineering and Management, Shanghai Jiao Tong University. His current research interests include quality control, production system planning and design, and lean manufacturing technology. E-mail: pes@sjtu.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (52175475).

Abstract

Abstract:

In an aircraft final assembly line (AFAL), the rational scheduling of assembly workers to complete tasks in an orderly manner is crucial for enhancing production efficiency. This paper addresses the multi-skilled worker scheduling problem in the AFAL, where the processing time of each task varies due to the assigned workers’ skill levels, referred to as variable duration. The objective is to minimize the makespan, i.e., the total time required for all workers to complete all tasks. A mixed integer linear programming model is formulated under complex constraints including assembly precedence relations, skill requirements, worker skill capabilities, and workspace capacities. To solve the model effectively, a multi-pass priority rule-based heuristic (MPRH) algorithm is proposed. This algorithm integrates 14 activity priority rules and nine worker priority rules with worker weights. Extensive experiments iteratively the best-performing priority rules, and the most effective rule subsets are integrated through a lightweight multi-pass mechanism to enhance its efficiency. The computational results demonstrate that the MPRH can find high-quality solutions effectively within very short central processing unit central processing unit (CPU) time compared to GUROBI. A case study based on real data obtained from an AFAL confirms the necessity and the feasibility of the approach in practical applications. Sensitivity analyses provide valuable insights to real production scenarios.

Key words: aircraft final assembly line, multi-skilled worker scheduling, variable duration, multi-pass heuristic

Meng LIU, Linman LI, Xinyi LIU, Ershun PAN. A multi-pass heuristic for multi-skilled worker scheduling in aircraft final assembly line with variable duration[J]. Journal of Systems Engineering and Electronics, 2025, 36(6): 1532-1547.

Figures/Tables 13

Fig 1

Table 1

Fig 2

Table 2

Table 3

Table 4

Fig 3

Fig 4

Table 5

Fig 5

Fig 6

Fig 7

Table 6

References 34

1	MEI Z Y, MAROPOULOS P G Review of the application of flexible, measurement-assisted assembly technology in aircraft manufacturing. Journal of Engineering Manufacture, 2014, 228 (10): 1185- 1197. doi: 10.1177/0954405413517387
2	LU Z Q, ZHU H M, HAN X, et al Integrated modelling and algorithm of material delivery and line-side storage for aircraft moving assembly lines. International Journal of Production Research, 2019, 57 (18): 5842- 5856. doi: 10.1080/00207543.2018.1554917
3	BAO Z K, CHEN L, QIU K J An aircraft final assembly line balancing problem considering resource constraints and parallel task scheduling. Computers & Industrial Engineering, 2023, 182, 109436.
4	FANG P C, YANG J J, LIAO Q M, et al Flexible worker allocation in aircraft final assembly line using multiobjective evolutionary algorithms. IEEE Trans. on Industrial Informatics, 2021, 17 (11): 7468- 7478. doi: 10.1109/TII.2021.3051896
5	ARKHIPOV D, BATTAIA O, CEGARRA J, et al Operator assignment problem in aircraft assembly lines: a new planning approach taking into account economic and ergonomic constraints. Procedia CIRP, 2018, 76, 63- 66. doi: 10.1016/j.procir.2018.01.020
6	HARTMANN S, BRISKORN D An updated survey of variants and extensions of the resource-constrained project scheduling problem. European Journal of Operational Research, 2022, 297 (1): 1- 14. doi: 10.1016/j.ejor.2021.05.004
7	SHAN S Q, HU Z J, LIU Z L, et al An adaptive genetic algorithm for demand-driven and resource-constrained project scheduling in aircraft assembly. Information Technology and Management, 2017, 18 (1): 41- 53. doi: 10.1007/s10799-015-0223-7
8	CAI H, SU Y, SHEN T. Research on intelligent schedule of aircraft assembly workshop. Proc. of the 12th International Conference on Intelligent Human-Machine Systems and Cybernetics, 2020. DOI: 10.1109/IHMSC49165.2020.10091.
9	REN Y F, LU Z Q, LIU X Y A branch-and-bound embedded genetic algorithm for resource-constrained project scheduling problem with resource transfer time of aircraft moving assembly line. Optimization Letters, 2020, 14 (8): 2161- 2195. doi: 10.1007/s11590-020-01542-x
10	LOVATO D, GUILLAUME R, THIERRY C, et al Managing disruptions in aircraft assembly lines with staircase criteria. International Journal of Production Research, 2023, 61 (2): 632- 648. doi: 10.1080/00207543.2021.2011982
11	REN Y F, LU Z Q A flexible resource investment problem based on project splitting for aircraft moving assembly line. Assembly Automation, 2019, 39 (4): 532- 547. doi: 10.1108/AA-09-2018-0126
12	AFSHAR-NADJAFI B Multi-skilling in scheduling problems: a review on models, methods and applications. Computers & Industrial Engineering, 2021, 151, 107004.
13	LI Y Y, LIN J, WANG Z J Multi-skill resource constrained project scheduling using a multi-objective discrete jaya algorithm. Applied Intelligence, 2022, 52 (5): 5718- 5738. doi: 10.1007/s10489-021-02608-8
14	CHEN R, LIANG C Y, GU D X, et al A competence-time-quality scheduling model of multi-skilled staff for IT project portfolio. Computers & Industrial Engineering, 2020, 139, 106183.
15	LIU S S, WANG C J Optimizing linear project scheduling with multi-skilled crews. Automation in Construction, 2012, 24, 16- 23. doi: 10.1016/j.autcon.2011.12.009
16	NASIRIAN A, ARASHPOUR M, ABBASI B, et al Optimal work assignment to multiskilled resources in prefabricated construction. Journal of Construction Engineering and Management, 2019, 145 (4): 04019011. doi: 10.1061/(ASCE)CO.1943-7862.0001627
17	ZAREI F, ARASHPOUR M, MIRNEZAMI S A, et al Multi-skill resource-constrained project scheduling problem considering overlapping: fuzzy multi-objective programming approach to a case study. International Journal of Construction Management, 2024, 24 (8): 820- 833. doi: 10.1080/15623599.2023.2260696
18	BELLENGUEZ O, NERON E. Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills. BURKE E, TRICK M, ed. Practice and theory of automated timetabling V. Berlin: Springer, 2005.
19	VALLS V, PEREZ A, QUINTANILLA S Skilled workforce scheduling in service centres. European Journal of Operational Research, 2009, 193 (3): 791- 804. doi: 10.1016/j.ejor.2007.11.008
20	SNAUWAERT J, VANHOUCKE M Mathematical formulations for project scheduling problems with categorical and hierarchical skills. Computers & Industrial Engineering, 2022, 169, 108147.
21	CHAND S, SINGH H, RAY T Evolving heuristics for the resource constrained project scheduling problem with dynamic resource disruptions. Swarm and Evolutionary Computation, 2019, 44, 897- 912. doi: 10.1016/j.swevo.2018.09.007
22	DING H Y, ZHUANG C B, LIU J H Extensions of the resource-constrained project scheduling problem. Automation in Construction, 2023, 153, 104958. doi: 10.1016/j.autcon.2023.104958
23	LIN J, ZHU L, GAO K Z A genetic programming hyper-heuristic approach for the multi-skill resource constrained project scheduling problem. Expert Systems with Applications, 2020, 140, 112915. doi: 10.1016/j.eswa.2019.112915
24	CHAKRABORTTY R K, RAHMAN H F, RYAN M J Efficient priority rules for project scheduling under dynamic environments: a heuristic approach. Computers & Industrial Engineering, 2020, 140, 106287.
25	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
26	TURKAKIN O H, ARDITI D, MANISALI E Comparison of heuristic priority rules in the solution of the resource-constrained project scheduling problem. Sustainability, 2021, 13 (17): 1- 17.
27	ALMEIDA B F, CORREIA I, SALDANHA-DA-GAMA F Priority-based heuristics for the multi-skill resource constrained project scheduling problem. Expert Systems with Applications, 2016, 57, 91- 103. doi: 10.1016/j.eswa.2016.03.017
28	ZHENG Q, XI L Heuristics for aircraft moving assembly line scheduling problem. Industrial Engineering and Management, 2015, 20 (2): 116- 121.
29	WILLIS R J Critical path analysis and resource constrained project scheduling-theory and practice. European Journal of Operational Research, 1985, 21 (2): 149- 155. doi: 10.1016/0377-2217(85)90026-8
30	ZAREEI S Project scheduling for constructing biogas plant using critical path method. Renewable and Sustainable Energy Reviews, 2018, 81, 756- 759. doi: 10.1016/j.rser.2017.08.025
31	SNAUWAERT J, VANHOUCKE M A new algorithm for resource-constrained project scheduling with breadth and depth of skills. European Journal of Operational Research, 2021, 292 (1): 43- 59. doi: 10.1016/j.ejor.2020.10.032
32	BELLENGUEZ O, NERON E A branch-and-bound method for solving multi-skill project scheduling problem. Operations Research, 2007, 41, 155- 170. doi: 10.1051/ro:2007015
33	SNAUWAERT J, VANHOUCKE M A classification and new benchmark instances for the multi-skilled resource-constrained project scheduling problem. European Journal of Operational Research, 2023, 307 (1): 1- 19. doi: 10.1016/j.ejor.2022.05.049
34	LIU M. MSPVD_AFAL data and results. https://github.com/liumeng2022/MSPVD_AFAL.

Variable	Description
${x_{jd}}$	Binary variable: 1, if activity $j$ is executed in period $[d,d + 1)$; 0, otherwise
${y_{ij}}$	Binary variable: 1, if activity $i$ is finished before activity $j$ starts; 0, otherwise
${z_{jsk}}$	Binary variable: 1, if worker $k$ is assigned to skill $s$ of activity $j$; 0, otherwise
${s_j}$	Non-negative integer variable: start time of activity $j$
${f_j}$	Non-negative integer variable: finish time of activity $j$

APR	Function	Formula
SPT	Min	${p_j}$
LPT	Min	${p_j}$
EST	Min	${{\mathrm{ES}}_j}$
EFT	Min	$ {{\mathrm{EF}}}_{j}={{\mathrm{ES}}}_{j}+ {p}_{j} $
LFT	Min	${{\mathrm{LF}}_j}$
LST	Min	${{\mathrm{LS}}_j} = {{\mathrm{LF}}_j} - {p_j}$
SLK	Min	${{\mathrm{LS}}_j} - {{\mathrm{ES}}_j}$
MIS	Max	$\|{W_j}\|$
MTS	Max	$\|W_j^*\|$
GRPW	Max	$ {p_j} + \displaystyle\sum\limits_{i \in {W_j}} {{p_i}} $
GRPW^*	Max	$ {p_j} + \displaystyle\sum\limits_{i \in W_j^*} {{p_i}} $
WRS	Min	${\sigma _j}$
SRS	Min	${\varphi _j}$
RR	Rand	−

WPR	Function	$\omega _k^g$
HBF	Max	$\|{S_k}\|$
LBF	Min	$\|{S_k}\|$
HDF	Max	${h_{{s^}k}}$, ${s^} = \left\{ s\|{r_{js}} = 1,s \in S\right\} $
LDF	Min	${h_{{s^}k}}$, ${s^} = \left\{ s\|{r_{js}} = 1,s \in S\right\} $
HSCF	Max	$ \|{S_k}\| \cdot \mathop {\max }\limits_{s \in {S_k}} \left\{ \displaystyle\sum\limits_{j \in {J_s}} {{p_j} \cdot {a_j}} /\|{K_s}\|\right\} $
LSCF	Min	$ \|{S_k}\| \cdot \mathop {\max }\limits_{s \in {S_k}} \left\{ \displaystyle\sum\limits_{j \in {J_s}} {{p_j} \cdot {a_j}} /\|{K_s}\|\right\} $
HDCF	Max	$ \|{S_k}\| \cdot \mathop {\max }\limits_{s \in {S_k}} \left\{ \displaystyle\sum\limits_{j \in U_s^g} {{p_j} \cdot {a_j}} /\|{K_s}\|\right\} $
LDCF	Min	$ \|{S_k}\| \cdot \mathop {\max }\limits_{s \in {S_k}} \left\{ \displaystyle\sum\limits_{j \in U_s^g} {{p_j} \cdot {a_j}} /\|{K_s}\|\right\} $
RR	Rand	$0$

Parameter	Instance information
Number of activities	Values in {30, 60, 90}; 625 instances per value
SP	Values in {0.1, 0.3, 0.5, 0.7, 0.9}; 375 instances per value
SS	Values in {0.1, 0.3, 0.5, 0.7, 0.9}; 375 instances per value
Number of workspaces	Values in {4, 8, 12}, matched to the three activity-number scales

Matrics		GUROBI			MPRH
Matrics		OPT/%	FNO/%	CPU/s	Gap/%	CPU/s
Scale	30	95.20	4.80	264.8	5.84	0.044
	60	89.60	7.20	731.0	2.58	0.129
	90	76.80	4.00	1179.0	−1.37	0.288
SP	0.1	58.67	18.67	1695.0	6.78	0.249
	0.3	86.67	2.67	659.6	4.58	0.147
	0.5	92.00	5.33	587.5	−2.06	0.132
	0.7	98.67	0.00	304.4	0.48	0.127
	0.9	100.00	0.00	335.5	0.03	0.116
SS	0.1	65.33	16.00	1656.4	1.23	0.112
	0.3	86.67	4.00	774.8	3.32	0.138
	0.5	93.33	2.67	479.1	1.51	0.156
	0.7	94.67	0.00	311.5	2.56	0.178
	0.9	96.00	4.00	360.1	0.59	0.186
Overall		87.20	5.33	718.36	2.01	0.154

A multi-pass heuristic for multi-skilled worker scheduling in aircraft final assembly line with variable duration

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 13

References 34

Related Articles 0

Recommended Articles

Metrics

Comments

Approach	CPU Time/s	Makespan/h	Gap/%
MPRH	0.131	53.0	−
TS	34.05	56.2	6.04
GA	61.69	53.4	0.75