基于产品—机器指派的动态调度和预防性维护方法

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

摘要/Abstract

摘要：

本文面向多产品、多机器的柔性制造系统，研究动态调度与预防性维护决策联合优化。考虑产品到达、加工等过程的随机性以及设备状态的劣化与维护恢复，提出产品-机器指派框架。先以混合整数线性规划按机器维度将原问题结构化分解为若干单机子问题，并通过匹配产品需求与机器特性在产出最大化与机器专用性之间实现权衡。继而建立并求解单机连续时间马尔可夫决策过程，合成得到原系统的近似最优策略。该方法使总体计算复杂度随机器数近似线性增长，具备大规模场景的可扩展性。数值仿真结果表明，产品-机器指派框架在提升加工量与缩短周期时间方面较传统调度方法具有显著优势。

关键词: 产品-机器指派, 动态调度, 预防性维护, 马尔科夫决策过程

Abstract:

A joint production dispatching and preventive maintenance problem in multi-product， heterogeneous-machine manufacturing is addressed through a Product-Machine Assignment （PMA） framework. The assignment is formulated as a mixed-integer linear program that matches product types to machines and controls per-machine variety through a penalty parameter $κ$ ， achieving a balance between throughput and machine specialization. The assignment decomposes the system into independent multi-product single-machine subproblems， each solved as a continuous-time Markov decision process to coordinate dispatching and preventive maintenance. Combining these yields a near-optimal system policy with computational complexity growing approximately linearly in the number of machines. Numerical experiments on 30 instances， compared with $C μ$ ， First-Come-First-Served， and Round-Robin under throughput and cycle-time metrics， show that PMA maintains throughput while notably reducing cycle time. Additional tests under non-Markovian inter-event times and a real semiconductor workstation dataset exhibit consistent performance. The results indicate that PMA provides a scalable and interpretable approach for real-time joint dispatching and maintenance decisions in large heterogeneous manufacturing systems.

Key words: product-machine assignments, dynamic scheduling, preventive maintenance, Markov decision process

中图分类号:

TP273

杨洋,张斌,吴政鸿. 基于产品—机器指派的动态调度和预防性维护方法[J]. 中国管理科学, 2026, 34(9): 173-183.

Yang Yang,Bin Zhang,Chenghung Wu. A Dynamic Scheduling and Preventive Maintenance Method Based on Product-machine Assignment[J]. Chinese Journal of Management Science, 2026, 34(9): 173-183.

图/表 12

表1

数学符号及其定义"

符号	定义
$j$	异质机器， $j ∈ 1, 2, …, J$
$i$	产品类型， $i ∈ 1, 2, …, I$
$h$	机器的健康状态， $h ∈ 0, 1, …, H$ ，其中 $0$ 为完全失效， $H$ 为完全健康
$q i$	类型 $i$ 产品的排队长度
$c i$	类型 $i$ 产品的单位等待成本
$λ i$	类型 $i$ 产品的到达率
$τ i, j h$	机器 $j$ 处于健康状态 $h$ 时加工类型 $i$ 产品的加工率（ $τ i, j 0 = 0$ ）
$δ i, j h$	机器 $j$ 处于健康状态 $h$ 时加工类型 $i$ 产品的退化率（从 $h$ 降到 $h - 1$ ， $δ i, j 0 = 0$ ）
$γ j$	机器 $j$ 的维护/维修率
$θ i$	系统对类型 $i$ 产品的总加工比例（产品 $i$ 长期平均加工率/产品 $i$ 到达率）
$X i j$	机器 $j$ 是否被指派处理类型 $i$ 产品， $X i j ∈ 0, 1$ ，其中 $0$ 为不指派， $1$ 为指派
$e i, j h$	机器 $j$ 处于健康状态 $h$ 时加工类型 $i$ 产品的时间比例
$f j h$	机器 $j$ 处于健康状态 $h$ 时进行预防性维护的时间比例
$κ$	惩罚参数
$b$	机器 $j$ 是否可用， $b ∈ 0,1$ ，其中 $0$ 为在维护/维修， $1$ 为可用
$I j$	机器 $j$ 经指派后加工的产品类型集合， $I j ⊆ I$
$S t$	机器 $j$ 在 $t$ 时刻的状态， $S t = h, b, q$ ，其中 $q = q i - i ∈ I j$ ,其维度为 $I j$
$x j$	机器 $j$ 的调度决策， $x j = i ∈ 1, 2, …, I$
$y j$	机器 $j$ 的预防性维护决策， $y j ∈ 0,1$ ，其中 $0$ 为不维护， $1$ 为维护

表1

图1

图2

表2

事件触发型离散时间马尔可夫过程的转移概率"

