Adaptive control of service in queueing systems. (English) Zbl 0534.90037

The authors consider the combined problem of parameter estimation and of optimal control of the service rate in an M/G/1 queueing system with unknown (but constant) arrival rate \(\lambda\) and with general cost structure. An optimal adaptive policy is determined using recently developed results on parameter estimation and adaptive control of semi- Markov processes. The authors show that under some general conditions the optimal adaptive control scheme is as following: (i) determine an optimal stationary policy (OSP) for the average cost problem for each value of the parameter \(\lambda\), (ii) at each decision point \(T_ n\) (assumed to be given), get a strong consistent estimate \(\lambda_ n\) of the true parameter value, (iii) define the adaptive policy as the value of OSP, obtained in step (i), in point \(\lambda =\lambda_ n\) at each decision moment \(T_ n\).
Reviewer: N.V.Kartasov


90B22 Queues and service in operations research
90C40 Markov and semi-Markov decision processes
60K25 Queueing theory (aspects of probability theory)
Full Text: DOI


[1] Basawa, I.V.; Prabhu, N.U., Estimation in single server queues, Naval res. log. quart., 28, 475-487, (1981) · Zbl 0468.60092
[2] Bertsekas, D., Dynamic programming and stochastic control, (1976), Academic Press New York · Zbl 0549.93064
[3] Cinlar, E., Introduction to stochastic processes, (1975), Prentice-Hall Englewood Cliffs · Zbl 0341.60019
[4] Cohen, J.W., On the optimal switching level for an M/G/1 queueing system, Stoch. process appl., 4, 297-316, (1976) · Zbl 0339.60085
[5] Doshi, B.T., Optimal control of the service rate in an M/G/1 queueing system, Adv. appl. probab., 10, 682-701, (1978) · Zbl 0381.60086
[6] Federgruen, A.; Hordijk, A.; Tijms, H.C., Denumerable state semi-Markov decision processes with unbounded costs, average cost criterion, Stoch. process. appl., 9, 223-235, (1979) · Zbl 0422.90084
[7] Gallisch, E., On monotone optimal policies in a queueing model of M/G/1 type with controllable service time distribution, Adv. appl. probab., 11, 870-887, (1979) · Zbl 0434.60095
[8] Georgin, J.P., Estimation et controle des chaines de Markov sur des espaces arbitraires, (), 71-113 · Zbl 0372.60094
[9] Hernandez-Lerma, O.; Marcus, S.I., Adaptive policies for average cost semi-Markov decision processes with unknown parameters, () · Zbl 0585.90090
[10] O. Hernandez-Lerma and S.I. Marcus, Optimal adaptive control of priority assignment in queueing systems. Submitted for publication. · Zbl 0529.90045
[11] Kolonko, M., Strongly consistent estimation in a controlled Markov renewal model, J. appl. probab., 19, 532-545, (1982) · Zbl 0489.90078
[12] W. Lin and P.R. Kumar, Optimal control of a queueing system with two heterogeneous servers, Preprint. · Zbl 0546.90035
[13] Mandl, P., Estimation and control of Markov chains, Adv. appl. probab., 6, 40-60, (1974) · Zbl 0281.60070
[14] Mitchell, B., Optimal service-rate selection in an M/G/1 queue, SIAM J. appl. math., 24, 19-35, (1973) · Zbl 0233.60081
[15] Ross, S.M., Average cost semi-Markov decision processes, J. appl. probab., 7, 649-656, (1970) · Zbl 0204.51704
[16] Schäl, M., On the M/G/1-queue with controlled service rate, (), 233-239
[17] Sobel, M.J., Optimal operation of queues, Lecture notes in econom. math. syst., 98, 231-261, (1974)
[18] Striebel, C., Optimal control of discrete time systems, () · Zbl 0137.35802
[19] Wittenmark, B., Stochastic adaptive control methods: a survey, Internat. J. control, 21, 705-730, (1975) · Zbl 0303.93055
[20] Mandl, P., On the adaptive control of countable Markov chains, () · Zbl 0439.60069
[21] Kolonko, M., The average-optimal adaptive control of a Markov renewal model in presence of an unknown parameter, Math. operationsforsch. statist., 13, 567-591, (1982) · Zbl 0518.90092
[22] Kolonko, M.; Schäl, M., Optimal control of semi-Markov chains under uncertainty with applications to queueing models, (), 430-435 · Zbl 0435.90107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.