New Paper: Approximating Sojourn Times

Yet another announcement today!  (I am atoning for months of ignoring my blog.)  My former student Hyun Ho Kim and I are pleased to announce the publication of “An Approximation Model for Sojourn Time Distributions in Acyclic Multi-Server Queueing Networks” in Computers & Operations Research.

Queueing networks have been an attractive method of modeling complex manufacturing and other systems for many decades. Much of this work is limited in that it develops means for performance measures of interest rather than distributions, or it assumes exponential arrival or service processes. Our paper describes a mathematical model that produces a distribution for the sojourn time (total time in the system, including delays and processing), in the presence of general distributions for service processes.

Results of the model
Results of the model. On the left is the probability density function; on the right, the cumulative distribution function. From the plot on the right, an order has approximately 80% chance of being processed in less than 10 time units.

Here’s an example of how this research might be used in practice: Suppose you are interested in determining a cutoff time for accepting orders in an order fulfillment system, before which you guarantee the order will make it onto the last truck leaving in the evening. You have collected data on all the relevant order processing times—picking, transport to packing, packing, transport to shipping, and shipping. These data, of course, are variable, and you would like to assess the risk of setting a particular cutoff time in light of all this variability.

The model we develop in this paper takes the means and variances of all the relevant processing times and combines them to produce a distribution for the sojourn time of an order, so that you can make statements such as, “orders can be fulfilled within 2 hours with 98 percent probability,” or “orders can be fulfilled within 1 hour with 90 percent probability.” These values can then be used to determine an “optimal” cutoff time, such that the expected benefit of getting the order on the truck (revenue from premium shipping) just exceeds the cost of missing the truck (perhaps offering free shipping because the promise wasn’t kept). The tradeoff is “newsvendor like.”

Technical AbstractWe develop an approximation model for the sojourn time distribution of customers or jobs arriving to an acyclic multi-server queueing network. The model accepts general interarrival times and general service times, and is based on the characteristics of phase-type distributions. The model produces excellent results for multi-server networks with a small to medium number of workstations, but is less accurate when the number of workstations is large.

If you would like a copy of the paper, please email me.

1 Comment

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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