考虑材料外置时间窗约束的航空复材制造热压成型批调度研究

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

摘要/Abstract

摘要：

航空复材在军民用飞机中的广泛应用导致其供需矛盾突出，热压成型工序作为复材制造的瓶颈工序亟待生产调度方案的科学化与合理化。本文针对航空复合材料热压成型制造问题，通过剖析航空复材制造的特点，考虑了热压成型制造时预浸料的外置时间和工件的二维空间特征，以最小化工件的总延误时间为目标，提出了带释放时间窗的二维单机批调度模型，并根据问题特点提出了基于最大时间兼容工件集合改进的遗传算法进行求解。通过仿真实验验证模型和算法的性能，并应用于企业实际生产场景。结果显示，本文的模型在求解效率上要优于经典整数规划模型，添加的有效不等式可以使模型的求解效率平均提高15%，且模型生成的调度方案比原有的调度方案最多可改善74%的延迟情况。此外，本文真实的企业生产场景验证了算法的有效性和方法的适用性。

关键词: 航空复材制造, 热压成型工序, 二维批调度, 释放时间窗

Abstract:

The scheduling problem is investigated in the autoclave operations of aerospace composite material production. The problem stems from the wide application of composites in military and civilian aircraft， which has led to a prominent contradiction between supply and demand. As a bottleneck process in composites production delays occur frequently in autoclave operations. In this study， the production planning and scheduling of autoclave operations is taken as a research perspective， aiming to provide a timely and efficient scheduling program. The current production and processing characteristics of the autoclave operations are first analyzed， describing in detail the limitations on production and processing imposed by the out-time of the prepreg and the two-dimensional spatial characteristics of the workpiece preforms. It is assumed that the out-time of all job prepregs is known. Based on the above analysis and assumptions， the problem is for mulated under consideration as a two-dimensional single-machine batch scheduling with a release time window， with the objective of minimizing the total jobs delay time of the scheduling scheme. A mixed integer programming （MILP） model is developed and effective inequalities are proposed based on the jobs release time window. For small-scale instances of the considered problem， the MILP model can be solved by commercial solvers such as Gurobi to obtain an exact solution. For solving large-scale instances， a genetic algorithm embedded with a maximum delay jobs neighborhood search strategy is developed based on the concept of maximum time-compatible jobs set. In numerical experiments， the results show that the proposed MILP model outperforms the classical integer programming model in terms of solution efficiency， and the added effective inequalities can improve the solution efficiency of the model by 15% on average. The designed genetic algorithm can solve the large-scale arithmetic and the solving quality is significantly better than the classical genetic algorithm. The results of the case study based on the M plant show that the weekly plan scheduling scheme generated by the MILP model can improve the delay situation by up to 74% over the original scheduling scheme. The total delay time of the algorithm's resultant jobs exhibits an incremental trend with the increase in the percentage of short-release time-window jobs in the jobs.

Key words: aerospace composite manufacturing, hot compression molding process, 2D batch machine scheduling, release time window

中图分类号:

丁靖淇, 谢乃明, 郑绍祥. 考虑材料外置时间窗约束的航空复材制造热压成型批调度研究[J]. 中国管理科学, 2024, 32(12): 130-139.

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.

图/表 15

图1

表1

模型MILP中的变量定义"

