English

运筹学学报 >

2025 , Vol. 29 >Issue 1: 142 - 158

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.01.012

 

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

展开
  • 1. 上海财经大学数学学院, 上海 200433
顾满占, E-mail: gu.manzhan@mail.shufe.edu.cn

收稿日期: 2021-12-24

  网络出版日期: 2025-03-08

版权

运筹学学报编辑部, 2025, 版权所有，未经授权，不得转载。
收起

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

Expand
  • 1. School of Mathematics, Shanghai University of Finance and Economics, Shanghai 200433, China

Received date: 2021-12-24

  Online published: 2025-03-08

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.
Fold

摘要

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

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

本文引用格式

杜诗翩, 顾满占 . 带机器维护的最小化总误工数期望的随机排序问题研究[J]. 运筹学学报, 2025 , 29(1) : 142 -158 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.01.012

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

参考文献

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.
3 Smith W E . Various optimizers for single-stage production[J]. Naval Research Logistics Quarterly, 1956, 3 (1-2): 59- 66.
4 Jackson J R . An extension of Johnson's results on job IDT scheduling[J]. Naval Research Logistics Quarterly, 1956, 3 (3): 201- 203.
5 Lee C Y . Machine scheduling with an availability constraint[J]. Journal of Global Optimization, 1996, 9 (3-4): 395- 416.
6 Sanlaville E , Schmidt G . Machine scheduling with availability constraints[J]. Acta Informatica, 1998, 35 (9): 795- 811.
7 Xu D , Yin Y , Li H . Scheduling jobs under increasing linear machine maintenance time[J]. Journal of Scheduling, 2010, 13 (4): 443- 449.
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.
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.
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.
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.
14 Jia C . Stochastic single machine scheduling with an exponentially distributed due date[J]. Operations Research Letters, 2001, 28 (5): 199- 203.
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.
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.
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.
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.
21 Liu M , Liu X . Machine scheduling with stochastic release and processing times[J]. IFAC-PapersOnLine, 2019, 52 (13): 2116- 2121.
22 Wei W . Single machine scheduling with stochastically dependent times[J]. Journal of Scheduling, 2019, 22 (6): 677- 689.
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.
Options
文章导航

/

〈 〉