Reentrant flexible job-shop scheduling problem with assembly constraints in the context of wafer manufacturing: an improved MOEA/D with objective-oriented search

doi:10.23919/JSEE.2026.000144

Abstract

Abstract:

The semiconductor chip industry has become a bottleneck in China’s industrial development. How to improve efficiency has attracted increasing attention. Effective and efficient scheduling decision is the key to improve production efficiency. Oriented towards the wafer manufacturing of micro-electro-mechanical system (MEMS), a reentrant flexible job-shop scheduling problem with assembly constraints (RFJSSP-AC) is modeled to minimize the makespan and the total energy consumption simultaneously. An improved multi-objective evolutionary algorithm based on decomposition (IMOEA/D) is developed to solve the problem. The proposed IMOEA/D incorporates three key innovations: a hybrid initialization strategy combining heuristic rules with random generation to produce high-quality initial populations; an objective- oriented search strategy for targeted solution optimization; and an energy consumption inverse optimization mechanism for further energy efficiency improvement. Comprehensive comparative experiments demonstrate the effectiveness of the proposed algorithmic components and the exceptional performance for the RFJSSP-AC problem.

Key words: assembly constraints, flexible job-shop scheduling, multi-objective evolutionary algorithm based on decomposition, objective-oriented search, reentrant characteristic

Xiuli Wu, Yaqi Zhang. Reentrant flexible job-shop scheduling problem with assembly constraints in the context of wafer manufacturing: an improved MOEA/D with objective-oriented search[J]. Journal of Systems Engineering and Electronics, 2026, 37(5): 1665-1690.

Figures/Tables 39

Fig 1

Fig 2

Table 1

Table 2

Fig 3

Table 3

Notations"

Type of notations	Symbol	Definition
Index	i	Job index, i∈{1, 2, ···, I}
	h, g	VC index, h, g∈{1, 2, 3, ···, H}
	l, v	Operation index in the VC, l, v∈{1, 2, ···, L_h}
	j	Workstation index, j∈{1, 2, ···, J}
	k	Machine index in the workstation, k∈{1, 2, ···, K_j}
	o	Position index on the machine, o∈{1, 2, ···, Q}
Parameters	I	Number of the jobs
	J	Number of the workstations
	H	Number of the VCs
	Q	Number of positions of all machines
	K_j	Number of machines in the jth workstation
	L_h	Number of the operations of the VC_h
	M_jk	The kth machine in the jth workstation
	O_hl	The lth operation index of the VC_h
	D_hl	Workstation index for handling the O_hl
	P_hlk/h	Processing time of the lth operation of the kth machine of VC_h
	F_jk/(kW/h)	Idle energy consumption per hour of the M_jk
	G_hlk/(kW/h)	Processing energy consumption per hour of the O_hl on the kth machine
	MM	A value of positive infinity
Variable	S_hl/h	Start time of the lth operation of VC_h
	C_hl/h	End time of the lth operation of VC_h
	Q_jk	Number of operations processed on M_jk
	V_jko	VC index processed on the oth position on M_jk
	W_jko	Operation index processed on the oth position on M_jk
	MI_hl	Index of processing machine of the lth operation of VC_h
	KS_jko/h	Start time of the oth operation on M_jk
	KE_jko/h	End time of the oth operation on M_jk
	MS_jk/h	Turn-on time of M_jk
	ME_jk/h	Turn-off time of M_jk
	MP_jk/h	Occupying time of M_jk
	Cmax	Makespan of a scheduling solution
	TEC/(kW/h)	Total energy consumption of a scheduling solution
	EI/(kW/h)	Total idle energy consumption of a scheduling solution
	EP/(kW/h)	Total processing energy consumption of a scheduling solution
	X_hlk	A binary variable is set to 1 if O_hl is processed on the kth machine; 0, otherwise
	Y_hlgv	A binary variable is set to 1 if operation O_hl is processed after O_gv on one machine; 0, otherwise
	A_hg	A binary variable is set to 1 if the VC_g is the successor of the VC_h; 0, otherwise
	B_hlv	A binary variable is set to 1 if the lth operation is the successor of the vth operation; 0, otherwise

Table 3

Fig 4

Fig 5

Table 4

Fig 6

Fig 7

Fig 8

Table 5

Table 6

Table 7

Table 8

Fig 9

Fig 10

Table 9

Table 10

Table 11

Table 12

Table 13

Fig 11

Table 14

Fig 12

Table 15

