Optimal Server Allocation in Zero-Buffer Tandem Queues

Abstract

<p>We study the server allocation problem for tandem queues in the absence of intermediate buffer space. Servers are assumed to be homogeneous and non-collaborative. We provide policies to maximize the throughput. We break down our work into four stages. First, we assume that all servers are dedicated. We propose an allocation algorithm that assigns servers to stations based on the mean service times and the current number of servers assigned to each station. The algorithm is proposed for stations with exponentially distributed service times, but where the service rate at each station may be different. We further study the impact on the proposed allocation method of including service time distributions with different coecients of variation. Second, we consider tandem queues with both dedicated and flexible servers. We examine policies to dynamically assign flexible servers. When there is one flexible server and two stations each with a dedicated server, we completely characterize the optimal policy. We use the insights gained from applying the Policy Iteration algorithm on systems with three, four, and five stations to devise heuristics for systems of arbitrary size. Third, we study cases where flexibility is constrained such that flexible servers can only service two adjacent stations. We provide optimal policies for tandem queues with three and four stations and compare them with optimal policies for corresponding non-constrained cases. Fourth, we consider two parallel tandem queues with both dedicated servers and vertical flexible servers - servers that can move between corresponding stations of the two tandem queues. The workload allocations are the same for each line and each vertical flexible server moves only between two corresponding stations. We examine policies for dynamic allocation of these vertical flexible servers. When each tandem queue has two stations, each station possesses a dedicated server, and a vertical flexible server exists for each pair of stations, we specify the optimal policy. For cases with more than two stations, heuristic assignments are proposed. We also analyze the throughput improvement gained from adding flexible servers within a tandem queue or between two parallel tandem queues. Numerical results are used to verify the heuristics provided in each of the stages.</p>