** Mark E. Lewis
Industrial and Operations Engineering Department
University of Michigan
1205 Beal Avenue
Ann Arbor, MI 48109-2117**

Douglas G. Down

Department of Computing and Software

McMaster University

1280 Main Street West

Hamilton, ON L8S 4L7, Canada

905-525-9140

We consider a system of parallel
queues with dedicated arrival

streams. At each decision epoch a decision-maker can move

customers from one queue to another. The cost for moving customers

consists of a fixed cost and a linear, variable cost dependent on

the number of customers moved. There are also linear holding costs

that may depend on the queue in which customers are stored. Under very

mild assumptions, we develop stability (and instability)

conditions for this system via a fluid model. Under the assumption

of stability, we consider minimizing the long-run average cost. In

the case of two-servers the optimal control policy is shown to

prefer to store customers in the lowest cost queue. When the

inter-arrival and service times are assumed to be exponential, we

use a Markov decision process formulation to show that for a fixed

number of customers in the system, there exists a level $S$ such

that whenever customers are moved from the high cost queue to the

low cost queue, the number of customers moved brings the number of

customers in the low cost queue to $S$. These results lead to the

development of a heuristic for the model with more than two

servers.