Solution methods for controlled queueing networks
In this dissertation we look at a controlled queueing network where a controller routes the incoming arrivals to parallel queues using state-dependent rules. Besides this general arrival there are dedicated arrivals to each queue. The dedicated arrivals can only be served by their designated server, hence there is no routing decision involved. The goal of the controller is to find a stationary policy that will minimize the average number of customers in the system;The problem is modeled as a semi-Markov decision process and solved using techniques from the theory of Markov decision processes. We develop an efficient policy iteration based methodology which performs better than the value iteration method which is widely thought of as the best method to use for large-scale problems. The novelty in our approach is to use iterative methods in solving the system of linear equations, and also take advantage of the sparsity of matrices. The methodology could be used for other problems that are similar in nature. Using this methodology we solve much larger problems than reported in the literature. We also look at how several heuristic methods perform on our problem. No heuristic method is suitable to use for all instances. In general, however, these heuristic methods offer quick and reasonable solutions to very large problems.