Pareto solutions obtained by the IMOEA/D, the IMOEA/D_6, and the IMOEA/D_4 during iterations"

Iteration	IMOEA/D	IMOEA/D_6	IMOEA/D_4
0th	[237, 57370], [263, 47702], [238, 57034], [235, 57600]	[237, 57370], [263, 47702], [238, 57034], [235, 57600]	[237, 57370], [263, 47702], [238, 57034], [235, 57600]
10th	[224, 53614], [234, 50830], [233, 51123], [235, 50475], [250, 46742], [221, 54549]	[263, 47702], [255, 48400], [260, 48220], [229, 51612], [259, 48252], [227, 52379], [226, 52902], [249, 51052], [253, 49841]	[263, 47702], [261, 47720], [230, 56429], [237, 54967], [260, 50831]
20th	[221, 53245], [229, 48643], [245, 46848], [246, 46821], [228, 49624], [231, 48456], [244, 46908], [247, 46118], [224, 52619]	[259, 47522], [249, 49474], [227, 52302], [226, 52801], [236, 51424], [255, 48122], [229, 51430], [253, 49009]	[263, 47702], [261, 47720], [230, 56429], [237, 54967], [258, 50796], [247, 54174], [250, 53723],[257, 52849]
30th	[221, 53245], [247, 46118], [231, 47838], [243, 46486], [240, 46683], [223, 48803], [227, 48693], [228, 48225]	[259, 47522], [226, 52801], [227, 52278], [249, 49310], [229, 51161], [255, 47961], [236, 51099], [253, 48985]	[230, 56429],[237, 54967], [258, 50796], [247, 54174], [250, 53723], [257, 52849], [261, 47624]
40th	[221, 53245], [247, 46090], [230, 47661], [224, 48458], [240, 46452], [223, 48585], [226, 47791], [243, 46350], [225, 47866], [237, 47515], [239, 46477], [246, 46148]	[259, 47522], [249, 49310], [229, 51161], [255, 47961], [236, 51099], [227, 52128], [226, 52651],[250, 49280], [252, 48776], [243, 50320],[224, 54271], [248, 49725]	[230, 56429], [237, 54967], [258, 50796], [247, 54174], [250, 53723], [257, 52849], [261, 47624]
50th	[230, 47661], [243, 45766], [223, 48532], [219, 52759], [240, 46260], [242, 46174], [225, 47823], [226, 47777], [235, 47110], [222, 51232], [224, 48213], [236, 46477], [238, 46273]	[227, 52128], [226, 52651],[224, 53827], [228, 50335], [259, 47511], [235, 50297], [239, 49963], [245, 48913], [255, 47840], [252, 48620]	[230, 56429], [237, 54967], [258, 50796], [247, 54174], [250, 53723], [257, 52849], [261, 47624]

Table 15

Fig 13

Fig 14

Table 16

Table 17

Fig 15

Fig 16

Table 18

Table 19

Table 20

Table 21

Fig 17

Fig 18

References 43

