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

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

作　　者：杜诗翩 顾满占 DU Shipian;GU Manzhan(School of Mathematics,Shanghai University of Finance and Economics,Shanghai 200433,China)

机构地区：[1]上海财经大学数学学院,上海200433

出　　处：《运筹学学报(中英文)》2025年第1期142-158,共17页Operations Research Transactions

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

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

分 类 号：O221.2[理学—运筹学与控制论]