航空复材热压成型制造并行机调度模型与算法

doi:10.16381/j.cnki.issn1003-207x.2023.1745

Abstract

Abstract:

The autoclave molding scheduling problem in aerospace composite materials manufacturing is investigated and identified as the parallel batch-processing machines scheduling problem with two-dimensional constraints. A novel compact mathematical formulation that eliminates symmetry and minimizes the makespan is developed to define the problem with incompatibility and linear batch setup times. An iterative approximation search algorithm is proposed to handle the problem： heuristic and exact algorithms are combined in the algorithm to find a feasible solution with a better objective value through an iterative process which employs an exact method so that the problems are solved with efficiency and effectiveness. In terms of the execution on different randomly generated instances， the results show that：（1） the presented model is much more efficient than the classic one； the efficiency and effectiveness of the model and the algorithm are compared to demonstrate the superiority in solving the problem； and both the developed model and algorithm outperform the compared method in a statistical sense. In the end， the properties and performance of the model and algorithm are concluded based on the simulation experiments， and the specific managerial implications are provided.

Key words: aerospace composite materials manufacturing, autoclave molding process, batch machine scheduling, mixed-integer programming, matheuristic

CLC Number:

TP18

Shaoxiang Zheng,Naiming Xie,Qiao Wu. Model and Algorithm for Parallel Batch-processing Machines Scheduling Problem in Aerospace Composite Materials Manufacturing[J]. Chinese Journal of Management Science, 2026, 34(9): 225-236.

Figures/Tables 10

变量符号	含义
$u j b$	0-1变量, 工件j分配到批次b时为1, 否则为0
$w b k$	0-1变量, 非空批次b分配到设备k时为1, 否则为0
$z j k$	连续变量, 工件j被分配到设备k则为1, 否则为0
$l i j$ , $b i j$	0-1变量, 工件i在j左侧（下侧）时为1, 否则为0
$x j$ , $y j$	连续变量, 表示工件j左下角横（纵）坐标
$o j$	0-1变量, 工件j不旋转时为1, 否则为0
$C m a x$	连续变量, 表示最大完工时间

参数	含义
$E k b$	设备 $k$ 的第 $i$ 个批次中的动作空间集合
$E$	所有批次中的动作空间集合
$F e$	动作空间 $e$ 所在批次的工件类别
$W e, H e$	动作空间 $e$ 的宽度和高度
$θ j k i$	在 $S$ 中, 如果j在设备 $k$ 的批次 $i$ 中为1, 否则为0
$η e e' s$	$η e e' s = 1, s = 1,2, 3,4$ 代表如图2所示的4种重叠情形
$E j o (E j r)$	$j$ 可以定向(旋转)放置的动作空间集合: $E j o = {e ∈ E \| w j ≤ W e ∧ h j ≤ H e ∧ f j = F e}$ , $E j r = {e ∈ E \| w j ≤ H e ∧ h j ≤ W e ∧ f j = F e}$

策略	工件尺寸( $w j$ 和 $h j$ )	W和H
1	均匀分布于区间[1, 10]	W = H = 10
2	均匀分布于区间[1, 10]	W = H = 30
3	均匀分布于区间[1, 35]	W = H = 40
4	均匀分布于区间[10, 35]	W = H = 100
5	均匀分布于区间[1, 100]	W = H = 100
6	均匀分布于区间[1, 100]	W = H = 300
7	70%类型1, 10%其他各类型	W = H = 100
8	70%类型2, 10%其他各类型	W = H = 100
9	70%类型3, 10%其他各类型	W = H = 100
10	70%类型4, 10%其他各类型	W = H = 100

References 28

[1]	Uzsoy R. Scheduling a single batch processing machine with non-identical job sizes［J］. International Journal of Production Research， 1994， 32（7）： 1615-1635.
[2]	杜冰，陈华平，邵浩，等. 具有不同到达时间的差异工件批调度问题的蚁群聚类算法［J］. 系统工程理论与实践， 2010， 30（9）： 1701-1709.
	Du B， Chen H P， Shao H， et al. Scheduling a single batching machine with non-identical job release times and sizes using ant colony clustering［J］. Systems Engineering-theory & Practice， 2010， 30（9）： 1701-1709.
