Fluid Limits for Longest Remaining Time First Queues

References

• [1] Abdullahi I (2012) Process scheduling in longest job first (LJF) algorithm. A Propose framework for starvation problem. MS dissertation, Ahmadu Bello University, Zaria, Nigeria.Google Scholar
• [2] Ahmed YEY (2019) Task scheduling mechanism in datacenter using longest processing time first and round robin algorithms. MS dissertation, University of Gezira, Wad Medani, Sudan.Google Scholar
• [3] Arisha A, Young P, El Baradie M (2002) Flow shop scheduling problem: A computational study. Proc. Sixth Internat. Conf. Production Engrg. Design Development (PEDD6), 543–557.Google Scholar
• [4] Atar R, Shadmi Y (2023) Fluid limits for earliest-deadline-first networks. Stochastic Processes Their Appl. 157:279–307.Crossref, Google Scholar
• [5] Atar R, Biswas A, Kaspi H (2015) Fluid limits of G/G/1+G queues under the non-preemptive earliest-deadline-first discipline. Math. Oper. Res. 40(3):683–702.Link, Google Scholar
• [6] Atar R, Biswas A, Kaspi H, Ramanan K (2018) A Skorokhod map on measure-valued paths with applications to priority queues. Ann. Appl. Probab. 28(1):418–481.Crossref, Google Scholar
• [7] Banerjee S, Budhiraja A, Puha AL (2022) Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions. Ann. Appl. Probab. 32(4):2587–2651.Crossref, Google Scholar
• [8] Billingsley P (1999) Convergence of Probability Measures, 2nd ed. (John Wiley & Sons, Inc., New York).Crossref, Google Scholar
• [9] Chen H, Yao DD (2001) Fundamentals of Queueing Networks (Springer Science+Business Media, New York).Crossref, Google Scholar
• [10] Cheng TCE, Kahlbacher HG (1991) A proof for the longest-job-first policy in one-machine scheduling. Naval Res. Logist. 38(5):715–720.Crossref, Google Scholar
• [11] Decreusefond L, Moyal P (2008) Fluid limit of a heavily loaded EDF queue with impatient customers. Markov Processes Related Fields 14(1):131–158.Google Scholar
• [12] DigitalThinkerHelp (2023) Longest remaining time first (LRTF) Scheduling with examples & programs. Accessed July 13, 2023, https://digitalthinkerhelp.com/longest-remaining-time-first-scheduling/.Google Scholar
• [13] Down DG, Gromoll HC, Puha AL (2009) Fluid limits for shortest remaining processing time queues. Math. Oper. Res. 34(4):880–911.Link, Google Scholar
• [14] Doytchinov B, Lehoczky JP, Shreve SE (2001) Real-time queues in heavy traffic with earliest-deadline-first queue discipline. Ann. Appl. Probab. 11(2):332–378.Crossref, Google Scholar
• [15] Ethier SN, Kurtz TG (1986) Markov Processes: Characterization and Convergence (John Wiley & Sons, Inc., New York).Crossref, Google Scholar
• [16] GateVidyalay (2023) Longest job first algorithm | LRTF scheduling. Accessed March 16, 2023, https://www.gatevidyalay.com/longest-job-first-algorithm-lrtf-scheduling/.Google Scholar
• [17] GeeksforGeeks (2022) Longest remaining time first (LRTF) or preemptive longest job first CPU scheduling algorithm. Accessed March 16, 2023, https://www.geeksforgeeks.org/longest-remaining-time-first-lrtf-cpu-scheduling-algorithm/.Google Scholar
• [18] Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2):416–429.Crossref, Google Scholar
• [19] Gromoll HC, Keutel M (2012) Invariance of fluid limits for the shortest remaining processing time and shortest job first policies. Queueing Systems 70(2):145–164.Crossref, Google Scholar
• [20] Gromoll HC, Kochalski KD (2023) Critical fluid limit of a gated processor sharing queue. Preprint, submitted February 14, https://arxiv.org/abs/2302.06796.Google Scholar
• [21] Gromoll HC, Williams RJ (2009) Fluid limits for networks with bandwidth sharing and general document size distribution. Ann. Appl. Probab. 19(1):243–280.Crossref, Google Scholar
• [22] Gromoll HC, Kruk Ł, Puha AL (2011) Diffusion limits for shortest remaining processing time queues. Stochastic Systems 1(1):1–16.Link, Google Scholar
• [23] Gromoll HC, Puha AL, Williams RJ (2002) The fluid limit of a heavily loaded processor sharing queue. Ann. Appl. Probab. 12(3):797–859.Crossref, Google Scholar
• [24] Gromoll HC, Robert P, Zwart B (2008) Fluid limits for processor sharing queues with impatience. Math. Oper. Res. 33(2):375–402.Link, Google Scholar
• [25] Harchol-Balter M, Sigman K, Wierman A (2002) Asymptotic convergence of scheduling policies with respect to slowdown. Performance Evaluation 49(1–4):241–256.Crossref, Google Scholar
• [26] Hefetz N, Adiri I (1982) An efficient optimal algorithm for the two-machines unit-time jobshop schedule-length problem. Math. Oper. Res. 7(3):354–360.Link, Google Scholar
• [27] Herrería-Alonso S, Suárez-González A, Rodríguez-Pérez M, López-Garcá C (2022) Enhancing LoRaWAN scalability with longest first slotted CSMA. Comput. Networks 216:109252.Crossref, Google Scholar
• [28] Keutel MP (2011) Fluid limits for the shortest job first and the least attained service protocols. PhD dissertation, University of Virginia, Charlottesville.Google Scholar
• [29] Kruekaew B, Kimpan W (2014) Virtual machine scheduling management on cloud computing using artificial bee colony. Ao SI, Castillo O, Douglas C, Feng DD, Lee Y-A, eds. Proc. Internat. MultiConference Engineers Comput. Scientists (IMECS 2014), vol. I (Newswood Limited, Hong Kong, China), 18–22.Google Scholar
• [30] Kruk Ł (2023) Instability of LRTF multiclass queueing networks. Oper. Res. Lett. 51(3):201–205.Crossref, Google Scholar
• [31] Kruk Ł, Sokołowska E (2016) Fluid limits for multiple-input shortest remaining processing time queues. Math. Oper. Res. 41(3):1055–1092.Link, Google Scholar
• [32] Kruk Ł, Lehoczky JP, Shreve SE, Yeung S-N (2004) Earliest-deadline-first service in heavy-traffic acyclic networks. Ann. Appl. Probab. 14(3):1306–1352.Crossref, Google Scholar
• [33] Kumar M, Sharma SC (2016) Priority aware longest job first (PA-LJF) algorithm for utilization of the resource in cloud environment. Hoda MN, ed. 2016 3rd Internat. Conf. Comput. Sustainable Global Development (INDIACom) (IEEE, New York), 415–420.Google Scholar
• [34] Kundakcı N, Kulak O (2016) Hybrid genetic algorithms for minimizing makespan in dynamic job shop scheduling problem. Comput. Indust. Engrg. 96:31–51.Crossref, Google Scholar
• [35] Pinedo ML (2012) Scheduling (Springer-Verlag, New York).Crossref, Google Scholar
• [36] Prohorov YuV (1956) Convergence of random processes and limit theorems in probability theory. Theory Probab. Appl. 1(2):157–214.Crossref, Google Scholar
• [37] Puha AL (2015) Diffusion limits for shortest remaining processing time queues under nonstandard spatial scaling. Ann. Appl. Probab. 25(6):3381–3404.Crossref, Google Scholar
• [38] Schrage LE (1968) A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16(3):687–690.Link, Google Scholar
• [39] Schrage LE, Miller LW (1966) The queue M/G/1 with the shortest remaining processing time discipline. Oper. Res. 14(4):670–684.Link, Google Scholar
• [40] Shadmi Y (2022) Fluid limits for shortest job first with aging. Queueing Systems 101(1–2):93–112.Crossref, Google Scholar
• [41] Wen C-H, Haga SW, Lin RC-H (2013) File delivery with longest processing time first scheduling in P2P networks. Internat. J. Grid Distributed Comput. 6(2):39–46.Google Scholar
• [42] Wierman A, Harchol-Balter M (2003) Classifying scheduling policies with respect to unfairness in an M/G/1. Cheng B, Tripathi ST, Rexford J, Sanders WH, eds. Proc. 2003 ACM Sigmetrics Internat. Conf. Measurement Model. Comput. Systems (Association for Computing Machinery, New York), 238–249.Google Scholar
• [43] Zhang J, Dai JG, Zwart B (2009) Law of large number limits of limited processor-sharing queues. Math. Oper. Res. 34(4):937–970.Link, Google Scholar