Abstract
In this paper we introduce the notion of regular ordering for periodic sequences based on the gaps between the entries. We define the notion of regular preserving functions using Schur convexity. This is used to extend some optimization results in queuing control problems. In particular, we show that the maximal traveling time in a stochastic event graph as well as the transmission times in a channel with redundancy, decrease (in the stochastic sense) when the input sequence becomes more regular.
Similar content being viewed by others
References
Altman, E., Gaujal, B., and Hordijk, A. 1997a. Admission control in stochastic event graphs. Technical Report 3179, INRIA.
Altman, E., Gaujal, B., and Hordijk, A. 1997b. Balanced sequences and optimal routing. Technical Report 3180, INRIA.
Altman, E., Gaujal, B., and Hordijk, A. 1997c. Multimodularity, convexity and optimization properties. Technical Report 3181, INRIA.
Altman, E., Gaujal, B., and Hordijk, A. 1997d. Optimal open-loop control of vacations, polling and service assignment. Technical Report 3261, INRIA.
Altman, E., Gaujal, B., Hordijk, A., and Koole, G. Optimal admission, routing and service assignment control: the case of single buffer queues. In CDC, Tampa Bay, Fl., Dec. 1998. IEEE.
Baccelli, F. 1992. Ergodic theory of stochastic Petri networks. Annals of Probability 20(1): 375–396.
Baccelli, F., Gohen, G., Olsder, G. J., and Quadrat, J. P. 1992. Synchronization and Linearity. Wiley.
Bartroli, M., and Stidham, S. Jr. 1987. Towards a unified theory of structure of optimal policies for control of network of queues. Technical report, Department of Operations Research, University of North Carolina, Chapel Hill.
Baryshnikov, Y. 1995. Complexity of trajectories in rectangular billiards. Commun. Math. Phys. 174: 43–56.
Berstel, J. 1986. The book of L, chapter Fibonacci words—A survey. Springer Verlag.
Berstel, J. 1990. Mots, chapter Tracé de droites, fractions continues et morphismes itérés. Hermes, Paris.
Bhulai, S. 1998. Optimal routing problems and multimodularity. Master's thesis, Vrije Universiteit, Amsterdam.
Borst, S., and Kamakrishnan, K. G. 1998. Optimization of template-driven scheduling mechanisms. J. of Discrete Event Dynamics Systems.
Combé, M. B., and Boxma, O. 1994. Optimization of static traffic allocation policies. Theoretical Computer Science 125: 17–43.
Gaujal, B. Optimal allocation sequences of two processes sharing a resource. Journal of Discrete Event Dynamic Systems 7: 327–354.
Gaujal, B., and Hyon, E. 2000. Optimal routing policy in two deterministic queues. Calculateurs Parallèles, accepted for publication, also available as INRIA RR-3997.
Glasserman, P., and Yao, D. D. 1994. Monotone optimal control of permutable gsmps. Mathematics of Operation Research 19: 449–476.
Graham, R. 1973. Covering the positive integers by disjoint sets of the form {[nα + β]: n = 1,2,....J. Combi. Theory 15: 354–358.
Hajek, B. 1984. Optimal control of two interacting service stations. IEEE Trans. Aut. Cont. 29: 491–499.
Hajek, B. 1985. Extremal splitting of point processes. Mathematics of Operation Research 10: 543–556.
Van Der Laan, D. 2000. Routing jobs to servers with deterministic distinct service times. Technical report, Leiden University.
Marshall, A. W., and Olkin, I. 1979. Inequalities: Theory of Majorization and Its Applications, volume 143 of Mathematics in Science and Engineering. Academic Press.
Morse, M., and Hedlund, G. A. 1940. Symbolic dynamics II-Sturmian trajectories. American Journal Math. 62: 287–306.
Senechal, M. 1995. Quasicrystals and geometry. Cambridge University Press.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Altman, E., Gaujal, B. & Hordijk, A. Regular Ordering and Applications in Control Policies. Discrete Event Dynamic Systems 12, 187–210 (2002). https://doi.org/10.1023/A:1014527021197
Issue Date:
DOI: https://doi.org/10.1023/A:1014527021197