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

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.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2025.01.012

https://www.ort.shu.edu.cn/EN/Y2025/V29/I1/142

Figures/Tables 6

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]	WANG Xiangfeng, ZENG Shangzhi, ZHANG Jin, ZHOU Jinchuan. Proximal-based methods can guarantee blunt local minimizer for nonconvex nonsmooth optimization problem [J]. Operations Research Transactions, 2026, 30(2): 1-23.
[2]	MEN Yanchao, LI Xudong. Fast algorithm for OWL1 norm constrained regression model [J]. Operations Research Transactions, 2026, 30(2): 24-44.
[3]	ZENG Jing, XIANG Yao, ZHANG Wenyan. The well-posedness of traffic equilibrium problems [J]. Operations Research Transactions, 2026, 30(2): 58-68.
[4]	WANG Feng, HANG Bo, HUANG Jinzhou, XU Degang, ZHANG Zeyu, LIU Jiamou. Research of touring route planning based on spatio-temporal awareness [J]. Operations Research Transactions, 2026, 30(2): 69-78.
[5]	WU Xiaoyu, SHAO Hu, LIU Pengjie, ZHOU Jincheng. Two RMIL-type conjugate gradient methods with sufficient descent property and applications in image restoration [J]. Operations Research Transactions, 2026, 30(2): 79-92.
[6]	CUI Hengxin, JIANG Fan. Inexact proximal point algorithms and projection methods for monotone variational inequalities [J]. Operations Research Transactions, 2026, 30(2): 194-208.
[7]	ZHANG Xuefeng, PENG Xiao, CHEN Liangyu, YANG Zhengfeng, ZENG Zhenbing. A review of intelligent branch and bound algorithms for mixed integer linear programming problems [J]. Operations Research Transactions, 2026, 30(2): 237-270.
[8]	WEI Jiazhen, BIAN Wei. A survey on research advances in consensus-based optimization algorithm [J]. Operations Research Transactions, 2026, 30(1): 1-23.
[9]	ZHOU Yunxu, YAO Fanjun, GAO Hongwei. Blockchain empowering the digital transformation: Study on the coordination strategies of supply chain [J]. Operations Research Transactions, 2026, 30(1): 61-74.
[10]	ZHAO Hongxin, KONG Lingchen. Research on diversification portfolio optimization model and method [J]. Operations Research Transactions, 2026, 30(1): 75-92.
[11]	SUN Ke, WANG Jinting, WANG Zhongbin. The economics of waiting-area entertainment [J]. Operations Research Transactions, 2026, 30(1): 93-107.
[12]	XU Ke, JI Lanping, GONG Hua, LIU Peng, SUN Wenjuan. A coordinated multi-agent production and transportation scheduling on parallel machines based on auction algorithm [J]. Operations Research Transactions, 2026, 30(1): 121-136.
[13]	WANG Ziqi, WANG Junlin, XU Zi. A variance reduced gradient descent ascent algorithm for a class of nonconvex-nonconcave minimax problems [J]. Operations Research Transactions, 2026, 30(1): 197-206.
[14]	YANG Jinji, SHEN Chungen, YU Zhensheng. Convergence analysis of an adaptive proximal gradient-subgradient algorithm for square-root-loss regression problems [J]. Operations Research Transactions, 2026, 30(1): 217-234.
[15]	Ruiqing SUN, Rui ZHANG, Yan LAN, Weidong LI. LPT algorithm for early work maximization problem [J]. Operations Research Transactions, 2025, 29(4): 249-254.

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

Related Articles 15

Recommended Articles

Metrics

Comments