Queueing Networks with Limited Flexibility

Abstract

<p>Queueing network models have been widely adopted in the field of complex systems involving service. In this thesis, we study a queueing network model which consists of servers and classes with incoming customers. Customers are served by servers at classes, where a class of a customer is used to indicate the stage of processing. All the servers are flexible to switch their service between classes. Our objective is to choose an efficient assignment of servers to classes that maximizes the capacity of t he given queueing network. By introducing limited flexibility, we restrict the maximum number of servers which can simultaneously work at a particular class and present a problem called the Total Discrete Capacity Constrained Problem (TDCCP). We also extend TDCCP to TDCCP with costs, where a cost is incurred when a server is working at a class.</p> <p>We prove that both TDCCP and TDCCP with costs are NP-complete problems. However, for a special case where all servers are identical, we show that TDCCP and TDCCP with costs can be solved in polynomial time. Then we present approximation algorithms for another special case where all classes are identical. We also give approximation algorithms for solving the general case of TDCCP and TDCCP with costs.</p> <p>Finally, we implement the approximation algorithms for solving TDCCP and TDCCP with costs. Numerical results on several experiments are reported. We compare and analyze the performance of the different algorithms. Several suggestions will be also given for choosing our algorithms and improving the results.</p>