符号	概率	事件	下一期状态 $S t + 1$
$P i 1$	$λ i / φ$	类型 $i$ 产品到达	$h, b, q 1, …, q i + 1, …, q I$
$P i, j, h 2$	$b τ i, j h / φ$	机器 $j$ 在健康状态 $h$ 下完成加工产品 $i$	$h, b, q 1, …, q i - 1, …, q I$
$P i, j, h 3$	$b δ i, j h / φ$	机器 $j$ 在健康状态 $h$ 下加工产品 $i$ 时退化	$h - 1, b, q$
$P j 4$	$(1 - b) γ j / φ$	机器 $j$ 完成维护/维修	$H, 1, q$
$P j 5$	$1 - ∑ h = 0 H ∑ i ∈ I j P i 1 + P i j 2 + P i j 3 - P j 4$	系统无变化	$h, b, q$

表2

表3

类正交实验设计的参数低—高水平"

实验参数	水平 $低, 高$
产品到达率 $λ i$	$2, 3$
机器在完全健康时的加工率 $τ i, j 2$	$4, 6$
机器加工衰退系数 $r i j (τ i, j 1 = r i j τ i, j 2)$	$0.5, 0.8$
机器在完全健康时（ $h = 2$ ）的退化率 $δ i, j 2$	$1 / 15, 1 / 10$
机器在疲劳时（ $h = 1$ ）的退化率 $δ i, j 1$	$1 / 12, 1 / 8$
机器维护/维修率 $γ j$	$1 / 3, 1 / 2$

表3

表4

三产品三机（I=3, J=3）系统仿真结果"

组数	加工量（throughput）				排名	周期时间（cycle time）
组数	PMA	$C μ$	FCFS	RR	排名	PMA	$C μ$	FCFS	RR	排名
1	1	0.999971	0.999966	0.997559	1	1	1.264588	1.986918	42.34997	1
2	1	1.000050	0.999897	0.991072	2	1	2.452379	4.219488	86.43064	1
3	1	1.000990	1.000920	0.951533	3	1	1.801101	2.703178	372.1982	1
4	1	0.999743	0.999638	0.974946	1	1	1.839797	3.288675	223.1338	1
5	1	1.000690	1.000650	0.976180	3	1	1.819549	2.601473	200.5406	1
6	1	1.000070	0.999835	0.945081	2	1	1.339083	4.561200	282.2754	1
7	1	0.998862	0.980997	0.915783	1	1	5.936320	91.12744	399.4801	1
8	1	0.999522	0.998956	0.902262	1	1	2.928198	10.96073	419.5037	1
9	1	0.999043	0.996639	0.922214	1	1	2.557469	23.77550	357.4400	1
10	1	0.999556	0.998368	0.922119	1	1	3.805694	14.93735	361.6735	1
11	1	1.000000	0.944389	0.903269	1	1	1.913713	114.9279	199.9187	1
12	1	0.952196	0.863463	0.843457	1	1	104.4222	170.1283	345.5426	1
13	1	0.985381	0.921614	0.860281	1	1	35.61172	138.7980	250.3416	1
14	1	0.994109	0.896403	0.875915	1	1	16.21934	178.9412	210.9248	1
15	1	0.953929	0.911621	0.880020	1	1	112.6484	196.6269	251.3258	1
平均	1	0.992270	0.967560	0.924110	1	1	19.77064	63.97229	266.8720	1

表4

表5

五产品三机（I=5, J=3）系统仿真结果"

组数	加工量（throughput）				排名	周期时间（cycle time）
组数	PMA	$C μ$	FCFS	RR	排名	PMA	$C μ$	FCFS	RR	排名
1	1	0.999896	0.999804	0.999320	1	1	1.518906	2.819724	13.75071	1
2	1	0.999582	0.999527	0.952204	1	1	1.762471	2.669434	274.6904	1
3	1	0.999434	0.999520	0.966677	1	1	3.704707	3.454183	247.1250	1
4	1	1.000150	1.000120	0.998866	3	1	1.267441	1.999892	25.19993	1
5	1	1.000190	1.000170	0.999191	3	1	1.098525	2.031347	16.80865	1
6	1	1.000190	0.999575	0.996797	2	1	1.997733	11.17308	38.66972	1
7	1	0.998396	0.978121	0.878477	1	1	8.353749	52.40721	298.2966	1
8	1	0.988495	0.994090	0.907828	1	1	61.24679	35.66157	427.1458	1
9	1	1.000150	0.999910	0.968758	2	1	1.402976	4.471217	201.6394	1
10	1	0.999788	0.999511	0.969740	1	1	1.016604	3.920757	149.3260	1
11	1	0.999088	0.892931	0.922390	1	1	4.575516	159.5305	220.2111	1
12	1	0.936060	0.899046	0.823862	1	1	7.553965	9.423581	22.53733	1
13	1	0.920833	0.890812	0.850538	1	1	144.5821	102.8903	320.3413	1
14	1	1.000310	0.962727	0.899880	2	1	1.813552	114.9261	332.0536	1
15	1	0.999820	0.953125	0.905323	1	1	1.116295	88.80913	207.3520	1
平均	1	0.989490	0.971270	0.935990	1	1	16.20075	39.74587	186.3432	1

