Article ID: | iaor20033019 |
Country: | Netherlands |
Volume: | 31 |
Issue: | 4 |
Start Page Number: | 254 |
End Page Number: | 262 |
Publication Date: | Jul 2003 |
Journal: | Operations Research Letters |
Authors: | Boxma O.J., Morrison J.A., Borst S.C., Queija R. Nez |
Keywords: | GI/M/1 queues |
In this note we explore a useful equivalence relation for the delay distribution in the G/M/1 queue under two different service disciplines: (i) processor sharing (PS); and (ii) random order of service (ROS). We provide a direct probabilistic argument to show that the sojourn time under PS is equal (in distribution) to the waiting time under ROS of a customer arriving to a non-empty system. We thus conclude that the sojourn time distribution for PS is related to the waiting-time distribution for ROS through a simple multiplicative factor, which corresponds to the probability of a non-empty system at an arrival instant. We verify that previously derived expressions for the sojourn time distribution in the M/M/1 PS queue and the waiting-time distribution in the M/M/1 ROS queue are indeed identical, up to a multiplicative constant. The probabilistic nature of the argument enables us to extend the equivalence result to more general models, such as the