PROBLEMS OF ADAPTIVE OPTIMIZATION IN MULTICLASS M GI/1 QUEUES WITH BERNOULLI FEEDBACK/

Adaptive algorithms are obtained for the solution of separable optimiz ation problems in multiclass M/GI/1 queues with Bernoulli feedback. Op timality of the algorithms is established by modifying and extending m ethods of stochastic approximation. These algorithms, can be used as a basis for designing policies for semi-separable and approximate lexic ographic optimization problems and in the case of M/GI/1 queues withou t feedback, they also provide a simple policy for lexicographic optimi zation. The results obtained on stochastic approximation imply converg ence of classical recursions such as Robbins-Monroe in cases where the conditional second moment of their increments is not finite.