A Hybrid Algorithm Based on Decomposition Strategy for DAJSP Solution

doi:10.3969/j.issn.1004-132X.2026.07.017

Abstract

Abstract:

This paper addresses the distributed assembly job-shop scheduling problem （DAJSP） by establishing a mixed-integer linear programming （MILP） model to minimize the makespan， and proposes a hybrid genetic-tabu search algorithm with a greedy strategy. The DAJSP is decomposed into two subproblems： job processing and product assembly. For the processing stage， a heuristic algorithm is applied； for the assembly stage， an efficient greedy algorithm is designed to provide a fast and effective scheduling solution. Experimental results on 40 instances show that， compared with a monolithic optimization method， the proposed decomposition strategy reduces computational time and improves solution quality， thereby validating its effectiveness and superiority.

Key words: distributed assembly job-shop scheduling, makespan, hybrid genetic-tabu search, greedy algorithm

摘要：

针对分布式装配作业车间调度问题（DAJSP），以最小化最大完工时间为目标，建立了混合整数线性规划（MILP）模型，提出了一种融合贪心策略的遗传-禁忌搜索算法（GTSAIGS）。将DAJSP分解为工件加工与产品装配的两阶段问题，在加工阶段采用启发式算法优化，针对装配阶段的调度问题设计了一种高效的贪心算法进行快速求解。40个算例的测试结果表明，相比于整体优化方法，GTSAIGS分解策略减少了计算耗时，提高了求解质量，进而验证了所提算法的有效性和优越性。

关键词: 分布式装配作业车间调度问题（DAJSP）, 最大完工时间, 混合算法, 贪心算法

CLC Number:

TP182

WU Zhengyuan, ZHAO Shikui, XIE Ruijian, YU Fengshun, LI Tong, ZHAO Lin. A Hybrid Algorithm Based on Decomposition Strategy for DAJSP Solution[J]. China Mechanical Engineering, 2026, 37(7): 1673-1685.

仵政源, 赵诗奎, 解瑞建, 于丰顺, 李彤, 赵林. 基于分解策略混合算法的DAJSP求解[J]. 中国机械工程, 2026, 37(7): 1673-1685.

Figures/Tables 19

Tab.1 DAJSP example with 3 products， 8 jobs and 2 factories

产品	工件	工序	各加工机器上的加工时间				装配用时
			工厂1		工厂2
			M₁	M₂	M₁	M₂
P₁	J₂	O_2，1		4		4	5
	J₂	O_2，2	5		5
	J₅	O_5，1	5		5
	J₅	O_5，2		6		6
	J₆	O_6，1		4		4
	J₆	O_6，2	4		4
P₂	J₁	O_1，1	6		6		4
	J₁	O_1，2		2		2
	J₃	O_3，1	3		3
	J₃	O_3，2		4		4
	J₈	O_8，1	2		2
	J₈	O_8，2		3		3
P₃	J₄	O_4，1	6		6		5
	J₄	O_4，2		3		3
	J₇	O_7，1	6		6
	J₇	O_7，2		5		5

Tab.2 Explanation of symbols

符号	意义
i，i′	工件索引， $i, i' ∈ I$
n	工件总数
I	工件索引集，I=｛1，…，n｝
j，j′	加工工序的索引， $j, j' ∈ O i$
O_i	工件i的工序索引集
O_i，j	工件i的第j道工序
f	分布式加工工厂索引， $f ∈ F$
N_f	分布式加工工厂总数
F	分布式加工工厂索引集，F=｛1，…， N_f ｝
T_i，j	工件i的第j道工序的加工时间
T_p	产品p的装配时间
p，p′	产品索引， $p, p' ∈ P$
S_p	构成产品p的工件索引集， $S p ⊆ I$
N_p	产品数量
P	产品索引集，P=｛1，…， N_p ｝
L	一个极大的正数
m	每个工厂的机器数
k_i，j	工件i的第j道工序的指定加工机器索引，k_i，j ∈｛1，2，…，m｝
X_i，f	如果工件i被分配到工厂f，则为1，否则为0
X_i，j，f	如果工件i的第j道工序被分配到工厂f，则为1，否则为0
Z_p，p’	如果产品p在产品p'之前进行装配，则为1，否则为0
S_i，j	工件i的工序j的开工时间，S_i，j ≥0
C_i	工件i的完工时间，C_i ≥0
A_p	产品p的装配开始时间，A_p ≥0
C_p	产品p的完工时间，C_p ≥0
Y_{i，j，i′，j′}	如果在一台机器上工件i的工序j在工件i'的工序j'之前加工，则为1，否则为0
C_max	整个调度方案的最大完工时间，C_max≥0

