Predicting departure times

I have completed a paper with my co-author Hyun Ho Kim entitled “Predicting Departure Times in Multi-Stage Queueing Systems,” which will appear in the journal Computers & Operations Research.

Non-Technical Summary:  This research answers a simple question:  Given that you’ve arrived to a service system (customers to a bank teller, patrons to a ride at Disney World, or orders to an Amazon warehouse) with customers in front of you, what is the probability you will finish service before a deadline (the bank closes, the rides stop, or the FedEx truck leaves)? The answer requires a state-dependent sojourn time distribution, which describes the probability that waiting time in queue plus service time with the server will be less than a particular value, given the number of people in front of you. We show how to calculate that probability.

Slightly Technical Summary:  The paper describes a state-dependent approximation model for sojourn time distributions in multi-stage, multi-server queueing networks in which processing times can take on general distributions. We approximate individual waiting times and service times with phase-type distributions, then convolve them to arrive at a distribution for sojourn time. The model can handle reasonably-sized serial lines (with multiple servers per stage) and even small acyclic queueing networks.

Show me some pictures! The density function (left) and distribution function (right) describe the time to complete service in a 4-station serial line in which each station has multiple workers and different numbers of orders ahead when the order of interest arrives.

Example distributions for a 4-station system. At the time of arrival, the order has 11 customers ahead at the first workstation, and there are 12, 8, and 13 customers in queue at later workstations.

In a small acyclic network, the sojourn time distribution can be complicated due to different possible paths to service completion.  Here, there is a small probability of taking a longer path.

Example distributions for a small acyclic system, in which service time varies depending on which path is taken.

How the model might be used:  Knowing the probability of meeting a deadline can be useful in a number of service settings, such as call centers or order fulfillment systems. The application that motivated this research was a large distribution center that attempts to ship as many packages as possible via next-day service. The operations manager wants to know at what time he should “give up” on newly arriving orders and shift his workforce to make sure orders already in the system will make the truck. Our model could be used to derive a “probability of success” for any order, at any time. For call centers, the model could be used to give callers an expectation of how long they will have to wait. Rather than providing a mean time, which leads to disappointment about half the time, the call center could say that expected time is t, where the probability of service time being less than t is 80 percent. Remember: Service = Perception – Expectation!

For more details on the research please download the paper.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s