Random-order-of-service for heterogeneous customers: waiting time analysis

In operations research and networking problems, random-order-of-service (ROS) provides a well-known alternative to the classic first-come-first-served (FCFS) policy. Models with ROS policy are typically harder to analyze than their FCFS counterparts, with some performance measures notoriously hard to obtain. While significant progress has been realized in the analysis of random-order-of-service models with homogeneous customer service demands, the impact of heterogeneous customer demand is largely unknown. The current contribution studies this impact, with a discrete-time random-order-of-service queue serving customers with heterogeneous demands. Customer service times are independent random variables with type-dependent distribution. The numbers of new arrivals in each slot are independent and identically distributed over time, but can be type-correlated within a single slot. This corresponds to bursty input traffic generated by a finite number of sources, with one source for each type. The burstiness consists in correlation among sources (or types): the rate at which a source generates customers depends on the instantaneous rate of all other sources (and vice versa). Using a transform-based approach yields closed-form formulas for the first few moments of the customer waiting time. Facilitator is a multi-stage description of the customer sojourn, which allows establishing a relation between the so-called conditional waiting time and the actual steady-state customer waiting time. A somewhat unexpected result shows that, under certain conditions on the arrival and service processes, the random-order-of-service policy outperforms the first-come-first-served policy in terms of mean waiting time. A number of numerical examples illustrate this finding. Copyright Springer Science+Business Media New York 2015