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

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

CLC Number:

TP273

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.

Figures/Tables 12

符号	定义
$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$ 为维护

符号	概率	事件	下一期状态 $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$

实验参数	水平 $低, 高$
产品到达率 $λ 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$

组数	加工量（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

组数	加工量（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

指标	组别	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

组数	加工量（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

组数	加工量（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

References 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.

A Dynamic Scheduling and Preventive Maintenance Method Based on Product-machine Assignment

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 24

Related Articles 13

Metrics

Comments

Recommended 0

[1]	Xiangtianrui Kong, Yanhong Long, Kaize Yu, Zelong Yi, Pengyu Yan. Optimal Lot-sizing for Digital Perishable Auction Platform with Demand Learning [J]. Chinese Journal of Management Science, 2025, 33(6): 222-232.
[2]	Wenjie Dong, Na Zhang, Chenchen Hua, Zhigeng Fang. Optimal Imperfect Maintenance Strategies for Repairable Systems Considering Repair Fatigue [J]. Chinese Journal of Management Science, 2025, 33(6): 151-159.
[3]	Wei-wei CUI,Xin-bo LIU. Integrating Production Planning and Energy Controlling for the Manufacturing Plant with Alternative Power Supplier [J]. Chinese Journal of Management Science, 2023, 31(8): 173-183.
[4]	XIE Fang, LI Hong-bo, BAI Qing-guo. Stochastic Multi-mode Resource-constrained Project Scheduling [J]. Chinese Journal of Management Science, 2022, 30(10): 155-164.
[5]	LIU Qin-ming, LIU Wen-yi, YE Chun-ming. Research on Joint Optimization of Equipment Maintenance and Buffer Stock by Considering Insufficient Buffer Stock [J]. Chinese Journal of Management Science, 2022, 30(1): 143-153.
[6]	LU Zhen, XU Jian, YANG Yun-feng. The Decision of Economic Production Quantity with Quality-Contingent Demand and Perfect Preventative Maintenance [J]. Chinese Journal of Management Science, 2020, 28(5): 71-78.
[7]	LIU Xue-juan, ZHAO Fei, MA Xiao-yang. Joint Optimal Multi-product Production and Non-cyclical Preventive Maintenance Planning Model [J]. Chinese Journal of Management Science, 2017, 25(11): 189-196.
[8]	ZHENG Rui, LV Wen-yuan. Modelling of Simultaneous Decision Making of Production Control and Maintenance Schedule in the Context of Failure Downtime [J]. Chinese Journal of Management Science, 2016, 24(8): 116-122.
[9]	LI Zhi, TAN De-qing. Research on Optimal Production-Inventory Control Policy for Erlang Assemble-To-Order System [J]. Chinese Journal of Management Science, 2016, 24(6): 61-69.
[10]	LIU Shu-ren, TANG Pei, HUANG Ying-na. Inventory Management with Selling by Internet Auctions and Purchasing by Reverse Auctions [J]. Chinese Journal of Management Science, 2015, 23(11): 62-69.
[11]	YANG Qin, ZHOU Guo-hua, YU Wei. Study on the Dynamic Scheduling Problem of 4S Auto Dealership Maintenance Service System Based on Theory of Constraint [J]. Chinese Journal of Management Science, 2011, 19(3): 88-93.
[12]	ZHENG Rui, LV Wen-yuan. Modelling of Preventive Maintenance Based on the Delay Time Theory and Case Study [J]. Chinese Journal of Management Science, 2010, 18(2): 48-54.
[13]	YAO Jian-ming, ZHANG Xiu-min, LIU Li-wen. Analysis on Pull Supply Chain Dynamic Scheduling Based on Improved Ant Algorithm [J]. Chinese Journal of Management Science, 2006, (3): 20-26.