Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-24T06:38:56.064Z Has data issue: false hasContentIssue false
  • English
  • Français

Open-loop routeing to M parallel servers with no buffers

Part of: Stochastic systems and control

Published online by Cambridge University Press:  14 July 2016

Eitan Altman ,
Sandjai Bhulai ,
Bruno Gaujal  and
Arie Hordijk
Eitan Altman*
Affiliation:
INRIA
Sandjai Bhulai*
Affiliation:
Vrije Universiteit Amsterdam
Bruno Gaujal*
Affiliation:
LORIA
Arie Hordijk*
Affiliation:
Leiden University
*
∗Postal address: INRIA B.P. 93, 2004 Route des Lucioles, 06902 Sophia Antipolis Cedex, France. Email address: [email protected]
∗∗Postal address: Vrije Universiteit Amsterdam, De Boelelaan 1081a, 1081 HV Amsterdam, The Netherlands
∗∗∗Postal address: LORIA B.P. 102, 54602 Villers-les-Nancy, France
∗∗∗∗Postal address: Leiden University, 2300 RA Leiden, The Netherlands
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we study the assignment of packets to M parallel heterogeneous servers with no buffers. The controller does not have knowledge on the state of the servers and bases all decisions on the number of time slots ago that packets have been sent to the different servers. The objective of the controller is to minimize the expected average cost. We consider a general stationary arrival process, with no independence assumptions. We show that the problem can be transformed into a Markov Decision Process (MDP). We further show under quite general conditions on cost functions that only a finite number of states have to be considered in this MDP, which then implies the optimality of periodic policies. For the case of two servers we obtain a more detailed structure of the cost and optimal policies. In particular we show that the average cost function is multimodular, and we obtain expressions for the cost for MMPP and MAP processes. Finally we present an application to optimal robot scheduling for Web search engines.

Keywords

Markov decision processesmultimodularityoptimal open-loop controlrouteing

MSC classification

Primary: 93E20: Optimal stochastic control
Secondary: 90C40: Markov and semi-Markov decision processes
Type
Research Papers
Information
Journal of Applied Probability , Volume 37 , Issue 3 , September 2000 , pp. 668 - 684
Copyright
Copyright © Applied Probability Trust 2000 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Altman, E., Bhulai, S., Gaujal, B., and Hordijk, A. (1999). Optimal routing problems and multimodularity. Res. Rept RR–3727, INRIA.Google Scholar
Altman, E., Gaujal, B., and Hordijk, A. (2000). Multimodularity, convexity and optimization properties. Math. Operat. Res. 25, 324–347.Google Scholar
Altman, E., Gaujal, B., and Hordijk, A. (1997). Balanced sequences and optimal routing. J. Assoc. Comput. Mach. 47, 752–775.Google Scholar
Altman, E., Gaujal, B., Hordijk, A., and Koole, G. (1998). Optimal admission, routing and service assignment control: the case of single buffer queues. IEEE Conf. Decision Control, Dec. 1998, Tampa, Florida.Google Scholar
Asmussen, S., and Koole, G. (1993). Marked point processes as limits of Markovian arrival streams. J. Appl. Prob. 30, 365–372.CrossRefGoogle Scholar
Bartroli, M. and Stidham, S. Jr. (1987). Towards a unified theory of structure of optimal policies for control of network of queues. Tech. Rept, Dept of Operations Research, University of North Carolina, Chapel Hill.Google Scholar
Coffman, E. G. Jr., Liu, Z., and Weber, R. R. (1998). Optimal robot scheduling for Web search engines. J. Scheduling 1, 15–19.Google Scholar
Fisher, W., and Meier-Hellstern, K. S. (1992). The Markov-modulated Poisson process (MMPP) cookbook. Perf. Eval. 18, 149–171.Google Scholar
Hajek, B. (1985). Extremal splitting of point processes. Math. Operat. Res. 10, 543–556.Google Scholar
Koole, G. (1999). On the static assignment to parallel servers. IEEE Trans. Automat. Control 44, 1588–1592.Google Scholar
Koole, G. and van der Sluis, E. (1998). An optimal local search procedure for manpower scheduling in call centers. Tech. Rept WS-501, Vrije Universiteit Amsterdam.Google Scholar
Lucantoni, D., Meier-Hellstern, K. S., and Neuts, M. F. (1990). A single-server queue with server vacations and a class of non-renewal arrival processes. Adv. Appl. Prob. 22, 675–705.Google Scholar
Marshall, A. W., and Olkin, I. (1979). Inequalities: Theory of Majorization and its Applications. Academic Press, New York.Google Scholar
Neuts, M. F. (1989). Structured Stochastic Matrices of M/G/1 Type and their Applications. Marcel Dekker, New York.Google Scholar
Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley, New York.Google Scholar