Exploiting Limited Customer Choice and Server Flexibility

Abstract

<p>Flexible queuing systems arise III a variety of applications, such as service operations, computer/communication systems and manufacturing. In such a system, customer types vary in the flexibility of choosing servers; servers vary in the flexibility of which types of customers to serve. This thesis studies several resource allocation policies which address the concerns of limited customer choice and server flexibility. First, to accommodate different levels of flexibility, we propose the MinDrift affinity routing (MARa) policy and three variants: MARO-2/k, MARO-flex and MARa-tree. These policies are designed to maximize the system capacity by using the first moments of the interarrival times and the service times, at the same time they require only a small amount of state information in minimizing the delay in the system. Using diffusion limits for systems with Poisson arrival processes, we prove that MARa, MARO-flex and MARO-tree have the same heavy traffic optimality properties and the optimality is achieved independent of the flexibility levels. By providing their applications in distributed computing systems, we show that the MARa related policies (which require significantly less state information) outperform the MinDrift(Q) policy (which requires global state information), in heterogeneous server systems with either high or medium loads. Second, when no state information is available, we propose both the random routing policy which asymptotically minimizes the delay in the system by using the second moments of the service times, and the pooling strategy which further reduces the delay by combining appropriate parallel single-server queues into a number of multi-server queues. Overall, this thesis intends to provide insights on designing effective policies for allocating servers' times to serve multiple types of customers.</p>