[3]	郭振和，胡雪松. 基于仿真优化的炼钢生产批调度求解方法［J］. 运筹与管理， 2019， 28（4）： 175-181.
	Guo Z H， Hu X S. Simulation optimization based solution method for production batch scheduling problem in steelmaking production［J］. Operations Research and Management Science， 2019， 28（4）： 175-181.
[4]	蒋小康，张朋，吕佑龙，等. 基于混合蚁群算法的半导体生产线炉管区调度方法［J］. 上海交通大学学报， 2020， 54（8）： 792-804.
	Jiang X K， Zhang P， Lv Y L， et al. Hybrid ant colony algorithm for batch scheduling in semiconductor furnace operation［J］. Journal of Shanghai Jiao Tong University， 2020， 54（8）： 792-804.
[5]	Queiroga E， Pinheiro R G S， Christ Q， et al. Iterated local search for single machine total weighted tardiness batch scheduling［J］. Journal of Heuristics， 2021， 27（3）： 353-438.
[6]	Trindade R S， de Araújo O C B， Fampa M. Arc-flow approach for single batch-processing machine scheduling［J］. Computers & Operations Research， 2021， 134： 105394.
[7]	Zheng S， Xie N， Wu Q， et al. Novel mathematical formulations for parallel-batching processing machine scheduling problems［J］. Computers & Operations Research， 2025， 173： 106859.
[8]	Pessoa A A， Bulhões T， Nesello V， et al. Exact approaches for single machine total weighted tardiness batch scheduling［J］. INFORMS Journal on Computing， 2022， 34（3）： 1512-1530.
[9]	Muter İ. Exact algorithms to minimize makespan on single and parallel batch processing machines［J］. European Journal of Operational Research， 2020， 285（2）： 470-483.
[10]	Yang F， Davari M， Wei W， et al. Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families［J］. European Journal of Operational Research， 2022， 303（2）： 602-615.
[11]	Husseinzadeh Kashan A， Ozturk O. A new class of lower bounds for scheduling a batch processing machine to minimize makespan［J］. European Journal of Operational Research， 2025， 327（3）： 754-775.
[12]	贺俊杰，张洁，张朋，等. 基于多智能体强化学习的纺织面料染色车间动态调度方法［J］. 计算机集成制造系统， 2023， 29（1）： 61-74.
	He J J， Zhang J， Zhang P， et al. Multi-agent reinforcement learning based textile dyeing workshop dynamic scheduling method［J］. Computer Integrated Manufacturing Systems， 2023， 29（1）： 61-74.
[13]	Li X， Zhang K. Single batch processing machine scheduling with two-dimensional Bin packing constraints［J］. International Journal of Production Economics， 2018， 196： 113-121.
[14]	Zhou S， Jin M， Liu C， et al. Scheduling a single batch processing machine with non-identical two-dimensional job sizes［J］. Expert Systems with Applications， 2022， 201： 116907.
[15]	Zhou S， Jia Z， Jin M， et al. Minimizing makespan on parallel batch processing machines with two-dimensional rectangular jobs［J］. Computers & Industrial Engineering， 2022， 169： 108167.
[16]	Polyakovskiy S， M’Hallah R. A hybrid feasibility constraints-guided search to the two-dimensional Bin packing problem with due dates［J］. European Journal of Operational Research， 2018， 266（3）： 819-839.
[17]	Arbib C， Marinelli F， Pizzuti A. Number of bins and maximum lateness minimization in two-dimensional Bin packing［J］. European Journal of Operational Research， 2021， 291（1）： 101-113.
[18]	Xie N， Zheng S， Wu Q. Two-dimensional packing algorithm for autoclave molding scheduling of aeronautical composite materials production［J］. Computers & Industrial Engineering， 2020， 146： 106599.
[19]	Zheng S， Xie N， Wu Q. Single batch machine scheduling with dual setup times for autoclave molding manufacturing［J］. Computers & Operations Research， 2021， 133： 105381.
[20]	周楠，谢乃明，郑绍祥. 考虑释放时间和装箱约束的航空复材热压成型单机批调度［J］. 工业工程与管理， 2024， 29（5）： 1-13.
	Zhou N， Xie N M， Zheng S X. Single batch machine scheduling with release times and packing constraints for autoclave molding of aerospace composites［J］. Industrial Engineering and Management， 2024， 29（5）： 1-13.