符号	定义
$N$	工件集合， $N = 1,2, …, N$ ， $n$ 表示工件数量
$B$	批次集合， $B = 1,2, …, B$ ， $b$ 表示批次数量
$w i, h i$	工件 $i$ 的宽度和高度， $i ∈ N$
$p i, d i$	工件 $i$ 的加工时间和预期交付时间， $i ∈ N$
$t i$	工件 $i$ 的释放时间窗， $t i = e s t i, l s t i, i ∈ N$ ， $e s t i$ 和 $l s t i$ 表示工件的最早可开始加工时间和最晚可开始加工时间
决策变量
$u i' i$	0-1变量，若工件 $i$ 和工件 $i'$ 分配到同一个批次则为1，否则为0
$e i i'$	0-1变量，若工件 $i$ 和 $i'$ 都是关键工件，且 $i$ 在 $i'$ 之前进行加工则为1，否则为0
$o i$	0-1变量，如果第 $i$ 个工件旋转90°放置则为1，否则为0
$a i i'$	0-1变量，若第 $i$ 个工件在第 $i'$ 工件的左侧则为1，否则为0
$b i i'$	0-1变量，若第 $i$ 个工件在第 $i'$ 工件的底部则为1，否则为0
$x i$	整数变量，工件 $i$ 左下角横坐标
$y i$	整数变量，工件 $i$ 左下角纵坐标
$f i$	整数变量，工件 $i$ 的实际完工时间

表1

图2

图3

图4

图5

表2

工件尺寸与时间窗生成策略"

策略	工件尺寸（ $w j$ 和 $h j$ ）	工件释放时间窗时长
1	30%类型1，70%类型2	80%类型A，20%类型B
2	30%类型1，70%类型2	20%类型A，80%类型B
3	70%类型1，30%类型2	80%类型A，20%类型B
4	70%类型1，30%类型2	20%类型A，80%类型B
5	全部满足类型1条件	80%类型A，20%类型B
6	全部满足类型1条件	20%类型A，80%类型B

表2

表3

不同策略下三类模型结果对比"

工件生成策略		MILP1			MILP2			MILP			$R T R T 1$	$R T R T 2$
工件生成策略		Obj	Gap	RT	Obj	Gap	RT	Obj	Gap	RT	$R T R T 1$	$R T R T 2$
20	1	10	0	0.5	10	0	0.06	10	0	0.06	0.12	1.00
	2	10	0	1.29	10	0	0.09	10	0	0.07	0.05	0.78
	3	10	0	0.69	10	0	0.06	10	0	0.05	0.07	0.83
	4	10	0	2.68	10	0	0.89	10	0	1.89	0.71	2.12
	5	10	0	0.97	10	0	0.34	10	0	0.33	0.34	0.97
	6	10	0	7.08	10	0	1.84	10	0	1.53	0.22	0.83
40	1	10	0	8.54	10	0	0.34	10	0	0.25	0.03	0.74
	2	10	0	92.79	10	0	3.28	10	0	1.72	0.02	0.52
	3	10	0	29.68	10	0	11.3	10	0	2.84	0.10	0.25
	4	9	2.61	511.03	8	15.91	340.7	9	6.36	366.72	0.72	1.08
	5	9	0.49	207.49	9	0.37	191.61	9	0.37	189.36	0.91	0.99
	6	10	0	242.63	5	40.3	1191.93	4	35.31	1262.6	5.20	1.06
60	1	10	0	84.19	10	0	1.08	10	0	1.01	0.01	0.94
	2	7	19.66	716.6	10	0	7.89	10	0	5.92	0.01	0.75
	3	8	1.67	501.84	8	1.52	398.19	8	1.11	396.19	0.79	0.99
	4	4	35.33	1395.03	4	37.28	1184.15	5	31.5	1117.44	0.80	0.94
	5	10	0	368.87	10	0	176.46	10	0	80.89	0.22	0.46
	6	3	72.37	1627.99	1	74.7	1725.96	0	68.37	1800.35	1.11	1.04
80	1	9	3.16	537.5	10	0	10.46	10	0	7.45	0.01	0.71
	2	1	63.92	1791.55	9	0.67	417.62	8	2.95	413.12	0.23	0.99
	3	9	0.93	726.02	8	0.31	505.19	8	0.31	398.5	0.55	0.79
	4	0	98.73	1800.62	0	74.43	1800.25	0	69.91	1800.26	1.00	1.00
	5	6	2.93	1434.74	6	11.72	921.54	6	5.57	835.95	0.58	0.91
	6	0	null	1800.25	0	80.05	1800.54	0	71.25	1800.19	1.00	1.00

表3

表4

图6

表5

