Equilibrium and optimal control policies for queueing models with variable service capacity
Authors: Δημητρακόπουλος Ιωάννης 
Published: August 2021

Στην παρούσα διατριβή αναπτύσσουμε και αναλύουμε Στοχαστικά Μοντέλα Ουρών Αναμονής για τη μελέτη της επίδρασης του μεταβαλλόμενου ρυθμού εξυπηρέτησης στο ρυθμό εισόδου πελατών στο σύστημα, υποθέτοντας δύο διαφορετικούς τρόπους για τον έλεγχο της εισόδου. Στο πρώτο πρόβλημα υποθέτουμε ότι οι πελάτες αντιμετωπίζουν στρατηγικά τις αναμενόμενες καθυστερήσεις κατά το χρόνο παραμονής τους στο σύστημα,συγκρίνοντας την ωφέλεια που έχουν από τη λήψη της εξυπηρέτησης σε σχέση με τον αναμενόμενο συνολικό χρόνο παραμονής τους, όταν ο διαχειριστής του συστήματος μεταβάλλει το ρυθμό εξυπηρέτησης δυναμικά σε σχέση με το επίπεδο του συνωστισμού. Σε αυτή τη περίπτωση, ο έλεγχος του ρυθμού εισόδου στο σύστημα είναι έμμεσος, καθώς αυτός προκύπτει ως σημείο στρατηγικής ισορροπίας του παιγνίου που πραγματοποιείται μεταξύ των δυνητικών πελατων που φθάνουν για εξυπηρέτηση. Η εφαρμοζόμενη πολιτικήελέγχου του ρυθμού εξυπηρέτησης έχει σαν αποτέλεσμα την ύπαρξη περισσότερων από ένα σημείων στρατηγικής ισορροπίας. Στο δεύτερο πρόβλημα υποθέτουμε ότι ο διαχειριστής του συστήματος ελέγχει άμεσα τόσο το ρυθμό εξυπηρέτησης όσο και το ρυθμό εισόδου των πελατών στο σύστημα ως συνάρτηση του επιπέδου του συνωστισμού, στο πλαίσιο του Στοχαστικού Δυναμικού Προγραμματισμού.Συγκεκριμένα, στο πρώτο μέρος της διατριβής θεωρούμε το πρόβλημα της στρατηγικής συμπεριφοράς πελατών όταν αυτοί λαμβάνουν αποφάσεις εισόδου σε ένα Μαρκοβιανό σύστημα εξυπηρέτησης με έναν υπηρέτη και με ρυθμό εξυπηρέτησης που μεταβάλλεται μεταξύ ενός αργού και ενός γρήγορου ρυθμού σύμφωνα με μία δυναμική πολιτική της μορφής κατωφλίου. Υποθέτουμε ότι οι αφικνούμενοι πελάτες αποφασίζουν αν θα εισέλθουν στο σύστημα λαμβάνοντας ένα σταθερό έσοδο στο τέλος της εξυπηρέτησης τους ή θα αρνηθούν να μπουν σε αυτό επιλέγοντας να λάβουν μία εναλλακτική πληρωμή. Οι πελάτες που φθάνουν στο σύστημα δεν έχουν πληροφόρηση σχετικά με το ύψος του συνωστισμού αν και γνωρίζουν τη πολιτική με την οποία αλλάζει ο ρυθμός εξυπηρέτησης από το διαχειριστή, όπως επίσης και το γενικό ρυθμό αφίξεων. Καθώς ο αναμενόμενος χρόνος παραμονής ενός πελάτη στο σύστημα δεν είναι μονότονη συνάρτηση του πραγματικού ρυθμού εισόδου, το σημείο στρατηγικής ισορροπίας δεν είναι μοναδικό και,μάλιστα, αποδεικνύουμε ότι υπάρχουν το πολύ τρεις στρατηγικές ισορροπίας. Επιπλέον, θεωρώντας το πρόβλημα μεγιστοποίησης του αναμενόμενου συνολικού οφέλους όλων των πελατών, δείχνουμε αριθμητικά ότι κάθε βέλτιστη στρατηγική που μεγιστοποιεί το αναμενόμενο συνολικό όφελος διατάσσεται μεταξύ των ακραίων σημείων ισορροπίας του προβλήματος της ατομικής βελτιστοποίησης. Από τη στιγμή που οι στρατηγικές ισορροπίαςτων πελατών δε συμπίτουν με τις βέλτιστες στρατηγικές της μεγιστποίησης του συνολικού οφέλους, αναλύουμε αυτή την αναποτελεσματικότητα του συστήματος μελετώντας τη τιμή αναρχίας. Πιο συγκεκριμένα, δείχνουμε αριθμητικά ότι η τιμή αναρχίας αυξάνεται απεριόριστα όταν η εναλλακτική πληρωμή μειώνεται, καθώς σε αυτή τη περίπτωση οι πελάτες είναι αδιάφοροι όσον αφορά την είσοδό τους ή όχι κάτω από οποιαδήποτε πολιτική ισσοροπίας.Το πρόβλημα της μεγιστοποίησης της αναμενόμενης συνολικής ωφέλειας όλων των πελατών, μπορεί να θεωρηθεί ως ένας τρόπος ελέγχου τόσο του ρυθμού εισόδου πελατών στο σύστημα όσο και του ρυθμού εξυπηρέτησης. Ενα πιο ρεαλιστικό πλαίσιο για την εξέταση της επίδρασης του μεταβαλλόμενου ρυθμού εξυπηρέτησης στο ρυθμό εισόδου πελατών είναι να υποθέσουμε ότι ο διαχειριστής του συστήματος πρώτα παρατηρεί το μήκος της ουράς και ακολούθως αποφασίζει δυναμικά τόσο το ρυθμό εισόδου πελατών στο σύστημα όσο και τον αντίστοιχο ρυθμό εξυπηρέτησης. Στο δεύτερο μέρος τηςπαρούσας διατριβής, μελετάμε την επίδραση του μεταβαλλόμενου ρυθμού εξυπηρέτησης όταν αυτός λαμβάνει διακεκριμένες τιμές από ένα πεπερασμένο σύνολο με αύξουσες τιμές σε μία Μ/Μ/1 ουρά αναμονής με δυναμικό έλεγχο της αποδοχής πελατών από το διαχειριστή του συστήματος. Για την ανάλυση του από κοινού δυναμικού ελέγχου του ρυθμού εξυπηρέτησης και της αποδοχής πελατών στο σύστημα, διαμορφώνουμε την αντίστοιχη Μαρκοβιανή διαδικασία αποφάσεων με κριτήριο τη μεγιστοποίηση του προεξοφλημένου ή του μέσου αναμενόμενου συνολικού κέρδους του συστήματος, όπου η πληρωμή κάθε πελάτη για την εξυπηρέτησή του πραγματοποιείται είτε κατά την είσοδο του στο σύστημα είτε στο τέλος κάθε εξυπηρέτησης. Για κάθε περίπτωση, αποδεικνύουμε ότι η από κοινού βέλτιστη πολιτική είναι της μορφής κατωφλίου και για τους δύο ελέγχους. Ορίζουμε την αξία της ευελιξίας στην εξυπηρέτηση ως τη διαφορά μεταξύ των βέλτιστων τιμών των προβλημάτων του από κοινού δυναμικού ελέγχου σε σχέση με το πρόβλημα τουδυναμικού ελέγχου της αποδοχής πελατών όταν ο υπηρέτης εξυπηρετεί μόνο στον πιο αργό ρυθμό. Υποθέτοντας μια απλή συνθήκη μεταξύ της πληρωμής για την εξυπηρέτηση και της σχετικής αύξησης του κόστους εξυπηρέτησης, αποδεικνύουμε ότι η αξία της ευελιξίας στην εξυπηρέτηση είναι θετική και αύξουσα ως προς το επίπεδο του συνωστισμού. Επιπλέον, το κατώφλι της βέλτιστης πολιτικής για την αποδοχη πελατών αυξάνει, με αποτέλεσμα περισσότεροι πελάτες να εξυπηρετούνται λόγω της ευελιξίας στο ρυθμόεξυπηρέτησης. Τέλος, παρουσιάζουμε και αριθμητικά αποτελέσματα για όλες τις διαφορετικές περιπτώσεις σχετικά με τη δομή της βέλτιστης πολιτικής και την ανάλυση της αξίας της ευελιξίας σε σχέση με τη πληρωμή της εξυπηρέτησης.