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

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

CLC Number:

O221.2

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.

Figures/Tables 6

References 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]	Xihong YAN, Xiaoni TANG. An inertial alternating direction method of multiplier for low rank matrix completion [J]. Operations Research Transactions, 2025, 29(1): 172-184.
[2]	Na LI, Ran MA, Long LI, Yuzhong ZHANG. Study on the production scheduling of prefabricated components with learning effect [J]. Operations Research Transactions, 2025, 29(1): 19-30.
[3]	GENG Xianya, CHAI Hui. Gallai's conjecture for complete bipartite graphs [J]. Operations Research Transactions, 2025, 29(1): 232-238.
[4]	Chengwen JIAO. Online scheduling on a single parallel-batch machine with linear lookahead [J]. Operations Research Transactions, 2024, 28(4): 111-116.
[5]	Dayong ZHANG, Honglei WANG. Optimization strategy for preventive maintenance of wind turbines in low wind speed areas based on Markov models [J]. Operations Research Transactions, 2024, 28(3): 108-120.
[6]	Fusheng WANG, Luyu SHI. An accelerated proximal stochastic gradient method with variance reduction based on Polyak step size [J]. Operations Research Transactions, 2024, 28(2): 131-142.
[7]	Minglu YE, Ming HUANG. An inertial projection algorithm for nonmonotone continuous variational inequalities [J]. Operations Research Transactions, 2024, 28(2): 81-92.
[8]	Juannian XU, Ran MA, Wenwen HAN, Yuzhong ZHANG. Single-machine online scheduling to minimize maximum weighted completion time with limited weights [J]. Operations Research Transactions, 2024, 28(2): 71-80.
[9]	Jiaqi ZHANG, Jueyou LI. A class of differential privacy stochastic gradient descent algorithm with adaptive gradient clipping [J]. Operations Research Transactions, 2024, 28(2): 47-57.
[10]	Yukun CHENG, Xin HAN, Xiuyang CHEN, Zhao ZHANG. Survey on several combinatorial optimization games on networks [J]. Operations Research Transactions, 2024, 28(2): 1-29.
[11]	Xuezheng LYU, Mengyu MA. The distance spectra of chain graphs [J]. Operations Research Transactions, 2024, 28(1): 112-120.
[12]	Fusheng BAI, Mi LAN. An adaptive surrogate optimization method for expensive black-box problems with hidden constraints [J]. Operations Research Transactions, 2024, 28(1): 89-100.
[13]	Yinghan LI, Xiaojiao TONG, Liu YANG. The study of distributionally robust reward-risk optimization models with moment-based ambiguity set [J]. Operations Research Transactions, 2024, 28(1): 77-88.
[14]	Yang XU, Junlin WANG, Zi XU. A mirror descent gradient ascent algorithm for one side relatively smooth nonconvex-concave minimax optimization problems [J]. Operations Research Transactions, 2024, 28(1): 18-28.
[15]	Xinqing MENG, Wenxing ZAHNG. An accelerated method for solving a class of linear equality constrained convex optimization [J]. Operations Research Transactions, 2024, 28(1): 1-17.

Stochastic scheduling to minimize the expected total number of tardy jobs with machine maintenance activities

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 23

Related Articles 15

Recommended Articles

Metrics

Comments