Tab.2 Explanation of symbols

符号	意义
i，i′	工件索引， $i, i' ∈ I$
n	工件总数
I	工件索引集，I=｛1，…，n｝
j，j′	加工工序的索引， $j, j' ∈ O i$
O_i	工件i的工序索引集
O_i，j	工件i的第j道工序
f	分布式加工工厂索引， $f ∈ F$
N_f	分布式加工工厂总数
F	分布式加工工厂索引集，F=｛1，…， N_f ｝
T_i，j	工件i的第j道工序的加工时间
T_p	产品p的装配时间
p，p′	产品索引， $p, p' ∈ P$
S_p	构成产品p的工件索引集， $S p ⊆ I$
N_p	产品数量
P	产品索引集，P=｛1，…， N_p ｝
L	一个极大的正数
m	每个工厂的机器数
k_i，j	工件i的第j道工序的指定加工机器索引，k_i，j ∈｛1，2，…，m｝
X_i，f	如果工件i被分配到工厂f，则为1，否则为0
X_i，j，f	如果工件i的第j道工序被分配到工厂f，则为1，否则为0
Z_p，p’	如果产品p在产品p'之前进行装配，则为1，否则为0
S_i，j	工件i的工序j的开工时间，S_i，j ≥0
C_i	工件i的完工时间，C_i ≥0
A_p	产品p的装配开始时间，A_p ≥0
C_p	产品p的完工时间，C_p ≥0
Y_{i，j，i′，j′}	如果在一台机器上工件i的工序j在工件i'的工序j'之前加工，则为1，否则为0
C_max	整个调度方案的最大完工时间，C_max≥0

Fig.1 Encoding scheme

Fig.2 Gantt chart corresponding to feasible solution

Fig.3 Illustration of crossover operations

Fig.4 Schematic diagram of mutation

Fig.5 Disjunctive graph of DAJSP

Fig.6 Schematic diagram of the N7 neighborhood structure

Tab.3 Example of assembly tasks for 10 products

产品	可开工时间	装配用时
P1	76	13
P2	162	35
P3	132	14
P4	183	28
P5	142	33
P6	132	19
P7	201	32
P8	97	4
P9	113	16
P10	186	22

Tab.4 Example of using a greedy algorithm for assembly process scheduling

序号	当前时间	待调度产品列表	选择工序	装配用时
1	0	P1，P8，P9，P3，P6，P5，P2，P4，P10，P7	P1	13
2	89	P8，P9，P3，P6，P5，P2，P4，P10，P7	P8	4
3	101	P9，P3，P6，P5，P2，P4，P10，P7	P9	16
4	129	P3，P6，P5，P2，P4，P10，P7	P3	14
5	146	P6，P5，P2，P4，P10，P7	P6	19
6	165	P5，P2，P4，P10，P7	P5	33
7	198	P2，P4，P10，P7	P10	22
8	220	P2，P4，P7	P4	28
9	248	P2，P7	P7	32
10	280	P2	P2	35

Tab.5 Hybrid algorithm parameters table

参数	水平值
种群规模popuSize	20，50，100
交叉概率P_c	0.85，0.90，0.95
精英保留占比P_ER/%	2，5，10，20

Fig.7 Main effects plots for algorithm parameters

Tab.6 Results of ablation experiments and comparative experiments of the algorithm （the case with 2 products）

