带机器维护的最小化总误工数期望的随机排序问题研究

doi:10.15960/j.cnki.issn.1007-6093.2025.01.012

摘要/Abstract

摘要：

本文研究了一类带多次机器维护的单机随机排序问题, 其中所有工件有相同的加工时间和工期, 且工期为一个随机变量, 问题目标是确定工作间的数目及每个工作间中加工的工件数, 在此基础上使得总误工数期望最小。针对工期服从指数分布, 维护时间函数为凹函数的情况, 基于函数性质和指数分布的特点讨论了最优排序需要满足的一些性质, 给出该问题的最优排序; 针对工期服从均匀分布, 维护时间函数为线性函数的情况, 给出了一个最优算法。

关键词: 随机排序, 机器维护, 总误工数期望, 指数分布, 均匀分布

Abstract:

This paper studies the single machine stochastic scheduling problem with multiple machine maintenance activities, where all the jobs have the same processing time and due date which is a random variable. The goal is to determine the number of workshops and the number of jobs processed in each workshop so as to minimize the expected total number of tardy jobs. In the case where the due date follows the exponential distribution and the maintenance time function is concave, some properties of the optimal schedule are introduced, based on which the optimal schedule is proposed. Moreover, an optimal algorithm is proposed in the case where the due date follows the uniform distribution and the maintenance time function is a linear function.

Key words: stochastic scheduling, machine maintenance, the expected total number of tardy jobs, exponential distribution, uniform distribution

中图分类号:

O221.2

杜诗翩, 顾满占. 带机器维护的最小化总误工数期望的随机排序问题研究[J]. 运筹学学报（中英文）, 2025, 29(1): 142-158.

Shipian DU, Manzhan GU. Stochastic scheduling to minimize the expected total number of tardy jobs with machine maintenance activities[J]. Operations Research Transactions, 2025, 29(1): 142-158.

图/表 6

图1

图2

图3

图4

图5

图6

参考文献 23

1	唐恒永, 赵传立. 排序引论[M]. 北京: 科学出版社, 2002: 19- 36.
2	Johnson S M . Optimal two and three stage production schedules with setup times included[J]. Naval Research Logistics Quarterly, 1954, 1 (1): 61- 68. doi: 10.1002/nav.3800010110
3	Smith W E . Various optimizers for single-stage production[J]. Naval Research Logistics Quarterly, 1956, 3 (1-2): 59- 66. doi: 10.1002/nav.3800030106
4	Jackson J R . An extension of Johnson's results on job IDT scheduling[J]. Naval Research Logistics Quarterly, 1956, 3 (3): 201- 203. doi: 10.1002/nav.3800030307
5	Lee C Y . Machine scheduling with an availability constraint[J]. Journal of Global Optimization, 1996, 9 (3-4): 395- 416. doi: 10.1007/BF00121681
6	Sanlaville E , Schmidt G . Machine scheduling with availability constraints[J]. Acta Informatica, 1998, 35 (9): 795- 811. doi: 10.1007/s002360050143
7	Xu D , Yin Y , Li H . Scheduling jobs under increasing linear machine maintenance time[J]. Journal of Scheduling, 2010, 13 (4): 443- 449. doi: 10.1007/s10951-010-0182-0
8	Shi X , Xu D . Best possible approximation algorithms for single machine scheduling with increasing linear maintenance durations[J]. The Scientific World Journal, 2014, 2014, 1- 8.
9	Xu Z , Xu D . Single-machine scheduling with preemptive jobs and workload-dependent maintenance durations[J]. Operational Research, 2015, 15 (3): 423- 436. doi: 10.1007/s12351-015-0179-8
10	Xu Z , Xu D . Single-machine scheduling with workload-dependent tool change durations and equal processing time jobs to minimize total completion time[J]. Journal of Scheduling, 2018, 21 (4): 461- 482. doi: 10.1007/s10951-017-0543-z
11	Xu D, Xu L, Xu Z. Single machine scheduling problem with a flexible maintenance revisited [C]// International Workshop on Frontiers in Algorithmics, 2020: 74-82.
12	Pinedo M . Stochastic scheduling with release dates and due dates[J]. Operations Research, 1983, 31 (3): 559- 572. doi: 10.1287/opre.31.3.559
13	Pinedo M , Rammouz E . A note on stochastic scheduling on a single machine subject to breakdown and repair[J]. Probability in the Engineering and Informational Sciences, 1988, 2 (1): 41- 49. doi: 10.1017/S0269964800000619
14	Jia C . Stochastic single machine scheduling with an exponentially distributed due date[J]. Operations Research Letters, 2001, 28 (5): 199- 203. doi: 10.1016/S0167-6377(01)00065-7
15	Cai X , Wang L , Zhou X . Single-machine scheduling to stochastically minimize maximum lateness[J]. Journal of Scheduling, 2007, 10 (4): 293- 301.
16	Wu X , Zhou X . Stochastic scheduling to minimize expected maximum lateness[J]. European Journal of Operational Research, 2008, 190 (1): 103- 115. doi: 10.1016/j.ejor.2007.06.015
17	Ronconi D P , Powell W B . Minimizing total tardiness in a stochastic single machine scheduling problem using approximate dynamic programming[J]. Journal of Scheduling, 2010, 13 (6): 597- 607. doi: 10.1007/s10951-009-0160-6
18	Gu J , Gu M , Gu X . Optimal rules for single machine scheduling with stochastic breakdowns[J]. Mathematical Problems in Engineering, 2014, 2014 (3): 1- 9.
19	Zhang L , Lin Y , Xiao Y , et al. Stochastic single-machine scheduling with random resource arrival times[J]. International Journal of Machine Learning and Cybernetics, 2018, 9 (7): 1101- 1107. doi: 10.1007/s13042-016-0631-y
20	Gu J , Gu M , Lu X , et al. Asymptotically optimal policy for stochastic job shop scheduling problem to minimize makespan[J]. Journal of Combinatorial Optimization, 2018, 36 (1): 142- 161. doi: 10.1007/s10878-018-0294-6
21	Liu M , Liu X . Machine scheduling with stochastic release and processing times[J]. IFAC-PapersOnLine, 2019, 52 (13): 2116- 2121. doi: 10.1016/j.ifacol.2019.11.518
22	Wei W . Single machine scheduling with stochastically dependent times[J]. Journal of Scheduling, 2019, 22 (6): 677- 689. doi: 10.1007/s10951-019-00600-2
23	Buchem M , Vredeveld T . Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines[J]. Computers Operations Research, 2021, 125 (1): 1- 16.

