OPTIMAL ROUTING AND JOCKEYING IN A TWO-STATION QUEUE

摘要

This paper studies the optimal routing and jockeying policies in a two-station parallel queueing system. It is assumed that jobs arrive to the system in a Poisson stream with rate λ and are routed to one of the two parallel stations. Each station has a single server and a buffer of infinite capacity. The service times are exponential with server-dependent rates, μ_1 and μ_2. Jockeying between stations is permitted. The jockeying cost is c_(ij) when a job in station i jockeys to station j, i≠ j. There is no cost for a new job to join either station. The holding cost in station j is h_j, h_1 ≤ h_2, per job per unit time. We characterize the structure of the dynamic routing and jockeying policies that minimize the expected total (holding plus jockeying) cost, for both the discounted and the long-run average cost criteria. We show that the optimal routing and jockeying controls are described by three monotonically nondecreasing functions. We study the properties of these control functions, their relationships, and their asymptotic behaviors. We show that some well-known queueing control models, such as optimal routing to symmetric and asymmetric queues, preemptive or nonpreemptive scheduling on homogeneous or heterogeneous servers, are special cases of our system.