1	Lin D P, Lee C K M A review of the research methodology for the re-entrant scheduling problem. International Journal of Production Research, 2011, 49 (6-8): 2221. doi: 10.1080/00207541003720350
2	Dong J, Ye C M Research on collaborative optimization of green manufacturing in semiconductor wafer distributed heterogeneous factory. Applied Sciences, 2019, 9 (14): 2879. doi: 10.3390/app9142879
3	Tay F E H, Lee L H, Wang L X Production scheduling of a MEMS manufacturing system with a wafer bonding process. Journal of Manufacturing Systems, 2002, 21 (4): 287. doi: 10.1016/S0278-6125(02)80168-6
4	Wang J, Tang H T, Lei D M A Q-learning artificial bee colony for distributed assembly flow shop scheduling with factory eligibility, transportation capacity and setup time. Engineering Applications of Artificial Intelligence: The International Journal of Intelligent Real-Time Automation, 2023, 123 (A): 106230.
5	Zhang Z Q, Hu R, Qian B, et al A matrix cube-based estimation of distribution algorithm for the energy-efficient distributed assembly permutation flow-shop scheduling problem. Expert Systems with Applications, 2022, 194, 116484. doi: 10.1016/j.eswa.2021.116484
6	Zhang Z K, Tang Q H Integrating flexible preventive maintenance activities into two-stage assembly flow shop scheduling with multiple assembly machines. Computers & Industrial Engineering, 2021, 159 (2): 107493. doi: 10.1016/j.cie.2021.107493
7	Zhao F Q, Di S L, Wang L, et al A self-learning hyper-heuristic for the distributed assembly blocking flow shop scheduling problem with total flowtime criterion. Engineering Applications of Artificial Intelligence: The International Journal of Intelligent Real-Time Automation, 2022, 116, 105418.
8	Birgin E G, Ferreira J E, Ronconi D P List scheduling and beam search methods for the flexible job shop scheduling problem with sequencing flexibility. European Journal of Operational Research, 2015, 247 (2): 421. doi: 10.1016/j.ejor.2015.06.023
9	Guo W F, Lei Q, Song Y C, et al A learning interactive genetic algorithm based on edge selection encoding for assembly job shop scheduling problem. Computers & Industrial Engineering, 2021, 159, 107455. doi: 10.1016/j.cie.2021.107455
10	Lin W H, Deng Q W, Han W W, et al An effective algorithm for flexible assembly job-shop scheduling with tight job constraints. International Transactions in Operational Research, 2020, 1 (29): 496. doi: 10.1111/itor.12767
11	Lunardi W T, Birgin E G, Ronconi D P, et al Metaheuristics for the online printing shop scheduling problem. European Journal of Operational Research, 2021, 293 (2): 419. doi: 10.1016/j.ejor.2020.12.021
12	Shi F, Zhao S K, Meng Y Hybrid algorithm based on improved extended shifting bottleneck procedure and GA for assembly job shop scheduling problem. International Journal of Production Research, 2020, 58 (9): 2604. doi: 10.1080/00207543.2019.1622052
13	Gonzalez T, Sahni S Flowshop and jobshop schedules: complexity and approximation. Operations Research, 1978, 26 (1): 36. doi: 10.1287/opre.26.1.36
14	Rifai A P, Mara S T W, Sudiasso A Multi-objective distributed reentrant permutation flow shop scheduling with sequence-dependent setup time. Expert Systems with Applications, 2021, 183, 115339. doi: 10.1016/j.eswa.2021.115339
15	Rifai A P, Nguyen H T, Aoyama H, et al Non-dominated sorting biogeography-based optimization for bi-objective reentrant flexible manufacturing system scheduling. Applied Soft Computing, 2018, 62, 187. doi: 10.1016/j.asoc.2017.10.045
16	Dong J, Ye C M Green scheduling of distributed two-stage reentrant hybrid flow shop considering distributed energy resources and energy storage system. Computers & Industrial Engineering, 2022, 169, 108146. doi: 10.1016/j.cie.2022.108146
17	Wu X L, Xie Z R Improved MOEA/D with local search for solving multi-stage distributed reentrant hybrid flow shop scheduling problem. Expert Systems with Applications, 2023, 232, 120893. doi: 10.1016/j.eswa.2023.120893
18	Wu X L, Cao Z An improved multi-objective evolutionary algorithm based on decomposition for solving re-entrant hybrid flow shop scheduling problem with batch processing machines. Computers & Industrial Engineering, 2022, 169, 108236. doi: 10.1016/j.cie.2022.108236
19	Lin C C, Liu W Y, Chen Y H Considering stockers in reentrant hybrid flow shop scheduling with limited buffer capacity. Computers & Industrial Engineering, 2020, 139, 106154. doi: 10.1016/j.cie.2019.106154
20	Li M, Wang G G A review of green shop scheduling problem. Information Sciences, 2022, 589, 478. doi: 10.1016/j.ins.2021.12.122
21	Wu X L, Yan X Y, Wang L Optimizing job release and scheduling jointly in a reentrant hybrid flow shop. Expert Systems with Applications, 2022, 209, 118278. doi: 10.1016/j.eswa.2022.118278
22	Geng K F, Ye C M, Dai Z H, et al. Bi-objective re-entrant hybrid flow shop scheduling considering energy consumption cost under time-of-use electricity tariffs[J]. Complexity, 2020, 8565921.
23	Wu X L, Zhang Y Q, Zhao K H. An improved NSGA-II for solving reentrant flexible assembly job shop scheduling problem[C]// 14th International Conference on Swarm Intelligence, 2023: 242.
24	Trivedi A, Srinivasan D, Sanyal K, et al A survey of multiobjective evolutionary algorithms based on decomposition. IEEE Trans. on Evolutionary Computation, 2017, 21 (3): 440.
25	Jiang E D, Wang L, Wang J J Decomposition-based multi-objective optimization for energy-aware distributed hybrid flow shop scheduling with multiprocessor tasks. Tsinghua Science and Technology, 2021, 26 (5): 646.
26	Luo C, Gong W Y, Li R, et al Problem-specific knowledge MOEA/D for energy-efficient scheduling of distributed permutation flow shop in heterogeneous factories. Engineering Applications of Artificial Intelligence, 2023, 123, 106454. doi: 10.1016/j.engappai.2023.106454
27	Shao W S, Shao Z S, Pi D C An ant colony optimization behavior-based MOEA/D for distributed heterogeneous hybrid flow shop scheduling problem under nonidentical time-of-use electricity tariffs. IEEE Trans. on Automation Science and Engineering, 2022, 19 (4): 3379. doi: 10.1109/TASE.2021.3119353
28	Yan X Y, Wu X L IMOEA/D to optimize job release problem for a reentrant hybrid flow shop. Computers & Industrial Engineering, 2022, 163, 107800. doi: 10.1016/j.cie.2021.107800
29	Zhao S K, Han Q, Wang G C Product comprehensive scheduling algorithm based on virtual component level division coding. Computer Integrated Manufacturing Systems, 2015, 21, 2435.
30	Li Y J. Research on lot splitting and scheduling method of multi-level assembly job shop based on genetic algorithm[D]. Guangzhou: Guangdong University of Technology, 2020. (in Chinese)
31	Qi Y T, Hou Z T, Li H, et al A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows. Computers & Operations Research, 2015, 62, 61. doi: 10.1016/j.cor.2015.04.009
32	Yang M H, Gan Y, Gao L, et al A structural optimization model of a biochemical detection micromixer based on RSM and MOEA/D. Chemical Engineering and Processing - Process Intensification, 2022, 173, 108832. doi: 10.1016/j.cep.2022.108832
33	Galeano-Brajones J, Luna-Valero F, Carmona-Murillo J, et al Designing problem-specific operators for solving the cell switch-off problem in ultra-dense 5G networks with hybrid MOEAs. Swarm and Evolutionary Computation, 2023, 78, 101290. doi: 10.1016/j.swevo.2023.101290
34	Wang L, Wang J J, Jiang E D Decomposition based multiobjective evolutionary algorithm with adaptive resource allocation for energy-aware welding shop scheduling problem. Computers & Industrial Engineering, 2021, 162, 107778. doi: 10.1016/j.cie.2021.107778
35	Ding J Y, Song S J, Wu C Carbon-efficient scheduling of flow shops by multi-objective optimization. European Journal of Operational Research, 2016, 248 (3): 758. doi: 10.1016/j.ejor.2015.05.019
36	Wang Z K, Zhang Q F, Gong M G, et al. A replacement strategy for balancing convergence and diversity in MOEA/D[C]// 2014 IEEE Congress on Evolutionary Computation, 2014: 2132.
37	Fry T D, Oliff M D, Minor E D, et al The effects of product structure and sequencing rule on assembly shop performance. International Journal of Production Research, 1989, 27 (4): 671. doi: 10.1080/00207548908942575
38	Auger A, Bader J, Brockhoff D, et al. Theory of the hypervolume indicator: optimal μ-distributions and the choice of the reference point[C]// 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, 2009: 87.
39	Van Velduizen D A, Lamont G B. Evolutionary computation and convergence to a Pareto front[R]. Stanford: Stanford University California, 1998.
40	Bosman P A N, Thierens D The balance between proximity and diversity in multiobjective evolutionary algorithms. IEEE Trans. on Evolutionary Computation, 2003, 7 (2): 174. doi: 10.1109/TEVC.2003.810761
41	Lou H Y, Wang X P, Dong Z M, et al Memetic algorithm based on learning and decomposition for multiobjective flexible job shop scheduling considering human factors. Swarm and Evolutionary Computation, 2022, 75, 101204. doi: 10.1016/j.swevo.2022.101204
42	Wang Y, Jia Z H, Zhang X Y A hybrid meta-heuristic for the flexible flow shop scheduling with blocking. Swarm and Evolutionary Computation, 2022, 75, 101195. doi: 10.1016/j.swevo.2022.101195
43	Deb K, Jain H An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE Trans. on Evolutionary Computation, 2014, 18 (4): 577. doi: 10.1109/TEVC.2013.2281535

