Multi-server preemptive priority queue with general arrivals and service times

Alexandre Brandwajn 1 Thomas Begin 2
2 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Abstract : We present a simple approximate solution for preemptive-resume queues with multiple servers, general (phase-type) service and general (phase-type) interarrival time distributions. In our solution, priority levels are solved one at a time in the order of decreasing priorities. Each priority level is solved approximately using a reduced state description. The complexity of our approximate solution in terms of the number of equations solved grows linearly with the number of servers and priority levels. We studied a large number of numerical examples with a range of values for mean service times and offered loads across priority levels, varying the number of servers from 8 to 48. Discrete-event simulation was used to assess the accuracy of our approximate solution. Overall, in the case of Poisson and quasi-Poisson arrivals, expected relative error for the mean number of customers in the system was below 2% while the corresponding median relative error was below 0.25%. The good accuracy of our approximation appears to extend to the case of phase-type times between arrivals, with expected relative errors for the mean number in system below 5% even for a Pareto-like distribution of interarrival times with a large coefficient of variation. Our numerical results indicate that the proposed approximation provides a relatively simple and generally accurate approach to preemptive-resume queues with larger numbers of servers and general distributions of service and interarrival times.
Type de document :
Article dans une revue
Performance Evaluation, Elsevier, 2017, 〈10.1016/j.peva.2017.08.003〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01581118
Contributeur : Thomas Begin <>
Soumis le : lundi 4 septembre 2017 - 12:28:43
Dernière modification le : jeudi 1 novembre 2018 - 01:22:16

Fichier

Preemptive priority queue-v28....
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Alexandre Brandwajn, Thomas Begin. Multi-server preemptive priority queue with general arrivals and service times. Performance Evaluation, Elsevier, 2017, 〈10.1016/j.peva.2017.08.003〉. 〈hal-01581118〉

Partager

Métriques

Consultations de la notice

238

Téléchargements de fichiers

282