Non-indexability of the stochastic appointment scheduling problem
Non-indexability of the stochastic appointment scheduling problem
复制标题
DOI：
10.1016/j.automatica.2020.109016
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Mehdi Jafarnia-Jahromi;Rahul Jain
中科院分区：
文献类型：
--
作者：
Mehdi Jafarnia-Jahromi;Rahul Jain
考虑一组具有独立随机服务时间的工件在单机上进行调度。工作可以是手术室的手术，病人在门诊诊所的预约，等等。面临的挑战是，以确定最佳的顺序和预约时间的工作，以尽量减少一些功能的服务器空闲时间和服务开始时间延迟。我们引入了延迟和空闲时间的广义目标函数，并考虑l 1型和l 2型代价函数作为感兴趣的特殊情况。确定一个基于索引的政策，在其中调度作业的最佳顺序已经是一个开放的问题多年。例如，证明了对于l1型目标，“最小方差优先”（LVF）策略是最优的.已知对于具有特定分布的两个作业的情况，这是正确的。在本文中的一个关键结果是，最优排序问题是不可索引的，即，无论是方差，也没有任何其他这样的指数可以用来确定最优的顺序，在其中调度工作的l1和l2型目标。然后，我们表明，给定一个序列，在其中安排的工作，样本平均近似产生一个解决方案，这是统计上一致的。
Consider a set of jobs with independent random service times to be scheduled on a single machine. The jobs can be surgeries in an operating room, patients’ appointments in outpatient clinics, etc. The challenge is to determine the optimal sequence and appointment times of jobs to minimize some function of the server idle time and service start-time delay. We introduce a generalized objective function of delay and idle time, and consider l 1-type and l 2-type cost functions as special cases of interest. Determining an index-based policy for the optimal sequence in which to schedule jobs has been an open problem for many years. For example, it was conjectured that ‘least variance first’(LVF) policy is optimal for the l 1-type objective. This is known to be true for the case of two jobs with specific distributions. A key result in this paper is that the optimal sequencing problem is non-indexable, ie, neither the variance, nor any other such index can be used to determine the optimal sequence in which to schedule jobs for l 1 and l 2-type objectives. We then show that given a sequence in which to schedule the jobs, sample average approximation yields a solution which is statistically consistent.