Iterative Algorithm for Threshold Calculation in the Problem of Routing Fixed Size Jobs to Two Parallel Servers
DOI:
https://doi.org/10.26636/jtit.2015.3.965Keywords:
continuous MDP, discretization, job allocation, optimal policy, thresholdAbstract
At present, solutions of many practical problems require significant computational resources and systems (grids, clouds, clusters etc.), which provide appropriate means are constantly evolving. The capability of the systems to fulfil quality of service requirements pose new challenges for the developers. One of the well-known approaches to increase system performance is the use of optimal scheduling (dispatching) policies. In this paper the special case of the general problem of finding optimal allocation policy in the heterogeneous n-server system processing fixed size jobs is considered. There are two servers working independently at constant but different speeds. Each of them has a dedicated queue (of infinite capacity) in front of it. Jobs of equal size arrive at the system. Inter-arrival times are i.i.d. random variables with general distribution with finite mean. Each job upon arrival must be immediately dispatched to one of the two queues wherefrom it will be served in FCFS manner (no pre-emption). The objective is the minimization of mean job sojourn time in the system. It is known that under this objective the optimal policy is of threshold type. The authors propose scalable fast iterative non-simulation algorithm for approximate calculation of the policy parameter (threshold). Numerical results are given.
Downloads
References
[1] M. E. Crovella, M. Harchol-Balter, and C. D. Murta, “Task assignment in a distributed system: Improving performance by unbalancing load”, in Proc. of Joint Int. Conf. on Measur. and Model. of Comp. Syst. SIGMETRICS’98/PERFORMANCE ’98, Madison, Wisconsin, USA, 1998, pp. 268–269.
View in Google Scholar
[2] M. Harchol-Balter, M. E. Crovella, and C. D. Murta, “On choosing a task assignment policy for a distributed server system”, J. of Parallel and Distrib. Comput., vol. 59, pp. 204–228, 1999.
View in Google Scholar
[3] S. Bhulai, “On the value function of the M/Cox(r)/1 queue”, J. of Appl. Probab., vol. 43, no. 2, pp. 363–376, 2006.
View in Google Scholar
[4] E. Hyytiä, J. Virtamo, S. Aalto, and A. Penttinen, “M/M/1-PS queue and size-aware task assignment”, Perform. Eval., vol. 68, no. 11, pp. 1136–1148, 2011.
View in Google Scholar
[5] E. Hyytiä, A. Penttinen, and S. Aalto, “Size- and state-aware dispatching problem with queue-specific job sizes”, Eur. J. of Oper. Res., vol. 217, no. 2, pp. 357–370, 2012.
View in Google Scholar
[6] E. Hyytiä, S. Aalto, and A. Penttinen, “Minimizing slowdown in heterogeneous size-aware dispatching systems”, in Proc. of the 12th ACM SIGMETRICS/Performance Conf. Measur. Model. Comp. Syst., London, UK, 2012, Eval. Rev., vol. 40, pp. 29–40, 2012.
View in Google Scholar
[7] J. Kołodziej and F. Xhafa, “Enhancing the genetic-based scheduling in computational grids by a structured hierarchical population”, Future Gener. Comp. Syst., vol. 27, no. 8, pp. 1035–1046, 2011.
View in Google Scholar
[8] K. R. Krishnan and T. J. Ott, “State-dependent routing for telephone traffic: Theory and results”, in Proc. 25th IEEE Conf. on Decision and Control, Athens, Greece, 1986, vol. 25, pp. 2124–2128.
View in Google Scholar
[9] M. G. Konovalov, “About one task of overload control”, Informatics and its Applications, vol. 7, no. 4, pp. 34–43, 2013 (in Russian).
View in Google Scholar
[10] E. Hyytiä, “Lookahead actions in dispatching to parallel queues”, Perform. Eval., vol. 70, no. 10, pp. 859–872, 2013.
View in Google Scholar
[11] E. Hyytiä, “Optimal routing of fixed size jobs to two parallel servers”, INFOR: Inform. Syst. and Oper. Res., vol. 51, no. 4, pp. 215–224, 2013.
View in Google Scholar
[12] R. L. Larsen, “Control of multiple exponential servers with application to computer systems”, Ph.D. thesis, University of Maryland at College Park, College Park, MD, USA, 1981.
View in Google Scholar
[13] K. R. Krishnan, “Markov decision algorithms for dynamic routing”, IEEE Commun. Mag., vol. 28, no. 10, pp. 66–69, 1990.
View in Google Scholar
[14] J. van Leeuwaarden, S. Aalto, and J. Virtamo, “Load balancing in cellular networks using first policy iteration”, Tech. Rep., Networking Laboratory, Helsinki University of Technology, 2001.
View in Google Scholar
[15] K. R. Krishnan, “Joining the right queue: a state-dependent decision rule”, IEEE Trans. on Autom. Contr., vol. 35, no. 1, pp. 104–108, 1990.
View in Google Scholar
[16] S. A. E. Sassen, H. C. Tijms, and R. D. Nobel, “A heuristic rule for routing customers to parallel servers”, Statistica Neerlandica, vol. 51, no. 1, pp. 107–121, 1997.
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2015 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
