Fluid Limits for Longest Job First Queues

• 成果类型: Article; Early Access
• 署名作者: Kruk, Lukasz
• 署名单位: Maria Curie-Sklodowska University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2024.0415
• 发表日期: 2025
• 关键词: remaining processing time

摘要

A single-server queue with renewal arrivals and generally distributed independent and identically distributed service times is considered. Customers are served using the longest job first (LJF) scheduling algorithm with first in, first out being used as a tiebreaking rule. We introduce a fluid model for the evolution of a measure-valued state descriptor of this queue, and we investigate its properties. We also prove a fluid limit theorem justifying our fluid model as the first order approximation of the queueing system under consideration. Finally, we compare LJF fluid models and fluid limits with their counterparts for the longest remaining service time first (LRTF) service discipline, a preemptive variant of LJF. It turns out that the queue limiting behavior under these two protocols differs significantly, suggesting implementing LJF rather than LRTF in single-server systems.