策略6下不同规模的模型和算法对比结果"

工件规模	MILP		GA-MTC		$N S G A - M T C$		$g a p G A$	$g a p N S G A$
工件规模	obj	RT	obj	RT	obj	RT	$g a p G A$	$g a p N S G A$
80	114	5400	182.82	272.90	134.33	860.77	0.60	0.18
80	71	5400	104.00	397.70	85.67	945.66	0.46	0.21
80	152	5400	169.18	414.50	137.5	810.42	0.11	-0.10
80	96	5400	122.18	522.11	110.25	845.01	0.27	0.15
80	74	5400	158.82	517.88	98.52	793.97	1.15	0.33
80	80	5400	97.55	211.11	76.25	764.82	0.22	-0.05
80	102	5400	175.09	366.74	131.67	826.55	0.72	0.29
80	90	5400	123.90	423.91	105.25	738.81	0.38	0.17
80	145	5400	135.55	439.46	130	795.12	-0.07	-0.10
80	48	5400	88.64	299.47	63.25	939.26	0.85	0.32
100	149	5400	141.01	396.26	130.21	1674.25	-0.05	-0.13
100	179	5400	152.45	865.89	129.75	1866.68	-0.15	-0.28
100	164	5400	202.55	935.82	151.01	1742.47	0.24	-0.08
100	173	5400	179.00	742.53	151.75	1812.21	0.03	-0.12
100	142	5400	151.00	766.62	112.31	1960.77	0.06	-0.21
120	284	5400	261.91	868.08	242.5	1983.45	-0.08	-0.15
120	215	5400	198.64	987.26	178.75	1886.31	-0.08	-0.17
120	122	5400	142.50	880.35	105.37	1846.79	0.17	-0.14
120	null	5400	144.50	958.11	121.37	2038.80	null	null
120	146	5400	148.55	928.76	124.15	1983.45	0.02	-0.15

表5

表6

图7

表7

图8

参考文献 24

1	Hindle K， Duffin M. Simul8-planner for composites manufacturing［C］//Proceedings of the 2006 Winter Simulation Conference. Monterey， CA， USA， December 3-6，IEEE， 2006： 1779-1784.
2	Azami A， Demirli K， Bhuiyan N. Scheduling in aerospace composite manufacturing systems： A two-stage hybrid flow shop problem［J］. The International Journal of Advanced Manufacturing Technology， 2018， 95（9-12）： 3259-3274.
3	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.
4	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.
5	Haskilic V， Ulucan A， Atici K B， et al. A real-world case of autoclave loading and scheduling problems in aerospace composite material production［J］. Omega， 2023， 120： 102918.
6	Zhang H， Ge H， Yang J， et al. Review of vehicle routing problems： Models， classification and solving algorithms［J］. Archives of Computational Methods in Engineering， 2022， 29（1）： 195-221.
7	苟梦圆，王勇，罗思妤，等. 带时间窗的多中心开闭混合式电动车配送路径优化问题研究［J］.中国管理科学，2024， DOI：10.16381/j.cnki.issn1003-207x.2023.2045 .
	Gou M Y， Wang Y， Luo S Y， et al. Open-closed mixed electric vehicle routing optimization of multi-center distribution with time windows［J］. Chinese Journal of Management Science，2024， DOI：10.16381/j.cnki.issn1003-207x.2023.2045 .
8	张歆悦，靳鹏，胡笑旋，等. 时间依赖型多配送中心带时间窗的开放式车辆路径问题研究［J］. 中国管理科学， 2024， 32（1）： 146-157.
	Zhang X Y， Jin P， Hu X X， et al. Research on the time-dependent multi-depot open vehicle routing problem with time windows［J］. Chinese Journal of Management Science， 2024， 32（1）： 146-157.
