Balanced sequences and optimal routing

被引：47

作者：

Altman, E

Gaujal, B

Hordijk, A

机构：

[1] INRIA, F-06902 Sophia Antipolis, France

[2] LORIA, F-54606 Villers les Nancy, France

[3] Leiden Univ, Dept Math & Comp Sci, NL-2300 RA Leiden, Netherlands

来源：

JOURNAL OF THE ACM | 2000年 / 47卷 / 04期

关键词：

balanced sequences; multimodularity; optimal control; stochastic event graphs;

D O I：

10.1145/347476.347482

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The objective pursued in this paper is two-fold. The first part addresses the fallowing combinatorial problem: is it possible to construct an infinite sequence wet n letters where each letter is distributed as "evenly" as possible and appears with a given rate? The second objective of the gaper is to use this construction in the framework of optimal routing in queuing networks. We show under rather general assumptions that the optimal deterministic routing in stochastic event graphs is such a sequence.

引用

页码：752 / 775

页数：24

共 35 条

[21] On the pathwise optimal bernoulli routing policy for homogeneous parallel servers [J].

Koole, G .

MATHEMATICS OF OPERATIONS RESEARCH, 1996, 21 (02) :469-476

[22]

Liu Z, 1998, OPER RES, V46, P563, DOI 10.1287/opre.46.3.S146

[23]

LOEVE JA, 1995, THESIS LEIDEN U, pCH8

[24]

LOTHAIRE M, 1991, MOTS CHAPTER TRACE D

[25]

MORIKAWA R, 1995, B FACULTY LIBERAL AR

[26]

MORIKAWA R, 1993, B FACULTY LIBERAL AR

[27]

MORSE M, 1940, AM J MATH, V62, P287

[28] ROOTS OF UNITY AND COVERING SETS [J].

NEWMAN, M .

MATHEMATISCHE ANNALEN, 1971, 191 (04) :279-&

[29]

Sinai Y G., 1977, Introduction to Ergodic Theory, Vvol 18

[30] Intertwinings of periodic sequences [J].

Tijdeman, R .

INDAGATIONES MATHEMATICAE-NEW SERIES, 1998, 9 (01) :113-122

← 1 2 3 4 →