[21]	丁靖淇，谢乃明，郑绍祥. 考虑材料外置时间窗约束的航空复材制造热压成型批调度研究［J］. 中国管理科学， 2024， 32（12）： 130-139.
	Ding J Q， Xie N M， Zheng S X. Research of hot compression molding batch scheduling for aerospace composite manufacturing with material external time window constraints［J］. Chinese Journal of Management Science， 2024， 32（12）： 130-139.
[22]	Che Y， Hu K， Zhang Z， et al. Machine scheduling with orientation selection and two-dimensional packing for additive manufacturing［J］. Computers & Operations Research， 2021， 130： 105245.
[23]	Hu K， Che Y， Zhang Z. Scheduling unrelated additive manufacturing machines with practical constraints［J］. Computers & Operations Research， 2022， 144： 105847.
[24]	Fowler J W， Mönch L. A survey of scheduling with parallel batch （p-batch） processing［J］. European Journal of Operational Research， 2022， 298（1）： 1-24.
[25]	何琨，黄文奇，金燕. 基于动作空间求解二维矩形Packing问题的高效算法［J］. 软件学报， 2012， 23（5）： 1037-1044.
	He K， Huang W Q， Jin Y. Efficient algorithm based on action space for solving the 2D rectangular packing problem［J］. Journal of Software， 2012， 23（5）： 1037-1044.
[26]	Chazelle B. The bottomn-left Bin-packing heuristic： An efficient implementation［J］. IEEE Transactions on Computers， 1983， C-32（8）： 697-707.
[27]	Wei L， Hu Q， Leung S C H， et al. An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation［J］. Computers & Operations Research， 2017， 80： 113-127.
[28]	Pisinger D， Sigurd M. The two-dimensional Bin packing problem with variable Bin sizes and costs［J］. Discrete Optimization， 2005， 2（2）： 154-167.

策略	MILP					Compared
策略	#RT(秒)	#Gap(%)	#Obj_r	#RT _r (秒)	#OPT	#RT(秒)	#Gap(%)	#Obj_r	#RT _r (秒)	#OPT
1	21.34	0.00	24.58	0.05	10.00	1605.93	4.06	14.70	0.73	6.00
2	1.23	0.00	22.43	0.04	10.00	1465.21	2.35	13.67	0.80	6.33
3	11.07	0.00	23.33	0.05	10.00	2316.17	7.20	13.81	0.77	4.33
4	646.42	1.55	22.74	0.05	8.33	1895.66	6.65	13.81	0.78	5.33
5	103.88	0.00	23.75	0.05	10.00	1656.48	4.88	14.02	0.76	5.67
6	6.28	0.00	22.85	0.04	10.00	1849.11	3.33	13.88	0.80	6.33
7	147.33	0.00	22.44	0.05	10.00	1683.31	5.00	13.80	0.75	6.00
8	44.79	0.00	23.53	0.05	10.00	1688.00	5.86	14.01	0.79	5.67
9	0.27	0.00	25.33	0.05	10.00	167.99	0.03	15.28	0.71	9.67
10	27.23	0.00	22.49	0.04	10.00	1892.43	5.21	13.74	0.74	5.33

参数	策略	#Obj	#RT	UB	#RT_UB	LB	#RT_LB	Gap_LB	#Gap	iter	RT_loop	N_s	#RT_LS	#Obj_Ls	N_p	RT_RSP
m	2	172.10	73.70	178.31	0.35	156.48	40.83	0.01	0.16	10.60	32.51	6.35	32.37	172.41	92.12	0.01
	3	130.04	118.12	138.16	0.41	119.11	45.99	0.01	0.21	12.40	71.72	6.15	71.54	130.32	116.09	0.02
	5	82.60	185.21	91.98	0.46	77.23	55.80	0.03	0.24	12.98	128.95	5.60	128.72	82.84	142.85	0.03
n	20	52.04	1.65	55.69	0.27	48.91	0.58	0.00	0.17	6.56	0.80	4.37	0.78	52.22	36.85	0.00
	40	91.32	53.83	97.72	0.30	84.16	30.49	0.01	0.22	11.03	23.04	6.18	22.96	91.43	81.90	0.01
	60	126.45	127.23	135.09	0.42	116.05	56.90	0.02	0.23	13.35	69.91	6.59	69.74	126.66	126.56	0.02
	80	166.40	200.95	175.87	0.51	152.12	73.03	0.03	0.21	13.80	127.41	6.57	127.15	166.84	156.25	0.03
	100	205.04	244.72	216.39	0.54	186.81	76.69	0.04	0.21	15.21	167.49	6.45	167.09	205.47	183.53	0.04
