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

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

摘要/Abstract

摘要：

针对航空复合材料热压成型制造问题，解构并提炼出并行机环境下考虑二维空间特征的批调度问题。针对航空复合材料制造的特点，考虑了类别的兼容性特征和线性批次准备时间，并以最大完工时间最小为目标，提出了结合消除对称性思想的求解二维并行机批调度的紧凑模型。此外，提出了迭代式近似搜索算法求解该问题。该算法结合了启发式和精确式算法，在迭代过程中基于精确式方法不断寻找目标值更优的可行解，且兼顾求解效率和精度。通过仿真实验设计了不同特征的算例以验证不同算法的性能，结果表明：（1）本文模型和算法具有远超经典并行机批调度模型的求解效率；（2）对模型和算法的求解效率与精度的比较验证了两者在求解不同特征的算例上的优越性；（3）所提模型和算法在统计学意义上均显著优于对比算法。最后，基于仿真实验总结了模型和算法的特征与有效性，并给出了具体的管理启示。

关键词: 航空复合材料制造, 热压成型工序, 批调度, 混合整数规划, 数学启发式

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

中图分类号:

TP18

郑绍祥,谢乃明,吴乔. 航空复材热压成型制造并行机调度模型与算法[J]. 中国管理科学, 2026, 34(9): 225-236.

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.

图/表 10

图1

表1

模型MILP中的变量含义"

变量符号	含义
$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$	连续变量, 表示最大完工时间

表1

表2

模型LS中的参数含义"

参数	含义
$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}$

表2

图2

表3

工件和设备尺寸生成策略"

策略	工件尺寸( $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

表3

表4

表5

表6

表7

表8

参考文献 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