Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Queueing Systems
Erschienen in: Queueing Systems 1-2/2022

04.04.2022

Fluid limits for shortest job first with aging

verfasst von: Yonatan Shadmi

Erschienen in: Queueing Systems | Ausgabe 1-2/2022

Einloggen

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

search-config
loading …

Abstract

We investigate fluid scaling of single-server queues operating under a version of shortest job first (SJF) where the priority level undergoes aging. That is, a job’s priority level is initialized by its size and varies smoothly in time according to an ordinary differential equation. Linear and exponential aging rules are special cases of this model. This policy can be regarded as an interpolation between FIFO and SJF. We use the measure-valued Skorokhod map to characterize the fluid model and establish convergence under fluid scale. We treat in detail examples of linear and exponential aging rules and provide a performance criterion based on our main result.
Vorheriger Artikel Instability of SRPT, SERPT and SJF multiclass queueing networks
Nächster Artikel Heavy traffic limits for queues with non-stationary path-dependent arrival processes

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
Literatur
1.
Atar, R., Biswas, A., Kaspi, H.: Law of large numbers for the many-server earliest-deadline-first queue. Stoch. Process. Appl. 128(7), 2270–2296 (2018)CrossRef
2.
Atar, R., Biswas, A., Kaspi, H., Ramanan, K.: A Skorokhod map on measure-valued paths with applications to priority queues. Ann. Appl. Probab. 28(1), 418–481 (2018)CrossRef
3.
Atar, R., Shadmi, Y.: Fluid limits for earliest-deadline-first networks (2020)
4.
Bach, M.: The Design of the UNIX Operating System. Prentice-Hall International Editions. Prentice-Hall (1986)
5.
Bansal, N., Harchol-Balter, M.: Analysis of SRPT scheduling: investigating unfairness. In: Proceedings of the Joint International Conference on Measurements and Modeling of Computer Systems (SIGMETRICS 2001, Cambridge, MA, USA, June 16–20, 2011), pp. 279–290. Association for Computing Machinery, Inc (2001)
6.
Behera, H.S., Swain, B.K., Parida, A.K., Sahu, G.: A new proposed round robin with highest response ratio next (RRHRRN) scheduling algorithm for soft real time systems. Int. J. Eng. Adv. Technol. 37, 200–206 (2012)
7.
Birkhoff, G., Rota, G.: Ordinary Differential Equations, Introductions to Higher Mathematics. Wiley (1989)
8.
Cildoz, M., Mallor, F., Ibarra, A.: Analysing the Ed patient flow management problem by using accumulating priority queues and simulation-based optimization. In: 2018 Winter Simulation Conference (WSC), pp. 2107–2118 (2018)
9.
Dell’Amico, M., Carra, D., Pastorelli, M., Michiardi, P.: Revisiting size-based scheduling with estimated job sizes. In: 2014 IEEE 22nd International Symposium on Modelling, Analysis Simulation of Computer and Telecommunication Systems, pp. 411–420 (2014)
10.
Down, D.G., Gromoll, H.C., Puha, A.L.: Fluid limits for shortest remaining processing time queues. Math. Oper. Res. 34(4), 880–911 (2009)CrossRef
11.
Feitelson, D.: Notes on Operating Systems. The Hebrew University of Jerusalem (2011)
12.
Gromoll, H.C., Kruk, L., Puha, A.L.: Diffusion limits for shortest remaining processing time queues. Stoch. Syst. 1(1), 1–16 (2011)CrossRef
13.
Gromoll, M., Keutel, H.C.: Invariance of fluid limits for the shortest remaining processing time and shortest job first policies. Queue. Syst. 70, 145–164 (2012)CrossRef
14.
Harchol-Balter, M., Sigman, K., Wierman, A.: Asymptotic convergence of scheduling policies with respect to slowdown. Perform. Eval. 49, 07 (2003)
15.
Kleinrock, L.: A delay dependent queue discipline. Naval Res. Log. Q. 11(3–4), 329–341 (1964)CrossRef
16.
Kleinrock, L., Finkelstein, R.P.: Time dependent priority queues. Oper. Res. 15(1), 104–116 (1967)CrossRef
17.
Kruk, L., Lehoczky, J., Ramanan, K., Shreve, S.: Heavy traffic analysis for EDF queues with reneging. Ann. Appl. Probab. 21(2), 484–545 (2011)CrossRef
18.
Li, N., Stanford, D.A., Taylor, P., Ziedins, I.: Nonlinear accumulating priority queues with equivalent linear proxies. Oper. Res. 65(6), 1712–1721 (2017)CrossRef
19.
Little, J.D.C.: A proof for the queuing formula: \(L = \lambda w\). Oper. Res. 9(3), 383–387 (1961)CrossRef
20.
Mirtchev, S., Goleva, R.: Evaluation of Pareto/D/1/K queue by simulation. International Book Series “Information Science and Computing” No. 1, Supplement to the International Journal “Information Technologies and Knowledge” (2008)
21.
Nuyens, M., Zwart, B.: A large-deviations analysis of the G/G/1 SRPT queue. Queue. Syst.: Theory Appl. 54(2), 85–97 (2006)CrossRef
22.
Puha, A.L.: Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling. Ann. Appl. Probab. 25(6), 3381–3404 (2015)CrossRef
23.
Schrage, L.: Letter to the editor-a proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16(3), 687–690 (1968)CrossRef
24.
Schrage, L.E., Miller, L.W.: The queue M/G/1 with the shortest remaining processing time discipline. Oper. Res. 14(4), 670–684 (1966)CrossRef
25.
Silberschatz, A., Galvin, P., Gagne, G.: Operating System Concepts. Windows XP Update. Wiley (2005)
26.
Smith, D.R.: Technical note—a new proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 26(1), 197–199 (1978)CrossRef
27.
Stanford, D.A., Taylor, P., Ziedins, I.: Waiting time distributions in the accumulating priority queue. Queue. Syst. 77(3), 297–330 (2014)CrossRef
Metadaten
Titel
Fluid limits for shortest job first with aging
verfasst von
Yonatan Shadmi
Publikationsdatum
04.04.2022
Verlag
Springer US
Erschienen in
Queueing Systems / Ausgabe 1-2/2022
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI
https://doi.org/10.1007/s11134-021-09723-w

Weitere Artikel der Ausgabe 1-2/2022

Queueing Systems 1-2/2022 Zur Ausgabe

OriginalPaper

Appointment-driven queueing systems with non-punctual customers

OriginalPaper

Tandem fluid queue with long-range dependent inputs: sticky behaviour and heavy traffic approximation

OriginalPaper

Heavy traffic limits for queues with non-stationary path-dependent arrival processes

OriginalPaper

Fluid limits of a loss storage network

OriginalPaper

Instability of SRPT, SERPT and SJF multiclass queueing networks

Premium Partner

    Bildnachweise