表5

图3

图4

表6

PMA与其他策略的成对t 检验结果"

指标	组别	PMA vs. $C μ$			PMA vs. FCFS			PMA vs. RR
指标	组别	B	I	W	B	I	W	B	I	W
加工量	一	4	11	0	8	7	0	15	0	0
加工量	二	3	12	0	7	8	0	12	3	0
周期时间	一	15	0	0	15	0	0	15	0	0
周期时间	二	13	2	0	15	0	0	15	0	0

表6

表7

三产品三机（I=3, J=3）非马尔可夫系统仿真结果"

组数	加工量（throughput）				排名	周期时间（cycle time）
组数	PMA	$C μ$	FCFS	RR	排名	PMA	$C μ$	FCFS	RR	排名
1	1	1.000300	1.000260	0.997253	3	1	1.244983	1.855764	53.11870	1
2	1	1.000340	1.000290	0.987597	3	1	2.583740	4.182920	116.5188	1
3	1	0.999955	0.999978	0.969720	1	1	1.919465	2.792775	252.7203	1
4	1	0.999997	0.999920	0.977503	1	1	1.737863	3.041734	291.5189	1
5	1	0.999449	0.999452	0.973035	1	1	1.562020	2.193473	308.7684	1
6	1	0.999612	0.999241	0.948604	1	1	1.366456	4.241919	185.1681	1
7	1	0.999579	0.987093	0.905298	1	1	7.815308	71.24070	443.9721	1
8	1	1.001390	1.000260	0.891561	3	1	2.999554	10.39073	425.6822	1
9	1	1.000160	0.998282	0.926443	2	1	2.654707	24.96753	357.8863	1
10	1	0.999629	0.997906	0.931753	1	1	3.944833	16.44068	326.5467	1
11	1	0.999984	0.937843	0.898725	1	1	1.616659	197.0719	318.9118	1
12	1	0.947369	0.867209	0.839919	1	1	79.98627	118.8993	242.5110	1
13	1	0.984864	0.922510	0.853131	1	1	27.18143	102.1317	192.3209	1
14	1	0.994618	0.899893	0.875854	1	1	14.12508	173.9866	210.6253	1
15	1	0.951994	0.909050	0.884920	1	1	1.244983	1.855764	53.11870	1
平均	1	0.991950	0.967950	0.924090	1	1	2.583740	4.182920	116.5188	1

表7

表8

半导体实际加工系统仿真结果"

组数	加工量（throughput）				排名	周期时间（cycle time）
组数	PMA	$C μ$	FCFS	RR	排名	PMA	$C μ$	FCFS	RR	排名
1	1	6.062083	5.871439	722.3035	1	1	0.9978	0.9982	0.12071	1
2	1	37.23411	39.85468	378.481	1	1	0.9339	0.93115	0.11134	1
3	1	26.2881	26.33949	130.6059	1	1	0.86642	0.86654	0.1193	1
平均	1	23.19476	24.02187	410.4635	1	1	0.9327	0.93196	0.11712	1

表8

参考文献 24

[1]	Geurtsen M， Didden J B H C， Adan J， et al. Production， maintenance and resource scheduling： A review［J］. European Journal of Operational Research， 2023， 305（2）： 501-529.
[2]	Serrano-Ruiz J C， Mula J， Poler R. Smart manufacturing scheduling： A literature review［J］. Journal of Manufacturing Systems， 2021， 61： 265-287.
[3]	刘虎沉，王鹤鸣，施华. 智能质量管理：理论模型、关键技术与研究展望［J］. 中国管理科学， 2024， 32（3）： 287-298.
	Liu H C， Wang H M， Shi H. Intelligent quality management： Theoretical framework， key technologies， and research prospect［J］. Chinese Journal of Management Science， 2024， 32（3）： 287-298.
