The N-Network Model with Upgrades

Mark E. Lewis
Cornell University
School of Operations Research and Information Engineering
226 Rhodes Hall
Ithaca, New York 14853


Douglas G. Down
Department of Computing and Software
McMaster University
1280 Main Street West
Hamilton, ON L8S 4L7, Canada

In this paper we introduce a new method of mitigating the problem of long wait times for low

priority customers in a two-class queueing system. To this end, we allow class 1 customers to

be “upgraded” to class 2 after they have been in queue for some time. We assume there are

ci servers at station i, i = 1, 2. The servers at station 1 are flexible in the sense that they can

work at either station while the servers at station 2 are dedicated. Holding costs at rate hi are

accrued per customer per unit time at station i, i = 1, 2. This study yields several surprising

results. First, we show that stability analysis requires a condition on the order of the service

rates. This is unexpected since no such condition is required when the system does not have

upgrades. This condition continues to play a role when control is considered. We provide

structural results which include a c μ rule when an inequality holds and a threshold policy

when the inequality is reversed. A numerical study verifies that the optimal control policy

significantly reduces holding costs over the policy that assigns the flexible server to station

1. At the same time, in most cases the optimal control policy reduces waiting times of both

customer classes.