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 条

[1] Optimality of monotonic policies for two-action Markovian decision processes, with applications to control of queues with delayed information [J].

Altman, E ;

Stidham, S .

QUEUEING SYSTEMS, 1995, 21 (3-4) :267-291

[2]

ALTMAN E, 1997, 3181 LEID U

[3]

ALTMAN E, 1997, 3179 INRIA LEID U

[4]

ARNOUX P, 1994, B SOC MATH FR, V122, P1

[5] Free-choice Petri nets - An algebraic approach [J].

Baccelli, F ;

Foss, S ;

Gaujal, B .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1996, 41 (12) :1751-1778

[6]

Baccelli F, 1992, SYNCHRONIZATION LINE

[7]

BARNOY A, 1998, P 9 ANN ACM SIAM S D

[8]

BARYSHNIKOV Y, 1995, COMMUN MATH PHYS, V174, P43, DOI 10.1007/BF02099463

[9]

BERSTEL J, 1994, B BELG MATH SOC, V1, P175

[10]

BOEL RK, 1989, P IEEE, P210

← 1 2 3 4 →