[1]	闫喜红, 唐晓妮. 一种求解低秩矩阵补全的惯性加速交替方向法[J]. 运筹学学报（中英文）, 2025, 29(1): 172-184.
[2]	李娜, 马冉, 李龙, 张玉忠. 具有学习效应的预制构件生产调度研究[J]. 运筹学学报（中英文）, 2025, 29(1): 19-30.
[3]	耿显亚, 柴惠. 完全二部图的Gallai猜想[J]. 运筹学学报（中英文）, 2025, 29(1): 232-238.
[4]	焦成文. 具有线性前瞻区间的单机平行批在线排序[J]. 运筹学学报（中英文）, 2024, 28(4): 111-116.
[5]	张大永, 王红蕾. 基于Markov模型的低风速地区风力发电机预防性维护优化策略[J]. 运筹学学报（中英文）, 2024, 28(3): 108-120.
[6]	王福胜, 史鲁玉. 基于Polyak步长的加速临近随机方差缩减算法[J]. 运筹学学报（中英文）, 2024, 28(2): 131-142.
[7]	叶明露, 黄明. 连续非单调变分不等式的一种惯性投影算法[J]. 运筹学学报（中英文）, 2024, 28(2): 81-92.
[8]	徐娟年, 马冉, 韩雯雯, 张玉忠. 工件权重带限制的最小化最大加权完工时间的单机在线排序问题[J]. 运筹学学报（中英文）, 2024, 28(2): 71-80.
[9]	张家棋, 李觉友. 一类自适应梯度裁剪的差分隐私随机梯度下降算法[J]. 运筹学学报（中英文）, 2024, 28(2): 47-57.
[10]	程郁琨, 韩鑫, 陈修杨, 张昭. 基于网络环境的若干组合优化博弈问题研究[J]. 运筹学学报（中英文）, 2024, 28(2): 1-29.
[11]	吕雪征, 马梦郁. 链图的距离特征值[J]. 运筹学学报（中英文）, 2024, 28(1): 112-120.
[12]	白富生, 兰秘. 带隐藏约束昂贵黑箱问题的自适应代理优化方法[J]. 运筹学学报（中英文）, 2024, 28(1): 89-100.
[13]	李颖涵, 童小娇, 杨柳. 基于矩不确定模糊集的分布鲁棒风险-回报优化模型研究[J]. 运筹学学报（中英文）, 2024, 28(1): 77-88.
[14]	徐洋, 王军霖, 徐姿. 单边相对光滑非凸-凹极小极大问题的镜像梯度算法[J]. 运筹学学报（中英文）, 2024, 28(1): 18-28.
[15]	孟辛晴, 张文星. 求解一类线性等式约束凸优化问题的加速方法[J]. 运筹学学报（中英文）, 2024, 28(1): 1-17.