Synchronized and gated queueing models

Abstract

Η διατριβή πραγματεύεται ζητήματα σχετιζόμενα με θεωρία ουρών που αφορούν σε συστήματα με θύρες με άπειρο πλήθος εξυπηρετούντων καθώς και συστήματα με συγχρονισμένες αφίξεις. Τα συστήματα με θύρες με άπειρο πλήθος εξυπηρετητών έχουν εφαρμογές σε βιομηχανικές διαδικασίες καθώς και σε τηλεπικοινωνιακά συστήματα. Λόγω του μηχανισμού της θύρας δεν είναι θεμιτό να γίνει μια ακριβής ανάλυση και γι’ αυτό εφαρμόζονται αναλυτικές μέθοδοι (ή προσομοίωση). Το γεγονός του άπειρου πλήθους των εξυπηρετούντων και η παρουσία του μηχανισμού θύρας κάνει το ερώτημα της ευστάθειας του συστήματος ενδιαφέρον ζήτημα.Η ευστάθεια της ουράς M/G/∞ με πύλη, διερευνάται με τη χρήση ενός κριτηρίου ολίσθησης των Foster–Lyapunov βάσει του οποίου αποδεικνύεται ότι το να είναι πεπερασμένη η πρώτη ροπή της κατανομής των χρόνων εξυπηρέτησης είναι ικανή και αναγκαία συνθήκη για τη θετική επανάληψη του συστήματος.Ένα σύστημα που αποτελείται από m ανεξάρτητους, παράλληλους και εκθετικούς εξυπηρετούντες, με ανάλογη ντετερμινιστική εισροή διερευνήθηκε ως μια τροποποίηση του Flatto-Hahn-Wright μοντέλου της θεωρίας ουρών, το οποίο αντίθετα με το αρχικό εξελίσσεται σε πιο εύκολα διαχειρίσιμο αναφορικά με την ανάλυσή του. Εστιάζουμε στην ευσταθή κατανομή του χρόνου που χρειάζονται οι πελάτες, η οποία επιτυγχάνεται με τη χρήση μιας Μαρκοβιανής προσέγγισης εισαγωγής σε συνδυασμό τον τύπο αντιστροφής.Τέλος, πραγματοποιήθηκε μια λεπτομερής ανάλυση της περιόδου αιχμής ενός συστήματος M/G/∞. Αναλύθηκε η διάρκεια του σταδίου μιας Μαρκοβιανής αλυσίδας παρέχοντας πλήθος λύσεων για την περίπτωση που έχουμε μικρή κίνηση. Και στις δύο περιπτώσεις τα τελικά αποτελέσματα εξαρτώνται από τη λύση άπειρων γραμμικών συστημάτων

This thesis deals with a number of related problems in Queueing Theory dealing with gated systems with an infinite number of servers, and systems with synchronized arrivals.Gated systems with an infinite number of servers have been studied as models of industrial processes and communications systems. Due to the gating mechanism, an exact analysis is typically not available and numerical methods (or simulation) is often used for such systems. Interestingly, despite the fact that there is an infinite number of servers, the presence of the gating mechanism makes even the question of stability of the system an interesting question. In Chapter 1 the stability of the gated M/G/∞ queue is investigated using a Foster–Lyapunov drift criterion and it is established that the finiteness of the first moment of the service time distribution is the necessary and sufficient condition for the positive recurrence of the system. This result was published in Probability in Engineering and Information Sciences. We examine a system consisting of m independent exponential servers in parallel, driven by the same deterministic input. This is a modification of the Flatto-Hahn-Wright model of queueing theory which, unlike the original, turns out to be analytically tractable. We focus on the time-stationary distribution of the number of customers which is obtained using a Markov embedding approach together with the Palm inversion formula. This result was published in Letters of Operations Research.Additionally, a detailed analysis of the busy period of the gated M/G/∞ system is carried out. The stage length Markov chain is analyzed and a series solution is given in the light traffic case. Similarly, a gated GI/M/∞ system is considered and again the Markov chain analyzing the number of customers in each service stage is analyzed in light traffic. In both cases the final results depend on the solution of infinite linear systems. Finally, we consider the problem of m servers in parallel fed by a single Poisson process which causes simultaneous arrivals in all systems. Under the assumption that service times in the servers are stochastically ordered we are able to obtain the joint workload distribution for the m systems using the rate conservation principle. We also study the joint statistics of the busy periods of the m systems.