算例	规模				MILP1	GA			GA-Grd			GATS			文献［9］结果		GTSAIGS
算例	N_f	n	m	N_p	best	best	average	time	best	average	time	best	average	time	MILP2	GA-VNS	best	average	time
DA01	2	15	15	2	2048	2421	2498.50	2.90	2324	2448.20	2.60	2052	2075.05	231.15	2048	2074	2048	2073.35	246.00
DA02	2	15	15	2	1560	1828	1911.15	2.64	1744	1871.20	1.76	1560	1562.00	51.77	1560	1560	1560	1560.00	52.71
DA03	2	15	15	2	2001	2256	2398.05	2.25	2292	2391.20	1.41	2003	2024.25	168.94	2001	2021	2003	2020.85	162.84
DA04	2	15	15	2	1852	2163	2269.00	2.19	2065	2203.20	2.17	1852	1867.20	261.17	1852	1852	1852	1854.80	266.14
DA05	2	15	15	2	2073	2262	2393.15	2.76	2205	2337.60	2.11	2073	2073.00	26.40	2073	2073	2073	2073.00	25.08
DA11	3	20	15	2	2111	2377	2456.50	2.07	2307	2416.05	1.58	2111	2117.50	137.05	2111	2169	2111	2124.40	128.80
DA12	3	20	15	2	1609	1879	1947.40	1.85	1805	1921.95	1.86	1609	1609.00	29.35	1609	1609	1609	1609.00	27.31
DA13	3	20	15	2	1969	2252	2362.65	3.35	2267	2348.55	1.72	1969	2010.25	55.11	1969	1969	1969	1988.90	58.35
DA14	3	20	15	2	1789	2162	2253.35	2.81	2087	2200.75	1.84	1789	1807.15	255.03	1789	1789	1789	1801.80	250.87
DA15	3	20	15	2	2086	2415	2491.00	2.31	2375	2446.05	2.11	2096	2100.30	59.32	2086	2100	2086	2086.00	61.56
DA21	3	20	20	2	2403	2768	2842.85	2.01	2611	2775.30	2.14	2403	2403.00	71.22	2403	2403	2403	2403.00	69.06
DA22	3	20	20	2	1793	2154	2243.40	2.64	2101	2230.55	1.71	1846	1858.35	46.77	1793	1806	1859	1859.00	48.02
DA23	3	20	20	2	2288	2627	2721.15	2.85	2558	2670.85	2.30	2288	2293.05	58.36	2288	2288	2288	2297.50	56.74
DA24	3	20	20	2	2186	2486	2633.90	2.93	2589	2663.45	1.68	2186	2186.00	52.26	2186	2186	2186	2186.00	53.01
DA25	3	20	20	2	2364	2726	2835.70	1.88	2649	2788.50	1.85	2364	2365.05	86.60	2364	2373	2364	2364.25	82.42

Tab.7 Results of ablation experiments and comparative experiments of the algorithm （the case with 3 products）

