A Queueing Model that Works Only on the Biggest Jobs

We consider a queueing system with capacity 1 and subject to a Poisson arrival process. Jobs consists of a random number of tasks and at each arrival, the system will continue to work on the current job if the number of its tasks is higher or equal than the number of tasks of the job just arrived, otherwise the job in the queue leaves the system and the one just arrived begins its service. The service time of each task is independent and exponentially distributed with the same parameter. We give an explicit solution for the stationary distribution of the queue by resorting to time-reversed analysis and we observe that this approach gives a much more elegant and constructive way to obtain the result than the traditional approach based on the verification of the system of global balance equations. For geometric distribution of the number of tasks, we use the q-algebra to make the results numerically tractable. The queueing system finds applications in contexts in which the size of jobs is known or partially known and schedulers or dispatchers can take decisions based on this information to improve the overall performance (e.g., reducing the mean response time).