s	1	151.97	53.08	160.84	0.35	142.47	37.09	0.01	0.15	12.57	15.63	6.47	15.43	152.43	127.80	0.02
	2	49.79	203.37	57.04	0.33	46.22	54.73	0.03	0.25	11.87	148.31	5.28	148.17	49.86	96.91	0.02
	3	122.07	148.07	130.99	0.30	105.90	61.89	0.02	0.25	13.95	85.87	6.41	85.63	122.36	144.92	0.03
	4	57.31	250.11	63.91	0.24	51.39	64.22	0.05	0.26	13.04	185.65	7.23	185.50	57.31	104.65	0.02
	5	135.95	117.14	145.09	0.36	120.03	51.01	0.01	0.23	13.57	65.77	6.48	65.54	136.33	142.89	0.02
	6	48.09	173.29	55.72	0.45	44.81	52.20	0.03	0.25	11.43	120.63	4.92	120.46	48.15	95.47	0.02
	7	159.01	80.28	166.51	0.37	142.96	44.11	0.01	0.19	11.77	35.80	6.43	35.61	159.35	115.44	0.02
	8	152.25	85.90	160.87	0.39	136.33	52.21	0.01	0.21	12.45	33.31	6.41	33.11	152.77	121.07	0.02
	9	277.80	19.84	284.39	0.86	268.37	10.38	0.00	0.07	7.29	8.59	4.64	8.44	278.17	104.02	0.01
	10	86.95	191.69	95.95	0.30	75.97	69.05	0.03	0.29	14.92	122.34	7.00	122.11	87.17	145.68	0.04

模型		s = 1	s = 2	s = 3	s = 4	s = 5	s = 6	s = 7	s = 8	s = 9	s = 10
ALNS	IASA	-0.62(0.0)	-0.74(0.0)	-0.67(-0.0)	-0.60(0.0)	-0.67(0.0)	-0.77(0.0)	-0.53(0.0)	-0.60(0.0)	-0.46(0.0)	-0.72(0.0)
ALNS	MILP	-0.84(0.0)	-0.58(0.0)	-0.71(0.0)	-0.26(0.0)	-0.79(-0.0)	-0.66(0.0)	-0.73(0.0)	-0.76(0.0)	-0.70(0.0)	-0.66(0.0)
IASA	MILP	-0.21(0.0)	0.17(0.0)	-0.05(0.29)^*	0.34(0.0)	-0.12(0.0)	0.11(0.01)	-0.20(0.0)	-0.16(0.0)	-0.24(0.0)	0.06(0.17)^*

m	模型		n = 20	n = 40	n = 60	n = 80	n = 100
m = 2	ALNS	IASA	-0.44(0.0)	-0.45(0.0)	-0.62(0.0)	-0.60(0.0)	-0.54(0.0)
	ALNS	MILP	-0.85(0.0)	-0.92(0.0)	-0.83(0.0)	-0.53(0.0)	-0.32(0.0)
	IASA	MILP	-0.41(0.0)	-0.47(0.0)	-0.20(0.0)	0.07(0.33)^*	0.22(0.0)
m = 3	ALNS	IASA	-0.53(0.0)	-0.62(0.0)	-0.72(0.0)	-0.72(0.0)	-0.67(0.0)
	ALNS	MILP	-0.9(0.0)	-0.93(0.0)	-0.82(0.0)	-0.55(0.0)	-0.28(0.0)
	IASA	MILP	-0.37(0.0)	-0.31(0.0)	-0.1(0.0)	0.17(0.001)	0.39(0.0)
m = 5	ALNS	IASA	-0.50(0.0)	-0.78(0.0)	-0.85(0.0)	-0.82(0.0)	-0.76(0.0)
	ALNS	MILP	-0.76(0.0)	-0.89(0.0)	-0.82(0.0)	-0.49(0.0)	-0.18(0.0)
	IASA	MILP	-0.26(0.0)	-0.12(0.0)	0.03(0.75)^*	0.33(0.0)	0.58(0.0)