算例	规模				MILP1	GA			GA-Grd			GATS			文献［9］结果		GTSAIGS
算例	N_f	n	m	N_p	best	best	average	time	best	average	time	best	average	time	MILP2	GA-VNS	best	average	time
DA06	2	15	15	3	2165	2424	2525.60	2.59	2376	2495.40	1.61	2167	2192.75	68.35	2165	2197	2165	2172.15	61.42
DA07	2	15	15	3	1774	2075	2174.80	2.95	2043	2144.85	1.83	1774	1774.00	91.20	1774	1774	1774	1774.00	83.40
DA08	2	15	15	3	1601	1909	1966.40	2.45	1854	1923.95	1.53	1601	1601.00	30.16	1601	1601	1601	1601.00	28.21
DA09	2	15	15	3	1929	2218	2336.70	2.79	2224	2311.65	1.96	1931	1953.20	222.22	1929	1931	1929	1953.75	210.45
DA10	2	15	15	3	2417	2725	2835.00	2.02	2662	2790.60	1.01	2417	2432.10	75.46	2417	2417	2417	2437.30	67.33
DA16	3	20	15	3	2172	2449	2569.40	3.00	2363	2508.00	2.09	2182	2184.25	52.89	2172	2172	2188	2188.00	47.59
DA17	3	20	15	3	1808	2144	2225.10	2.31	2017	2150.90	2.60	1808	1808.00	34.71	1808	1808	1808	1808.00	32.68
DA18	3	20	15	3	1541	1845	1920.80	3.11	1720	1874.25	2.10	1541	1541.00	147.37	1541	1571	1541	1541.00	142.52
DA19	3	20	15	3	1812	2115	2273.30	1.50	2007	2173.90	2.19	1812	1812.00	51.39	1812	1812	1812	1812.00	47.34
DA20	3	20	15	3	2454	2664	2761.40	2.70	2511	2695.70	2.05	2454	2454.15	19.30	2454	2454	2454	2454.00	18.28
DA26	3	20	20	3	2489	2857	2951.35	2.97	2745	2926.80	1.53	2489	2510.45	131.52	2489	2489	2494	2508.45	122.85
DA27	3	20	20	3	2154	2498	2616.35	3.24	2466	2590.15	1.64	2154	2154.00	46.11	2154	2154	2154	2154.00	40.54
DA28	3	20	20	3	1860	2139	2321.60	1.50	2142	2228.85	1.67	1860	1860.00	24.39	1860	1860	1860	1860.00	22.27
DA29	3	20	20	3	2129	2541	2684.80	2.63	2525	2616.90	2.12	2145	2153.75	163.01	2129	2145	2129	2149.95	148.00
DA30	3	20	20	3	2403	3025	3120.85	2.36	2893	3065.90	1.69	2640	2640.00	34.26	2640	2640	2640	2640.00	32.38
DA31	4	30	15	3	2352	2741	2831.50	3.01	2641	2803.15	1.91	2352	2352.00	21.80	2352	2352	2352	2352.00	21.89
DA32	4	30	15	3	2174	2531	2729.50	2.89	2544	2666.00	2.56	2174	2174.00	91.74	2192	2174	2174	2174.00	82.6
DA33	4	30	15	3	2063	2428	2561.40	3.22	2332	2523.80	2.18	2063	2071.45	81.30	2063	2063	2063	2087.60	76.68
DA34	4	30	15	3	2113	2498	2600.60	4.10	2410	2565.25	3.23	2113	2113.00	53.42	2113	2113	2113	2113.00	48.13
DA35	4	30	15	3	2471	2813	2977.50	2.65	2786	2909.00	1.99	2471	2471.00	76.84	2503	2511	2471	2471.15	72.82

Tab.7 Results of ablation experiments and comparative experiments of the algorithm （the case with 3 products）

算例	规模				MILP1	GA			GA-Grd			GATS			文献［9］结果		GTSAIGS
算例	N_f	n	m	N_p	best	best	average	time	best	average	time	best	average	time	MILP2	GA-VNS	best	average	time
DA06	2	15	15	3	2165	2424	2525.60	2.59	2376	2495.40	1.61	2167	2192.75	68.35	2165	2197	2165	2172.15	61.42
DA07	2	15	15	3	1774	2075	2174.80	2.95	2043	2144.85	1.83	1774	1774.00	91.20	1774	1774	1774	1774.00	83.40
DA08	2	15	15	3	1601	1909	1966.40	2.45	1854	1923.95	1.53	1601	1601.00	30.16	1601	1601	1601	1601.00	28.21
DA09	2	15	15	3	1929	2218	2336.70	2.79	2224	2311.65	1.96	1931	1953.20	222.22	1929	1931	1929	1953.75	210.45
DA10	2	15	15	3	2417	2725	2835.00	2.02	2662	2790.60	1.01	2417	2432.10	75.46	2417	2417	2417	2437.30	67.33
DA16	3	20	15	3	2172	2449	2569.40	3.00	2363	2508.00	2.09	2182	2184.25	52.89	2172	2172	2188	2188.00	47.59
DA17	3	20	15	3	1808	2144	2225.10	2.31	2017	2150.90	2.60	1808	1808.00	34.71	1808	1808	1808	1808.00	32.68
DA18	3	20	15	3	1541	1845	1920.80	3.11	1720	1874.25	2.10	1541	1541.00	147.37	1541	1571	1541	1541.00	142.52
DA19	3	20	15	3	1812	2115	2273.30	1.50	2007	2173.90	2.19	1812	1812.00	51.39	1812	1812	1812	1812.00	47.34
DA20	3	20	15	3	2454	2664	2761.40	2.70	2511	2695.70	2.05	2454	2454.15	19.30	2454	2454	2454	2454.00	18.28
DA26	3	20	20	3	2489	2857	2951.35	2.97	2745	2926.80	1.53	2489	2510.45	131.52	2489	2489	2494	2508.45	122.85
DA27	3	20	20	3	2154	2498	2616.35	3.24	2466	2590.15	1.64	2154	2154.00	46.11	2154	2154	2154	2154.00	40.54
DA28	3	20	20	3	1860	2139	2321.60	1.50	2142	2228.85	1.67	1860	1860.00	24.39	1860	1860	1860	1860.00	22.27
DA29	3	20	20	3	2129	2541	2684.80	2.63	2525	2616.90	2.12	2145	2153.75	163.01	2129	2145	2129	2149.95	148.00
DA30	3	20	20	3	2403	3025	3120.85	2.36	2893	3065.90	1.69	2640	2640.00	34.26	2640	2640	2640	2640.00	32.38
DA31	4	30	15	3	2352	2741	2831.50	3.01	2641	2803.15	1.91	2352	2352.00	21.80	2352	2352	2352	2352.00	21.89
DA32	4	30	15	3	2174	2531	2729.50	2.89	2544	2666.00	2.56	2174	2174.00	91.74	2192	2174	2174	2174.00	82.6
DA33	4	30	15	3	2063	2428	2561.40	3.22	2332	2523.80	2.18	2063	2071.45	81.30	2063	2063	2063	2087.60	76.68
DA34	4	30	15	3	2113	2498	2600.60	4.10	2410	2565.25	3.23	2113	2113.00	53.42	2113	2113	2113	2113.00	48.13
DA35	4	30	15	3	2471	2813	2977.50	2.65	2786	2909.00	1.99	2471	2471.00	76.84	2503	2511	2471	2471.15	72.82