[4]	Lu B， Luo Y. A dynamic condition-based maintenance policy for heterogeneous-wearing tools with considering product quality deterioration［J］. International Journal of Production Research， 2024， 62（19）： 7096-7113.
[5]	Yang W， Chen L， Dauzère-Pèrés S. A dynamic optimisation approach for a single machine scheduling problem with machine conditions and maintenance decisions［J］. International Journal of Production Research， 2022， 60（10）： 3047-3062.
[6]	Yin J， Ye Z， Cui L. Reliability and optimal replacement policy of a multistate system under Markov renewal shock model［J］. IEEE Transactions on Reliability， 2025， 74（1）： 2214-2225.
[7]	Yao X， Xie X， Fu M C， et al. Optimal joint preventive maintenance and production policies［J］. Naval Research Logistics （NRL）， 2005， 52（7）： 668-681.
[8]	Huang J， Down D G， Lewis M E， et al. Dynamically scheduling and maintaining a flexible server［J］. Naval Research Logistics （NRL）， 2022， 69（2）： 223-240.
[9]	Wu C H， Yao Y C， Dauzère-Pérès S， et al. Dynamic dispatching and preventive maintenance for parallel machines with dispatching-dependent deterioration［J］. Computers & Operations Research， 2020， 113： 104779.
[10]	安友军，陈晓慧，胡家文，等. 基于多阶段-多阈值的设备退化建模与维护决策优化［J］. 系统工程理论与实践， 2024， 44（8）： 2700-2717.
	An Y J， Chen X H， Hu J W， et al. Equipment degradation modeling and maintenance decision optimization based on multi-phase and multi-threshold［J］. Systems Engineering-Theory & Practice， 2024， 44（8）： 2700-2717.
[11]	金爽，周晶，胡骞. 考虑灵活弧中断的网络维护调度问题及其算法研究［J］. 中国管理科学， 2025， 33（8）： 250-259.
	Jin S， Zhou J， Hu Q. Research on the network maintenance scheduling problem with flexible arc outages and its algorithm［J］. Chinese Journal of Management Science， 2025， 33（8）： 250-259.
[12]	Forootani A， Iervolino R， Tipaldi M， et al. Off-policy temporal difference learning for perturbed Markov decision processes［J］. IEEE Control Systems Letters， 2024， 8： 3488-3493.
[13]	李阳，范厚明，张晓楠. 动态需求下车辆路径问题的周期性优化模型及求解［J］. 中国管理科学， 2022， 30（8）： 254-266.
	Li Y， Fan H M， Zhang X N. A periodic optimization model and solution for capacitated vehicle routing problem with dynamic requests［J］. Chinese Journal of Management Science， 2022， 30（8）： 254-266.
[14]	Saffar F， Moghaddam S K， Huang S. Dynamic layout design for scalable reconfigurable manufacturing systems［J］. International Journal of Production Research， 2025， 63（17）： 6530-6552.
[15]	刘乐. 可外包条件下最大时间偏离受限的单机重调度［J］. 系统工程学报， 2019， 34（1）： 12-28.
	Liu L. Single-machine rescheduling with outsourcing allowed and a limit to maximum time deviation［J］. Journal of Systems Engineering， 2019， 34（1）： 12-28.
[16]	Park J， Han J， Lee K. Integer optimization models and algorithms for the multi-period non-shareable resource allocation problem［J］. European Journal of Operational Research， 2024， 317（1）： 43-59.
[17]	镇璐，高佳静，谭哲一. 多卡车与多无人机协同配送路径优化问题研究［J］. 管理科学学报， 2024， 27（7）： 1-18.
	Zhen L， Gao J J， Tan Z Y. Routing problem of multiple trucks and drones cooperative delivery［J］. Journal of Management Sciences in China，2024， 27（7）： 1-18.
[18]	Hu J， Wang H， Tang H K， et al. Knowledge-enhanced reinforcement learning for multi-machine integrated production and maintenance scheduling［J］. Computers & Industrial Engineering， 2023， 185： 109631.
[19]	Sabri A， Allaoui H， Souissi O. Reinforcement learning and stochastic dynamic programming for jointly scheduling jobs and preventive maintenance on a single machine to minimise earliness-tardiness［J］. International Journal of Production Research， 2024， 62（3）： 705-719.
[20]	Satic U， Jacko P， Kirkbride C. A simulation-based approximate dynamic programming approach to dynamic and stochastic resource-constrained multi-project scheduling problem［J］. European Journal of Operational Research， 2024， 315（2）： 454-469.
[21]	初梓豪，徐哲，刘东宁. 带有活动重叠的随机调度问题建模与算法研究［J］. 中国管理科学， 2024， 32（7）： 84-94.
	Chu Z H， Xu Z， Liu D N. Model and algorithm on stochastic scheduling problem with activity overlapping［J］. Chinese Journal of Management Science， 2024， 32（7）： 84-94.
[22]	An Y， Chen X， Hu J， et al. Integrated optimization of condition-based preventive maintenance and production rescheduling with multi-phase processing speed selection and old machine scrap［J］. Reliability Engineering & System Safety， 2023， 238： 109399.
[23]	Xia L， Zhang Z G， Li Q L. Ac/μ-rule for job assignment in heterogeneous group-server queues［J］. Production and Operations Management， 2022， 31（3）： 1191-1215.
[24]	Kopp D， Hassoun M， Kalir A， et al. SMT2020—a semiconductor manufacturing testbed［J］. IEEE Transactions on Semiconductor Manufacturing， 2020， 33（4）： 522-531.