Notes(Jul 5 2018)

來自專欄 Research Notes3 人贊了文章

（為了拯救自己的拖延症，決定每三天至少一篇）

（中間具體的formula和deduction的部分因為無法直接導入latex或者pdf所以放棄了...主要的內容重點在connection和simulation techniques上面，不過這一篇寫的實在太爛，明天應該會再修改的精簡一點吧= =）

Ibrahim, R. and Whitt, W., 2009. Real-time delay estimation based on delay history.Manufacturing & Service Operations Management,11(3), pp.397-415.

Based on recent customer delay experience (three main estimators):

1. The delay of the last customer to enter service (LES)
2. The delay experienced so far by the customer at the head of the line(HOL)
3. The delay experienced by the customer to have arrived most recently among those who have already completed service (RCS)

Steps:

• Compare these estimators to the standard estimator based on the queue length (QL)
• Performance is characterized by the mean squared error (MSE)
• Conducted simulations for the standard GI/M/s multi-server queueing model
• Obtain conditional distribution of the delay given observed HOL

Some simulations:

(Comparison of Efficiency of Different Real-Time Delay Estimators for GI/M/100 Queue as a Function of Traffic Intensity and Interarrival-Time Distribution)

(Efficiency of Different Real-Time Delay Estimators Conditional on Level of Delay Experienced for M/M/100 Model as a Function of Traffic Intensity)

(Evaluation of MSE Approximations for Estimators in Steady State with theorems and Simulation Estimates of First Two Moments of Conditional Delay)

(Evaluation of Approximations for Steady-State MSE of HOL by Comparing to Simulation Estimates of ASE for LES in GI/M/100 Model as a Function of Interarrival-Time Distribution and Traffic Intensity)

(Comparing Approximations for Expectations & Variance of WHOL of for Fixed w with Simulation Estimates of Mean and Variance of HOL, LES, and RCS Estimators in GI/M/100 Model with traffic intensity = 0.95 as a Function of Interarrival-Time Distribution)

Review on the GI/M/s model

(The service times are independent and identically distributed (i.i.d.) exponential random variables Vn with mean 1. The interarrival times are i.i.d. positive random variables Un with a nonlattice cumulative distribution function (cdf) F. The GI/M/s system is well known to be stable, and have a proper limiting steady-state behavior, if and only if . All our simulation results are for the GI/M/s model in steady state, even though the estimation procedures apply more generally.)

Motivations

Advantages of QL Estimator:

Whenever the actual system is well modeled by a GI/M/s queueing model and the system state is known accurately at each time

Real service systems are rarely simple as GI/M/s queueing model:

1. Service time nonexponential (call centers, Brown et al. (2005).)
2. # of servers and mean service time changes (when servers are humans)
3. QL may not be directly observable (ticket queues where each ticket is numbered but customer abandonments are not observable, Xu et al. (2007).)

QL typically known but the rate customers enter service is often not known and/or difficult to estimate reliably:

1. Multiple customer classes, multiple service pools, some skill-based routing (Gans et al. (2003))
2. Server serve several customers simultaneously, or different servers participate in a single service, or interruptions in the service times.
3. Delays are large, abandonment from customers.

Relations with Related Literature

Armony et al. (2009):

Customer response & balking or customer abandonment, while our study doesn』t consider these.

Avramidis et al. (2004), Brown, et al. (2005), and Glynn and Whitt (1989) :

Also doing statistical inference for queues, but aims to estimate the model or the steady-state performance

Coates et al. (2002):

delay estimation, related to the Internet with different setting and time scales

Ward and Whitt (2000) and Nakibly (2002):

delay estimation for real-time delay prediction (focus on processor sharing and priority disciplines, respectively)

Doytchinov et al. (2001) and references therein:

the real-time focus in this study is inspired by their real-time queueing

Others:

QL estimator can be revised to provide an accurate estimate of delays with abandonments when the time-to-abandon distribution is exponential. (Whitt (1999))

Then the time-to-abandon distribution has been found to be nonexponential in practice. (Brown et al. (2005))

The performance measures in the overloaded M/M/s + GI model, with nonexponential time-to-abandon distribution, depend strongly on the time-to-abandon distribution beyond its mean. (Whitt (2006))

Alternative delay estimators in the presence of abandonments in a sequel to Brown et al. (2005), gave examples with nonexponential distributions in which both the standard QL estimator and the refinement for the M/M/s + M model are outperformed by delay estimators based on recent delay history (Ibrahim and Whitt (2008)).

Estimators:

• Direct estimator(of the delay encountered by the new arrival): observed delay

• Refined estimator(based on the same information): mean of the conditional distribution of the delay given that observed delay (conditional mean is complicated, hence develop approximations for it)

No-Information (NI) Steady-State Estimator

Full-Information QL Delay Estimator (QL)

Last Customer to Enter Service (LES)

Head of the Line (HOL) Estimator

Delay of the Last Customer to Complete Service (LCS)

Delay of the Most Recent Arrival to Complete Service (RCS)

Among the Last c√s Customers to Complete Service (RCS-c√s)

Note:

• Our main estimators are individual delays experienced by a recent customer, rather than an average over many past delays (only NI can be said to use averages)

• We can extend the LES, LCS, RCS, and RCS-c√s estimators to get LES-k, LCS-k, RCS-k, and RCS-c√s?k by averaging over the last k experienced delays.

• The exception of LCS with large s (which does not have desirable properties), averages do not help when the delays are relatively large (delays change relatively slowly compared to the size of the delays, can be explained by the HT snapshot principle)

• In the Heave Traffic snapshot principle settings, it is better to use recent information than to eliminate noise by averaging.

This Study

1. LES and HOL delay estimators are very similar, with both being more accurate than the others based on delay history, but less accurate than the full-information QL estimator. (MSEs of the delay-history estimators are about the same as the MSE of the QL estimator when the arrival process variability is low, but considerably greater when the arrival-process variability is high)
2. RCS is far superior to the delay of the LCS for large s (caused by issues in order)
3. LCS outperformed by the NI estimator for large s & low traffic intensities
4. RCS should only be preferred to HOL and LES if delay information is not available until after customers complete service (but the MSE is not much greater for RCS than for LES and HOL).

Further Directions

Main source of estimation uncertainty: the remaining service times & arrival-process variability

More reliable estimation:

Able to better predict the remaining service times

• Certainly possible if the service times are actively controlled
• Possible to some extent if either the service-time distribution is nonexponential or if it is possible to classify the customers.

Develop more sophisticated estimators that exploit much more of the information.

推薦閱讀：