VCs	Operation	Workstation₁		Workstation₂	Workstation₃
VCs	Operation	M₁₁	M₁₂	M₂₁	M₃₁
VC₁	O₁₁	1, 5	1, 4	−	−
	O₁₂	−	−	1, 5	−
	O₁₃	1, 5	2, 3	−	−
VC₂	O₂₁	1, 4	1, 5	−	−
VC₂	O₂₂	−	−	1, 4	−
VC₃	O₃₁	−	−	−	2, 3
VC₃	O₃₂	1, 5	1, 6	−	−
VC₄	O₄₁	−	−	2, 2	−
VC₄	O₄₂	1, 5	2, 3	−	−
VC₅	O₅₁	−	−	−	1, 3
VC₅	O₅₂	−	−	1, 2	−

Machine	Idle energy consumption/(kw/h)
M₁₁	1
M₁₂	2
M₂₁	1
M₃₁	1

Rule	Description	Calculation equation
First come first served (FCFS)	Select a VC $ {h}^{*} $ that first reaches the buffer	$ {h}^{*}={\text{argmin}}_{h\in \boldsymbol{Q}}\left({C}_{h({{l}^{\text{'}}}-1)}\right) $
Importance ratio (IR)	Select a VC $ {h}^{*} $ that has the highest ratio of the number of remaining operations of the VC in the buffer to the maximum number of remaining operations of its associated parts	$ {h}^{*}={\text{argmax}}_{h\in \boldsymbol{Q}}\left(\frac{{NUO}_{h}}{{max}_{g\in {{[1,Z}_{h}}]}(NU{O}_{g})}\right) $
Longest remaining time first (LRTF)	Select a VC $ {h}^{*} $ that has the highest remaining processing time in the buffer	$ {h}^{*}={\text{argmin}}_{h\in \boldsymbol{Q}}\left(\displaystyle\sum\limits_{l={l}^{\text{'}}}^{{L}_{h}}\left(\frac{\displaystyle\sum\limits_{k=1}^{{K}_{{{D}_\text{hl}}}}{P}_\text{hlk})}{{K}_{{{D}_\text{hl}}}}\right)\right) $
Rule 1	Select a machine $ {k}^{*} $ with the smallest total energy consumption increment among machines with the earliest completion time	$ {\boldsymbol{k}}^{\text{'}}={\text{argmin}}_{k\in [1,{{K}_{j}}]}\left({KE}_{jk{{Q}_\text{jk}}}\right) $ $ {k}^{}={\text{argmin}}_{k\in {{\boldsymbol{k}}^{\text{'}}}}\left({F}_\text{jk}\times \left({KE}_{jk{{Q}_\text{jk}}}-{KE}_{jk({{Q}_\text{jk}}-1)}\right)+{P}_\text{hlk}{G}_\text{hlk}\right) $
Rule 2	Select a machine $ {k}^{*} $ with the earliest completion time among machines with the smallest total energy consumption increment	$ {\boldsymbol{k}}^{\text{'}}={\text{argmin}}_{k\in [1,{{K}_{j}}]}\left({F}_\text{jk}\times \left({KE}_{jk{{Q}_\text{jk}}}-{KE}_{jk({{Q}_\text{jk}}-1)}\right)+{P}_\text{hlk}{G}_\text{hlk}\right) $ $ {k}^{}={\text{argmin}}_{k\in {{\boldsymbol{k}}^{\text{'}}}}\left({KE}_{jk{{Q}_\text{jk}}}\right) $

Parameter	Small-scale instance	Large-scale instance
Range of operation amount	40-160	100-600
Number of the processing workstations NS	U[3,5]	U[3,5]
Number of the assembly workstations	1	1
Number of parallel machines in each processing workstation	U[1,2]	U[1,3]
Number of parallel machines in each assembly workstation	1	1
Number of the operations for processing	U[NS +1, max_N × NS]	U[NS +1, max_N × NS]
Number of reentries max_N	2	3
Number of the operations of the assembly	1	1
Processing time	U[1,10]	U[1,10]
Processing power of the machine per unit	U[40, 60]	U[40, 60]
Idle power of the machine per unit	U[10,30]	U[10,30]

Index of instances	Name of instances	Product structure	Problem scale	Index of configuration
1	a_s_1	a	Small	1
2	a_s_2	a	Small	2
3	a_l_1	a	Large	1
4	a_l_2	a	Large	2
5	b_s_1	b	Small	1
6	b_s_2	b	Small	2
7	b_l_1	b	Large	1
8	b_l_2	b	Large	2
9	c_s_1	c	Small	1
10	c_s_2	c	Small	2
11	c_l_1	c	Large	1
12	c_l_2	c	Large	2