Thread: Queuing question: I think non-preemptive probabilities?

Hi guys,

I've grabbed a queuing question from my operations research textbook (by W. Winston) which I am really struggling with and unfortunately haven't got a solutions manual for. Would really appreciate help in identifying what type of queue it is. I'm leaning towards M/M/2/NPRP/c/infinity, but we didn't cover those at university yet this question has been listed on the review sheet.

Anyway, here is the question:

Smalltown has 2 ambulances. Ambulance 1 is based at the local college, and ambulance 2 is based downtown. If a request for an ambulance comes from the local college, the college-based ambulance is sent if it is available. Otherwise, the downtown-based ambulance is sent (if available). If no ambulance is available, the call is assumed to be lost to the system. If a request for an ambulance comes from anywhere else in the town, the downtown based ambulance is sent if it is available. Otherwise, the college-based ambulance is sent if available. If no ambulance is available, the call is considered lost to the system. The time between calls is exponentially distributed. An average of 3 calls per hour are received from the rest of the town. The average time (exponentially distributed) it takes an ambulance to respond to a call and be ready to respond to another call is shown below:

Ambulance from College travelling to College: 4 minutes
Ambulance from College travelling to Noncollege: 7 minutes
Ambulance from Downtown travelling to College: 5 minutes
Ambulance from Downtown travelling to Noncollege: 4 minutes

a) What fraction of the time is the downtown ambulance busy?
b) What fraction of the time is the college ambulance busy?
c) What fraction of all calls will be lost to the system?
d) On average, who waits longer for an ambulance, a college student or a town person?

I'm sure I could answer the questions if I could only work out what type of queue I was looking at. The textbook covers both M/G/s/GD/s/inf queues, or the blocked customers cleared type, where people can get lost in the system, and also covers M/M/s/NPRP/inf/inf queues, where there are different probabilities of someone being served, but this would be a mixture of both, right?

Thanks in advance! And sorry for the long post.

Hey PeterPan01.

One question for you: what is NPRP?

I don't really know the notation too well, but the model needs to account for the fact that if the queues are "full" then the call just gets lost and I don't personally remember what that kind of model is.

Ah sorry, my notation is probably a bit confusing, NPRP stands for non-preemptive something something. It just means that different items in the queue have different priorities, but that once you've started serving someone, you can't stop halfway through, e.g. once an ambulance starts travelling towards a customer we're assuming it isn't going to ditch the customer and turn around and go back to another customer instead (that would be a priority queue with preemptive probabilities).

Yeah it does need to account for calls getting lost - that would be a queue with something like M/G/s/GD/s/inf, so the s in the second last spot relates to calls being lost in the system.

So what I'm looking at currently is M/M/2/?/2/inf, where the first M refers to exponential time between arrivals, the second M refers to the exponential service times, the first 2 means 2 ambulances/servers, the second 2 means 2 places in the system (because once both ambulances are used, it gets lost in the system), and the inf at the end means that the data is coming from a large sample, because we get no information about how big the town/colleges are it's safe to assume that it's a largeish sample I guess.

The ? spot relates to the service discipline, so whether the serving pattern is like first in first served, or whether they are served in a random order, or in this case, I really suspect that it's a priority type of queue, because where the ambulance goes depends on where the patient is located, but then I'd be looking at an M/M/2/NPRP/2/inf queue, and the textbook doesn't consider those, but this question is in the chapter review of the textbook, so it would have to be a type of queue that we've considered I guess.

My only alternative seems to be considering the question as like 2 separate queues, one for college people and one for downtown, but again, I would guess that if we didn't cover that in class, it wouldn't be a "review" of the content.

Or perhaps I am wrong and it's not a priority queue after all - another glance at the textbook has indicated that would be more like if a certain type of customers were getting served before others - that's not really what's happening, it's that a certain type of server/ambulance is assigning itself to a certain type of customer (based on location), which is what is baffling me a bit.

I don't think it's a priority queue: If you can guarantee that the customer will get served either way (if the call is not lost) then I think it's just a normal 2 server queue system.

Hmmmm, okay. Any ideas on how I could make it so that one server (Ambulance 1) will serve a certain type of customer (college students) first and the other server will serve downtown people first?

I have a university assignment that is very similar to the original problem posted. Was there ever any progress made here? I am fairly sure it is a priority queuing model, perhaps two parallel priority queues. Its the only way we have covered that allows for preferential selection of next service (i.e. college ambulance takes jobs from college over downtown). But I dont know how to factor in that different servers have different priorities. Which makes me think that modelling as two priority queues is the way to go. But then I'm not sure how to factor in the division of work amongst the two queues (i.e. the state of the college queue is related to the state of the down town queue)

So, I figured out an approach to my problem. Posting here just in case it may come in handy to anyone in the future. I ended up not using a queuing model at all. Instead I took a markovian / birth death process approach to the problem (which is the theory behind a lot of the queuing models anyway). I considered all the states of nature of the system, e.g. (let y->x mean that the ambulance from y assigned to job from x. y in {C, D}, x in {C, D, N} where C = college, D = downtown and N = neither).

state 0: C->N, D->N
state 1: C->C, D->N
state 2: C->N, D->D
etc, etc.

All up you should have nine states. Then construct a rate diagram and attach rates accordingly. e.g. from state 0 you can only go to state 1 or 2 (assuming you are considering one event per time step, which is a law of birth-death processes). You go from state 0 to state 1 at the rate at which College calls come in to the system and you go from state 0 to state 2 at the rate at which downtown calls come into the system.

Then, since number of entraces into state j = number of departures from state j, you can construct a system of equations from your rate diagram, not forgetting the additional equation representing that the sum of your steady state probs = 1. This will give you 10 equations in 9 unknowns and its just lin alg from there. Once you have all your probabilities you just need to sum the appropriate ones for each question. i.e. for % of time college ambulance is busy you sum all steady state probs for states in which the college ambulance is busy.