Tab.8 Results of ablation experiments and comparative experiments of the algorithm （the case with 4 products）

算例	规模				MILP1	GA			GA-Grd			GATS			文献［9］结果		GTSAIGS
算例	N_f	n	m	N_p	best	best	average	time	best	average	time	best	average	time	MILP2	GA-VNS	best	average	time
DA36	4	30	15	4	1873	2345	2455.05	3.20	2234	2403.95	1.82	1873	1873.00	66.45	2044	1873	1873	1873.00	61.26
DA37	4	30	15	4	2637	3021	3121.10	3.18	2934	3051.25	2.00	2637	2637.15	35.94	2637	2637	2637	2637.00	32.72
DA38	4	30	15	4	2519	2831	3007.65	3.38	2780	2929.55	1.80	2519	2519.00	39.90	2519	2519	2519	2519.00	35.62
DA39	4	30	15	4	2165	2571	2679.40	2.95	2498	2594.20	2.41	2165	2165.85	108.62	2184	2165	2165	2165.00	98.24
DA40	4	30	15	4	1681	2059	2159.3	2.37	1958	2091.2	2.43	1695	1706.15	92.61	1757	1695	1695	1709.50	80.41

Fig.8 Computation time and solution quality between GTSAIGS and GATS for different instances

Fig.9 Running time of GTSAIGS and GATS in different instances

Fig.10 Gantt chart of the optimal solution of instance DA35

Tab.9 Solution results table for actual production instance

算法	best	average	time
MILP	15166	-	7160.98
GA	16915	17633.3	3.67
GA-Grd	16358	17085.2	3.34
GATS	15234	16839.6	312.68
GTSAIGS	15166	16170.0	217.99

References 14

[1]	ZHANG Sicheng， LI Xiang， ZHANG Bowen， et al. Multi-objective Optimisation in Flexible Assembly Job Shop Scheduling Using a Distributed Ant Colony System［J］. European Journal of Operational Research， 2020， 283（2）： 441-460.
[2]	SHI Fei， ZHAO Shikui， MENG Yue. Hybrid Algorithm Based on Improved Extended Shifting Bottleneck Procedure and GA for Assembly Job Shop Scheduling Problem［J］. International Journal of Production Research， 2020， 58（9）： 2604-2625.
[3]	李仲华，唐红涛，张伟. 基于改进鲸鱼动态调度算法求解带外协的柔性装配作业车间调度［J］. 机床与液压， 2024， 52（20）： 1-9.
	LI Zhonghua， TANG Hongtao， ZHANG Wei. Solving the Scheduling of Flexible Assembly Workshops with Outsourcing Cooperation Based on Improving Whale Dynamic Scheduling Algorithm［J］. Machine Tool & Hydraulics， 2024， 52（20）： 1-9.
