Υπολογισμοί στάσιμων χαρακτηριστικών πολυδιάστατων μαρκοβιανών αλυσίδων και εφαρμογές στις ουρές αναμονής

Abstract

Το θέμα της διδακτορικής διατριβής αφορά στη μελέτη διαφόρων ουρών αναμονής και τις εφαρμογές τους. Συγκεκριμένα ασχολήθηκα με χωρικά μη-ομογενείς, εξαρτώμενες από την εκάστοτε κατάσταση του συστήματος, Μαρκοβιανές διαδικασίες, δηλαδή διαδικασίες στις οποίες εμφανίζονται ρυθμοί από μια κατάσταση n σε κάποια άλλη κατάσταση n' με ρυθμό ανάλογο του n. Το φαινόμενο αυτό συνήθως εμφανίζεται εξαιτίας χαρακτηριστικών όπως οι επαναπροσπάθειες (retrials), υπαναχωρήσεις (reneging) ή ο άπειρος αριθμός υπηρετών. Αυτός είναι επίσης ο κανόνας στα στοχαστικά μοντέλα της μαθηματικής βιολογίας, μιας και κάθε μονάδα του πληθυσμού σχετίζεται με γεννήσεις και θανάτους. Συγκεκριμένα μελέτησα μη-ομογενείς Μαρκοβιανές διαδικασίες με διωνυμικούς ρυθμούς μετάβασης, καθώς και αλυσίδες με διωνυμικές μεταβάσεις και γενικούς χρόνους. Στα Μαρκοβιανά μοντέλα, αυτοί οι τύποι μη ομογενών ρυθμών μετάβασης, εξαρτώμενοι από την εκάστοτε κατάσταση, οδηγούν σε μη-ομογενείς πίνακες ρυθμών μετάβασης, που δυσχεραίνουν τον υπολογισμό των μέτρων απόδοσης του συστήματος. Στη περίπτωση μη Μαρκοβιανών συστημάτων, ο κύριος τρόπος αντιμετώπισης τους βασίζεται σε μεθοδολογίες που απορρέουν από τη μελέτη της M/G/? ουράς. Και στις δυο περιπτώσεις, είναι δίκαιο να πούμε πως τα περισσότερα εξ' αυτών των μοντέλων είναι μη ιχνηλατίσημα (analytically intractable). Για να ξεπεραστούν οι δυσκολίες στη μελέτη τέτοιων συστημάτων έχουν αναπτυχθεί πλήθος μεθοδολογιών. Ιδιαιτέρως αποτελεσματικές έχουν αποδειχθεί οι γεννήτριες συναρτήσεις. Tέτοιας μορφής συστήματα είναι συνήθως μη ιχνηλατίσημα (intractable) ή επιλύονται με τη χρήση υπεργεωμετρικών σειρών. Στη διδακτορική διατριβή μελετήθηκαν συγκεκριμένα μη ομογενή μοντέλα που προκύπτουν από συγχρονισμένες εξυπηρετήσεις ή συγχρονισμένες υπαναχωρήσεις. Για να συνοψίσω τι είναι οι συγχρονισμένες αποφάσεις θεωρούμε μια Poisson διαδικασίας με ρυθμό ν, στις στιγμές της οποίας δίνεται η ευκαιρία στους πελάτες να αποφασίσουν ταυτόχρονα, αλλά ανεξάρτητα ο ένας από τον άλλον αν θα αναχωρήσουν από το σύστημα όλοι με την ίδια πιθανότητα p. Συνεπώς στις ευκαιρίες της Poisson διαδικασίας όλοι οι παρόντες πελάτες παραμένουν στο σύστημα με πιθανότητα q=1-p, p?(0,1) ή εγκαταλείπουν το σύστημα με πιθανότητα p, ανεξάρτητα ο καθένας από τους υπόλοιπους. Η ανωτέρω μορφή αναφέρεται ως συγχρονισμένες αποφάσεις (εξυπηρετήσεις/αναχωρήσεις). Γενικά, το φαινόμενο του συγχρονισμού σε Μαρκοβιανά μοντέλα οδηγεί σε ρυθμούς από μια κατάσταση n σε μια κατάσταση n' ανάλογους μιας διωνυμικής πιθανότητας (n,p), όπως φαίνεται στο ακόλουθο σχήμα. To καινοτόμο στοιχείο της διδακτορικής διατριβής έγκειται στην εισαγωγή και μελέτη συγχρονισμένων γεγονότων τα οποία συνεπάγονται διωνυμικές μεταβάσεις, από μια κατάσταση n σε όλες τις καταστάσεις n', για 0? n'< n. Παρόμοιες Μαρκοβιανές αλυσίδες εμφανίζονται στη Μαθηματική Βιολογία στη μελέτη του μεγέθους πληθυσμών που υπόκεινται σε διωνυμικές καταστροφές. Επικεντρώθηκα σε διδιάστατα συστήματα εξυπηρέτησης με συγχρονισμένες εξυπηρετήσεις ή συγχρονισμένες υπαναχωρήσεις. Αρχικά μελετήθηκαν συστήματα με συγχρονισμένες εξυπηρετήσεις σαν τροποποίηση/επέκταση των μοντέλων με άπειρους υπηρέτες. Ενώ στη συνέχεια μελετήθηκαν συστήματα με συγχρονισμένες υπαναχωρήσεις, συνδυάζοντας το χαρακτηριστικό των συγχρονισμένων υπαναχωρήσεων με την απουσία του υπηρέτη. Η ιδέα του συγχρονισμού, λόγω των διωνυμικών μεταβάσεων, αυξάνει τη δυσκολία υπολογισμού της στάσιμης κατανομής του συστήματος, καθώς και των υπόλοιπων μέτρων στασιμότητας, όπως της κατανομής του χρόνου αναμονής και της κατανομής του χρόνου συνεχούς λειτουργίας. Η μελέτη γίνεται με τη χρήση της τεχνικής των γεννητριών συναρτήσεων. Συγκεκριμένα υπολογίστηκαν η στάσιμη κατανομή των συστημάτων υπό μελέτη, παρέχοντας αλγοριθμικά σχήματα και κλειστές μορφές των πιθανογεννητριών συναρτήσεων του πλήθους των πελατών στο σύστημα, διάφορα μέτρα λειτουργικότητας, όπως η κατανομή του χρόνου παραμονής και η κατανομή του χρόνου συνεχούς λειτουργίας, και διάφορες μέσες τιμές μέτρων λειτουργικότητας του συστήματος. Τέλος παραθέτονται διάφορα αποτελέσματα που αφορούν τη συμπεριφορά του συστήματος κάτω από διάφορες οριακές περιπτώσεις.