Iterative Algorithm for Threshold Calculation in the Problem of Routing Fixed Size Jobs to Two Parallel Servers

• Autorzy: Konovalov M. , Razumchik R.
• Języki publikacji: EN

Abstrakty

EN

At present, solutions of many practical problems require signicant computational resources and systems (grids, clouds, clusters etc.), which provide appropriate means are constantly evolving. The capability of the systems to full 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 nding optimal allocation policy in the heterogeneous n-server system processing xed size jobs is considered. There are two servers working independently at constant but di erent speeds. Each of them has a dedicated queue (of innite 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 nite 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.

Słowa kluczowe

EN

continuous MDP; discretization; job allocation; optimal policy; threshold

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2015
• Tom: nr 3
• Strony: 32--38
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Konovalov M.

• Institute of Informatics Problems, Federal Research Center “Computer Science and Control", Russian Academy of Sciences, Vavilova st 44-2, 119333 Moscow, Russia

autor

Razumchik R.

• Institute of Informatics Problems, Federal Research Center “Computer Science and Control", Russian Academy of Sciences, Vavilova st 44-2, 119333 Moscow, Russia

Bibliografia

• [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.
• [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.
• [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.
• [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.
• [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.
• [6] E. Hyytiä, S. Aalto, and A. Penttinen, “Minimizing slowdown in heterogeneous size-aware dis-patching 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.
• [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.
• [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.
• [9] M. G. Konovalov, “About one task of overload control", Informatics and its Applications, vol. 7, no. 4, pp. 34-43, 2013 (in Russian).
• [10] E. Hyytiä, “Lookahead actions in dispatching to parallel queues", Perform. Eval., vol. 70, no. 10, pp. 859-872, 2013.
• [11] E. Hyytiä, “Optimal routing of _xed size jobs to two parallel servers", INFOR: Inform. Syst. and Oper. Res., vol. 51, no. 4, pp. 215-224, 2013.
• [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.
• [13] K. R. Krishnan, “Markov decision algorithms for dynamic routing", IEEE Commun. Mag., vol. 28, no. 10, pp. 66-69, 1990.
• [14] J. Leeuwaarden, S. Aalto, and J. Virtamo, “Load balancing in cellular networks using first policy iteration", Tech. Rep., Networking Laboratory, Helsinki University of Technology, 2001.
• [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.
• [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.