m	n	s = 1		s = 2		s = 3		s = 4		s = 5		s = 6		s = 7		s = 8		s = 9		s = 10
2	20	0.7	4.1	0.6	0.2	0.8	4.1	0.7	1541	0.9	4	0.7	0.3	0.6	359.7	0.5	113.3	0.8	0.1	1	4.7
	40	27.6	2318	4.5	2172	43	2981	8.8	3240	31.2	2371	8.8	2163	4.7	1457	18	2649	21.4	137	38.8	2785
	60	47.3	3601	51.8	3600	106.7	3600	87.7	3601	72.9	2526	63.1	3242	62.4	3601	55.1	3298	9.5	12	121.4	3601
	80	90.2	3601	155.4	3601	146.8	3601	161.8	3601	133.2	3601	167.2	3601	58.7	3324	83.9	2908	19.4	736	184.7	3601
	100	45.5	3245	359.8	3603	185	3602	258.1	3602	158.6	3345	263.4	3601	123.7	3338	132.4	3245	42.2	757	214.9	3603
3	20	1	3	0.7	0.6	1.4	8.1	2.2	392	1.3	29.1	0.6	0.3	1.2	70.7	1	12.2	0.9	0.3	2.5	37.2
	40	21	1814	25.8	808	37.9	2160	54.5	3374	47.9	1502	34.7	912	27.2	2523	74	2561	1.9	2	68.6	3510
	60	70.1	1873	249.9	3601	101.1	2611	153.9	3600	123.7	2881	184.5	3032	65.1	3355	98	2551	24.6	393	189.8	3253
	80	38.9	1814	266.9	3601	221.4	3601	462.3	3601	144.3	2892	355.3	3601	72	3246	182.2	3601	5.9	131	281.9	3601
	100	119.6	2994	474.4	3602	246.9	3601	399	3602	260.7	3250	290.5	3602	112.8	3183	209.5	3602	46.8	1812	356.3	3608
5	20	3.6	56.9	0.9	2.9	7.5	21	1.5	5.4	10.2	278.6	0.6	18.3	1.1	11.5	1.2	8.8	1.4	0.5	10	39.8
	40	71.2	2276	72.4	1336	167.4	2883	280.9	2790	82	2560	165.2	1475	56.1	2179	20	1817	15	732	265.8	3600
	60	77.4	2178	282.7	3601	277.1	3243	562.6	3601	152.4	2168	195.3	3601	113.4	2942	107.2	3246	39.6	727	289	3246
	80	65.3	1977	500.5	3601	305.6	3242	616.7	3601	252	2919	425	3601	274.2	3601	181.1	3601	39.5	1483	390.8	3601
	100	116.6	3360	604.2	3602	372.3	3308	701.1	3602	285.7	3248	444.5	3604	231	3471	94.6	2606	28.7	1233	459.9	3602

Model and Algorithm for Parallel Batch-processing Machines Scheduling Problem in Aerospace Composite Materials Manufacturing

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 28

Related Articles 5

Metrics

Comments

Recommended 0

[1]	Chenchen Du, Xue Han, Peixin Zhao. Optimization of Airport Electric Ferry Vehicle Scheduling Considering Flight Priorities [J]. Chinese Journal of Management Science, 2026, 34(9): 164-172.
[2]	Jingqi Ding, Naiming Xie, Shaoxiang Zheng. Research of Hot Compression Molding Batch Scheduling for Aerospace Composite Manufacturing with Material External Time Window Constraints [J]. Chinese Journal of Management Science, 2024, 32(12): 130-139.
[3]	WU Jiang, WANG Min-ke, TAN Tao, Zhang Pei-wen. Modeling and Solving the Location-Inventory Problem with Nonstationary Demand Considering Carbon Cap-and-trade [J]. Chinese Journal of Management Science, 2020, 28(3): 162-173.
[4]	GUO Chuan-hao, CHEN Fang, SHAN Er-fang. Cost and Revenue Optimization for Supply Chain Network of Dairy Products with Short-Life-Cycle [J]. Chinese Journal of Management Science, 2017, 25(2): 87-97.
[5]	QI Ming-liang, QIN Kai-jie, ZHAO Yan. Research on Problem of Scheduling of Helicopter Coordinated with Vehicle for Resources Distribution in Snowstorm [J]. Chinese Journal of Management Science, 2014, 22(3): 59-67.