Optimal control of a deterministic multiclass queuing system for which several queues can be served simultaneously. (English) Zbl 1222.49042
Summary: We consider the optimal control problem of emptying a deterministic single server multiclass queuing system without arrivals. We assume that the server is able to serve several queues simultaneously, each at its own rate, independent of the number of queues being served.We show that the optimal sequence of modes is ordered by the rate of cost decrease. However, queues are not necessarily emptied. We propose a dynamic programming approach for solving the problem, which reduces the multi-parametric QP (mpQP) to a series of problems that can be solved readily.
MSC:
| 49L20 | Dynamic programming in optimal control and differential games |
| 90B22 | Queues and service in operations research |
Software:
MPTReferences:
| [1] | Baras, J.; Ma, D.-J.; Makowski, A., \(K\) competing queues with geometric service requirements and linear costs: the \(\mu c\)-rule is always optimal, Systems and Control Letters, 6, 173-180 (1985) · Zbl 0568.60090 |
| [2] | Baras, J.; Ma, D.-J.; Makowski, A., Two competing queues with linear costs and geometric service requirements: the \(\mu c\)-rule is often optimal, Advances in Applied Probability, 17, 186-209 (1985) · Zbl 0554.60087 |
| [3] | Buyukkoc, C.; Varaiya, P.; Walrand, J., The \(\mu c\)-rule revisited, Advances in Applied Probability, 17, 237-238 (1985) · Zbl 0557.60082 |
| [4] | Nain, P.; Tsoucas, P.; Walrand, J., Interchange arguments in stochastic scheduling, Journal of Applied Probability, 27, 815-826 (1989) · Zbl 0689.90030 |
| [5] | Bemporad, A.; Morari, M.; Dua, V.; Pistikopoulos, E., The explicit linear-quadratic regulator for constrained systems, Automatic, 38, 1, 3-20 (2002) · Zbl 0999.93018 |
| [6] | P. Tøndel, T. Johansen, A. Bemporad, An algorithm for multi-parametric quadratic programming and explicit MPC solutions, in: Proceedings of the 40th IEEE Conference on Decision and Control, Orlando, Florida, USA, 2001, pp. 1199-1204.; P. Tøndel, T. Johansen, A. Bemporad, An algorithm for multi-parametric quadratic programming and explicit MPC solutions, in: Proceedings of the 40th IEEE Conference on Decision and Control, Orlando, Florida, USA, 2001, pp. 1199-1204. · Zbl 1019.93019 |
| [7] | M. Kvasnica, P. Grieder, M. Baotić, Multi-Parametric Toolbox (MPT) (2004) URL: http://control.ee.ethz.ch/ mpt/; M. Kvasnica, P. Grieder, M. Baotić, Multi-Parametric Toolbox (MPT) (2004) URL: http://control.ee.ethz.ch/ mpt/ |
| [8] | Weiss, G., A simplex based algorithm to solve separated continuous linear programs, Mathematical Programming, 115, 1, 151-198 (2008) · Zbl 1165.90011 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
