Ordinal optimization for a class of deterministic and stochastic discrete resource allocation problems

被引:36
作者
Cassandras, CG [1 ]
Dai, LY
Panayiotou, CG
机构
[1] Boston Univ, Dept Mfg Engn, Boston, MA 02215 USA
[2] Washington Univ, Dept Syst Sci & Math, St Louis, MO 63130 USA
[3] Univ Massachusetts, Dept Elect & Comp Engn, Amherst, MA 01003 USA
基金
美国国家科学基金会;
关键词
discrete-event systems; resource allocation; stochastic optimization;
D O I
10.1109/9.701087
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
The authors consider a class of discrete resource allocation problems which are hard due to the combinatorial explosion of the feasible allocation search space. In addition, if no closed-form expressions are available for the cost function of interest, one needs to evaluate or (for stochastic environments) estimate the cost function through direct online observation or through simulation. For the deterministic version of this class of problems, the authors derive necessary and sufficient conditions for a globally optimal solution and present an online algorithm which they show to yield a global optimum. For the stochastic version, they show that an appropriately modified algorithm, analyzed as a Markov process, converges in probability to the global optimum, An important feature of this algorithm is that it is driven by ordinal estimates of a cost function, i.e., simple comparisons of estimates, rather than their cardinal values. They can therefore exploit the fast convergence properties of ordinal comparisons, as well as eliminate the need for "step size" parameters whose selection is always difficult in optimization schemes. An application to a stochastic discrete resource allocation problem is included, illustrating the main features of their approach.
引用
收藏
页码:881 / 900
页数:20
相关论文
共 20 条
[1]  
Aarts E., 1989, Wiley-Interscience Series in Discrete Mathematics and Optimization
[2]  
[Anonymous], 1988, DISCRETE OPTIMIZATIO
[3]   SCHEDULING POLICIES USING MARKED/PHANTOM SLOT ALGORITHMS [J].
CASSANDRAS, CG ;
JULKA, V .
QUEUEING SYSTEMS, 1995, 20 (1-2) :207-254
[4]  
Cassandras CG, 1996, IEEE DECIS CONTR P, P3332, DOI 10.1109/CDC.1996.573665
[5]  
CASSANDRAS CG, 1994, IEEE DECIS CONTR P, P2639, DOI 10.1109/CDC.1994.411545
[6]  
CASSANDRAS CG, 1993, P 31 ANN ALL C COMM
[7]  
Cassandras Christos., 1993, Discrete Event Systems: Modeling and Performance Analysis
[8]   Convergence properties of ordinal comparison in the simulation of discrete event dynamic systems [J].
Dai, L .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1996, 91 (02) :363-388
[9]   MINIMUM DELAY ROUTING ALGORITHM USING DISTRIBUTED COMPUTATION [J].
GALLAGER, RG .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1977, 25 (01) :73-85
[10]  
GONG WB, 1992, P 31 IEEE C DEC CONT