[4]	石飞，赵诗奎. 基于工序约束链编码的遗传算法求解产品综合调度问题［J］. 中国机械工程， 2017， 28（20）： 2483-2492.
	SHI Fei， ZHAO Shikui. Product Comprehensive Scheduling Problems Solved by Genetic Algorithm Based on Operation Constraint Chain Coding［J］. China Mechanical Engineering， 2017， 28（20）： 2483-2492.
[5]	CHAOUCH I， DRISS O B， GHEDIRA K. A Modified Ant Colony Optimization Algorithm for the Distributed Job Shop Scheduling Problem［J］. Procedia Computer Science， 2017， 112： 296-305.
[6]	ŞAHMAN M A. A Discrete Spotted Hyena Optimizer for Solving Distributed Job Shop Scheduling Problems［J］. Applied Soft Computing， 2021， 106： 107349.
[7]	JIANG Enda， WANG Ling， PENG Zhiping. Solving Energy-efficient Distributed Job Shop Scheduling via Multi-objective Evolutionary Algorithm with Decomposition［J］. Swarm and Evolutionary Computation， 2020， 58： 100745.
[8]	WANG Sihan， LI Xinyu， GAO Liang， et al. An Improved Genetic Algorithm for Distributed Job Shop Scheduling Problem［C］∥Intelligent Computing Theories and Application. Cham： Springer， 2021： 37-47.
[9]	TIAN Shichen， ZHANG Chunjiang， FAN Jiaxin， et al. A Genetic Algorithm with Critical Path-based Variable Neighborhood Search for Distributed Assembly Job Shop Scheduling Problem［J］. Swarm and Evolutionary Computation， 2024， 85： 101485.
[10]	YANG Zhijie， HU Xinkai， LI Yibing， et al. A Q-learning-based Improved Multi-objective Genetic Algorithm for Solving Distributed Heterogeneous Assembly Flexible Job Shop Scheduling Problems with Transfers［J］. Journal of Manufacturing Systems， 2025， 79： 398-418.
[11]	杨绍文，钱斌，胡蓉，等. 混合三维分布估计算法求解分布式加工装配和车辆配送集成调度问题［J］. 电子学报， 2024， 52（3）： 909-923.
	YANG Shaowen， QIAN Bin， HU Rong， et al. Hybrid Three-dimensional Estimation of Distribution Algorithm for Integrated Scheduling Problem of Distributed Production Assembly and Vehicle Delivery［J］. Acta Electronica Sinica， 2024， 52（3）： 909-923.
[12]	王玉芳，葛嘉荣，缪昇，等. 一种求解柔性作业车间的改进遗传算法［J］. 重庆理工大学学报（自然科学版）， 2021， 35（9）： 152-159.
	WANG Yufang， GE Jiarong， MIAO Sheng， et al. An Improve Genetic Algorithm for Solving Flexible Job Shop Scheduling Problem［J］. Journal of Chongqing Institute of Technology， 2021， 35（9）： 152-159.
[13]	刘设，李佳欣，田志强，等．考虑客户满意度的模糊柔性作业车间调度优化方法［J/OL］.中国机械工程［2026-03-17］..
	LIU She， LI Jiaxin， TIAN Zhiqiang，et al. Fuzzy Flexible Job-shop Scheduling Optimization Approach Considering Customer Satisfaction［J/OL］. China Mechanical Engineering.［2026-03-17］. .
[14]	周豪，张超勇，刘辉，等. 改进Jaya算法求解混合流水车间调度问题［J］. 中国机械工程， 2024， 35（8）： 1462-1471.
	ZHOU Hao， ZHANG Chaoyong， LIU Hui， et al. Improved Jaya Algorithm for Solving HFSPS［J］. China Mechanical Engineering， 2024， 35（8）： 1462-1471.