nach oben

Queueing Systems

Erschienen in:

01.02.2013

Analysis of transient queues with semidefinite optimization

verfasst von: Takayuki Osogami, Rudy Raymond

Erschienen in: Queueing Systems | Ausgabe 2/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We derive upper bounds on the tail distribution of the transient waiting time in the GI/GI/1 queue, given a truncated sequence of the moments of the service time and that of the interarrival time. Our upper bound is given as the objective value of the optimal solution to a semidefinite program (SDP) and can be calculated numerically by solving the SDP. We also derive the upper bounds in closed form for the case when only the first two moments of the service time and those of the interarrival time are given. The upper bounds in closed form are constructed by formulating the dual problem associated with the SDP. Specifically, we obtain the objective value of a feasible solution of the dual problem in closed from, which turns out to be the upper bound that we derive. In addition, we study bounds on the maximum waiting time in the first busy period.

Vorheriger Artikel Fluid models of many-server queues with abandonment

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Altman, E.: Constrained Markov Decision Processes. Chapman & Hall/CRC, London (1999)

Ansell, P.S., Glazebrook, K.D., Mitrani, I., Niño-Mora, J.: A semidefinite programming approach to the optimal control of a single server queueing system with imposed second moment constraints. J. Oper. Res. Soc. 50, 765–773 (1999)

Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. Philadelphia, SIAM (2001) CrossRef

Bertsimas, D., Natarajan, K.: A semidefinite optimization approach to the steady-state analysis of queueing systems. Queueing Syst. 56, 27–39 (2007) CrossRef

Bertsimas, D., Niño-Mora, J.: Optimization of multiclass queueing networks with changeover times via the achievable region approach: Part I, the single-station case. Math. Oper. Res. 24, 306–330 (1999) CrossRef

Bertsimas, D., Niño-Mora, J.: Optimization of multiclass queueing networks with changeover times via the achievable region approach: Part II, the multi-station case. Math. Oper. Res. 24, 331–361 (1999) CrossRef

Bertsimas, D., Popescu, I.: Optimal inequalities in probability theory: a convex optimization approach. SIAM J. Optim. 15, 780–804 (2005) CrossRef

Daley, D.J.: Inequalities for moments of tails of random variables, with a queueing application. Z. Wahrscheinlichkeitstheor. Verw. Geb. 41, 139–143 (1977) CrossRef

Gallager, R.G.: Discrete Stochastic Processes. Kluwer Academic, Dordrecht (1995)

10.

Helmes, K.: Numerical methods for optimal stopping using linear and non-linear programming. Lect. Notes Control Inf. Sci. 280, 185–203 (2002) CrossRef

11.

Helmes, K., Rohl, S., Stockbridge, R.H.: Computing moments of the exit time distribution for Markov processes by linear programming. Oper. Res. 49, 516–530 (2001) CrossRef

12.

Kingman, J.F.C.: Some inequalities for the GI/GI/1 queue. Biometrika 49, 315–324 (1962)

13.

Kleinrock, L.: Queueing Systems, vol. 2: Computer Applications. Wiley-Interscience, New York (1976)

14.

Kobayashi, H., Mark, B.L.: System Modeling and Analysis: Foundations of System Performance Evaluation. Prentice Hall, New York (2008)

15.

Lanckriet, G.R.G., Cristianini, N., Bartlett, P., Ghaoui, L.E., Jordan, M.I.: Learning the kernel matrix with semidefinite programming. J. Mach. Learn. Res. 5, 27–72 (2004)

16.

Lasserre, J.B., Prieto-Rumeau, T.: SDP vs. LP relaxations for the moment approach in some performance evaluation problems. Stoch. Models 20, 439–456 (2004) CrossRef

17.

Lasserre, J.B., Prieto-Rumeau, T., Zervos, M.: Pricing a class of exotic options via moments and SDP relaxations. Math. Finance 16, 469–494 (2006) CrossRef

18.

Liu, Z., Nain, P., Towsley, D.: Exponential bounds with an application to call admission. J. ACM 44, 366–394 (1997) CrossRef

19.

Nakata, M.: A numerical evaluation of highly accurate multiple-precision arithmetic version of semidefinite programming solver: SDPA-GMP, -QD and -DD. In: Proceedings of 2010 IEEE Multi-Conference on Systems and Control, pp. 29–34 (2010)

20.

Osogami, T., Raymond, R.: Semidefinite optimization for analysis of queues in closed forms. Technical Report RT0896, IBM Research–Tokyo, March (2010). http://www.research.ibm.com/trl/people/osogami/paper/RT0896.pdf

21.

Osogami, T., Raymond, R.: Simple bounds for a transient queue. In: Proceedings of the 41st Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2011), pp. 562–573 (2011) CrossRef

22.

Rengarajan, B., Caramanis, C., de Veciana, G.: Analyzing queuing systems with coupled processors through semidefinite programming. Unpublished (2008)

23.

Yamashita, M., Fujisawa, K., Fukuda, M., Kobayashi, K., Nakta, K., Nakata, M.: Latest developments in the SDPA family for solving large-scale SDPs. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook on Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications, pp. 687–714. Springer, New York (2011). Chap. 24

Titel: Analysis of transient queues with semidefinite optimization
verfasst von: Takayuki Osogami
Rudy Raymond
Publikationsdatum: 01.02.2013
Verlag: Springer US
Erschienen in: Queueing Systems / Ausgabe 2/2013
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI: https://doi.org/10.1007/s11134-012-9309-7