Variations of Hypercube Model

The class material  of the last week covered the hypercube queuing model, approximation and some variations. As an extension, I am going talk more about variations of the hypercube model in this post.

exact model and approximation model
These were covered in the class in detail. See Larson(1974) for the exact model. The approximation model treat servers identical to reduce the state space from 2^n to 2n. See Larson(1975).

customer-dependent service rates
Jarvis(1985) provides a procedure for approximating the equilibrium behavior of multi-server loss systems with distinguishable servers and multiple customer types. Instead of using a fixed value of mean service time, the mean service time is approximated at the end of each iteration using weighted sum of dispatch probabilities and customer-dependent service rates. We’ve covered this iterative procedure in the class. But there are exact models with customer-dependent service rates too. Atkinson et al(2008) considers a queuing system describing EMS with distinct geographical zones. Their exact hypercube model has 3^n states, so for computational tractability they propose two heuristic methods and a simulation approach for approximating the steady-state probabilities.

modeling co-located servers and dispatch ties
It is assumed that the servers are dispatched according to a fixed preference dispatching scheme(which is frequent in hypercube family of queuing models). When servers are co-located in the same station, these equally preferred servers generate ties in the dispatch preference lists. In order to break the tie and distribute workload, Burwell et al(1992) use a method called stacking, which is to split the call type with tied preferred servers into multiple copies. This problem of co-located servers is solved in Budge et al(2009) by other approach. They explicitly allows multiple vehicles per station by providing an extended iterative hypercube approximation procedure.

partial backup hypercube queuing model for EMS on highways
Iannoni et al (2007) considers an EMS on highways that only certain servers in the system can service calls in a given region(partial backup). Calls are of different types and the servers are distinct. Multiple(1-3 servers for a call) dispatch is also considered here.

I myself is also studying some kind of variations, which is to apply a hypercube approximation model to analyze cutoff priority queue. In the cutoff priority queue scheme, low priority customers are served only when the system is relatively idle. When the number of busy servers is above ‘cutoff number’, a low priority call is put in a queue(or lost if queue is out of capacity) instead of being served immediately. As a result, the system keeps servers in hand most of the time so that it can better be ready to serve future high priority customers.

Before I finish the post, let me stress that this is NOT a comprehensive summary of all hypercube queuing model variations. There are vast literatures related to hypercube queuing mode, and I am introducing just a small subset of it. So I expect we may share more information as any of us see other interesting variations of hypercube queuing model later.


Atkinson JB, Kovalenko IN, Kuznetsov N, Mykhalevych KV (2008) A hypercube queuing loss model with customer-dependent service rates. Eur. J. Oper. Res.
Budge S, Ingolfsson A, Erkut E (2009) Approximating vehicle dispatch probabilities for emergency service systems with location-specific service times and multiple units per location. Oper. Res.
Burwell TH, Jarvis JP, McKnew MA (1993) Modeling co-located servers and dispatch ties in the hypercube model. Comput. Oper. Res.
Iannoni AP, Morabito R (2007) A multiple dispatch and partial backup hypercube queuing model to analyze emergency medical systems on highways. Transportation Res.
Jarvis JP (1985) Approximating the equilibrium behavior of multi-server loss systems. Management Sci.
Larson RC (1974) A hypercube queuing model for facility location and redistricting in urban emergency services. Comput. Oper. Res.
Larson RC (1975) Approximating the Performance of Urban Emergency Service Systems. Oper. Res.


2 thoughts on “Variations of Hypercube Model

    1. Thank you for the feedback.
      Among the literatures I mentioned above, Iannoni et al (2007) considers distinguishable multiple-type server. Their EMS has six servers located, 5 identical rescue ambulances and 1 medical vehicle. Each server can only be dispatched to their predetermined primary and backup atoms. They also model six different call types that require different kinds of ambulance dispatch: type 1a (1 ambulance), type 1b(1 medical vehicle), type 2a (2 ambulances), type 2b (1 ambulance and 1 medical vehicle), type 3a(3 ambulances), type 3b(2 ambulances and 1 medical vehicle). But they make an assumption that an ambulance can be a backup to the medical vehicle.
      I will follow up as soon as I see other adequate literatures.

      Liked by 1 person

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