Fluid Limits for Longest Job First Queues

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 tie-breaking 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.