9	Lera-Romero G， Miranda Bront J J， Soulignac F J. A branch-cut-and-price algorithm for the time-dependent electric vehicle routing problem with time windows［J］. European Journal of Operational Research， 2024， 312（3）： 978-995.
10	Meiling H， Wei Z X， Wu X H， et al. Improved ant colony optimization algorithm for solving vehicle routing problem with soft time windows［J］. Computer Integrated Manufacturing System， 2023， 29（3）： 1029-1039.
11	符卓，刘文，邱萌. 带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法［J］. 中国管理科学， 2017， 25（5）： 78-86.
	Fu Z， Liu W， Qiu M. A tabu search algorithm for the vehicle routing problem with soft time windows and split deliveries by order［J］. Chinese Journal of Management Science， 2017， 25（5）： 78-86.
12	Rolim G A， Nagano M S. Structural properties and algorithms for earliness and tardiness scheduling against common due dates and windows： A review［J］. Computers & Industrial Engineering， 2020， 149： 106803.
13	Lin S W， Ying K C， Wu W J， et al. Single machine job sequencing with a restricted common due window［J］. IEEE Access， 2019（7）： 148741-148755.
14	赵子夜，陈晓慧，安友军，等. 刚柔混合约束下柔性流水车间生产调度与设备维护集成优化［J］.算机集成制造系统，2024， DOI： 10.13196/j.cims.2023.0757 .
	Zhao Z Y， Chen X H， An Y J， et al. Integrated optimization of flexible flow-shop scheduling and machine maintenance with rigid-flexible hybrid constraints［J］. Computer Integrated Manufacturing Systems， 2024，DOI： 10.13196/j.cims.2023.0757 .
15	李小林，司佳佳，尹传传，等. 考虑工件释放时间和柔性维护的单机调度问题［J］. 计算机集成制造系统， 2023， 29（2）： 581-592.
	Li X L， Si J J， Yin C C， et al. Single-machine scheduling problem considering jobs’release times and flexible maintenances［J］. Computer Integrated Manufacturing Systems， 2023， 29（2）： 581-592.
16	刘清奇，杨华龙，张燕. 考虑时间窗及恶化效应的批处理生产调度优化［J］. 系统工程理论与实践，2024， 44（6）： 2033-2045.
	Liu Q Q， Yang H L， Zhang Y. Batch production scheduling considering time window and deterioration effect［J］. Systems Engineering-Theory & Practice， 2024， 44（6）： 2033-2045.
17	何珮洋，李昆鹏，田倩南. 基于3D打印技术的备件生产与运输协同调度问题研究［J］. 中国管理科学， 2023， 31（4）： 239-249.
	He P Y， Li K P， Tian Q N. The integrated production and transportation scheduling problem based on 3D printing technology［J］. Chinese Journal of Management Science， 2023， 31（4）： 239-249.
18	Parsa N R， Karimi B， Husseini S M M. Exact and heuristic algorithms for the just-in-time scheduling problem in a batch processing system［J］. Computers & Operations Research， 2017， 80： 173-183.
19	Rolim G A， Nagano M S， Prata B D A. Formulations and an adaptive large neighborhood search for just-in-time scheduling of unrelated parallel machines with a common due window［J］. Computers & Operations Research， 2023， 153： 106159.
20	Liu Q， Cheng H， Tian T， et al. Algorithms for the variable-sized bin packing problem with time windows［J］. Computers & Industrial Engineering， 2021， 155： 107175.
21	Fleszar K. A new MILP model and fast heuristics for the variable-sized bin packing problem with time windows［J］. Computers & Industrial Engineering， 2023， 175： 108849.
22	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.
23	Fleszar K. A new MILP model and fast heuristics for the variable-sized bin packing problem with time windows［J］. Computers & Industrial Engineering， 2023， 175： 108849.
24	Chen N， Xie N， Wang Y. An elite genetic algorithm for flexible job shop scheduling problem with extracted grey processing time［J］. Applied Soft Computing， 2022， 131： 109783.

预浸料卷尺寸类型	时间窗长度（小时）
尺寸1：预浸料卷长度:30米	[2, 6]
尺寸2：预浸料卷长度:10米	[16, 24]