Asymptotic Optimality of Balanced Routing in a Multiclass G/G/1 Queue
In this paper we consider a multiclass G/G/1 queueing system. When the server is idle, we use a balanced routing control policy to determine what kind of customer is served. Under such a balanced policy, we derive the diffusion limits of the queue length
- PDF / 1,704,288 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 77 Downloads / 145 Views
Abstract In this paper we consider a multiclass G/G/1 queueing system. When the server is idle, we use a balanced routing control policy to determine what kind of customer is served. Under such a balanced policy, we derive the diffusion limits of the queue length processes and the workload processes. The diffusion limits are the same for these processes regardless the choice of c as long as c C 2. We further show that the proposed balanced routing policy for any fixed c C 2 is asymptotically optimal in the sense that it minimizes the workload over all time in the diffusion limit. Keywords G/G/1 queueing system
Balanced routing Asymptotic optimality
1 Introduction We consider a multiclass G/G/1 queueing system. When the server is idle, we use a balanced routing control policy to determine what kind of customer is served. This problem arises in a number of important applications. For example, it can be viewed as a order model of Van Mieghem [1]. It is interesting to think of our system as modeling order fulfillment at a firm which dynamically receives orders from customers for several different types or classes of goods and services. In order not to keep one kind of customer’s orders in the firm for too long, we need to X. Xiao (&) Department of Mathematics, Anhui University of Science and Technology, Huainan 232007, People’s Republic of China e-mail: [email protected] L. Wu Department of Economics, Anhui University of Science and Technology, Huainan 232007, People’s Republic of China e-mail: [email protected]
Z. Yin et al. (eds.), Proceedings of The Eighth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA), 2013, Advances in Intelligent Systems and Computing 212, DOI: 10.1007/978-3-642-37502-6_9, Ó Springer-Verlag Berlin Heidelberg 2013
73
74
X. Xiao and L. Wu
settle the problem of routing control in such a system. The purpose of this paper is to show how the firm should sequence the different orders that are competing for its scarce resources. Load balancing is a canonical method for sharing resources among different customers efficiently. Two versions of the load balancing problem have been studied in the literature: static and dynamic. The static version was first analyzed by Azar et al. [2] using the balls-and-bins model. In this paper, we are interested in the dynamic version, in Vvednskaya et al. [3], a routing policy that is based on the partial queue length information is proposed. The model was also studied by Mitzenmacher [4]. Chen and Ye [5] extends and complements the previous works in several ways. Firstly, based on Mitzenmacher’s, they establish the asymptotic optimality of the balanced routing under more general queueing systems. Secondly, they complements the work of He and Down [6], they rigorously establish the heavy traffic limit theorem for the queueing system under balance routing. Compared to Chen and Ye [5], the distinguishing feature of our analysis is that here we consider a multiclass G/G/1 queueing system. We extend the balanced routing
Data Loading...
