Equilibrium and optimal control policies for queueing models with variable service capacity

Abstract

In this thesis, we develop and analyze stochastic queueing models with which we study the effect of a varying service rate policy on customer arrival rate, considering two different ways for controlling customer entrance. In the first problem, we assume thatcustomers respond strategically to excessive delays by taking into account the tradeoff between service benefit and expected delay in the presence of a service control dynamic policy employed by the system administrator. In this case, arrival rate control is implicit, since it is imposed in equilibrium in the game between potential incoming customers. The effect of the service rate policy is that the possible equilibria are generally more than one. In the second problem, we assume that the system administrator controls both customer arrival rate and the service rate employed with respect to the system congestion in a stochastic dynamic framework.More specifically, in the first part of this dissertation, we consider the problem of customer equilibrium behavior on joining a single server Markovian queueing system with varying service rate between a low and a high value, according to a threshold based dynamic policy. We assume that arriving customers decide whether they will join a queue and receive a fixed reward or balk, i.e., decline to enter the queue, and compromise with an alternative payment. When customers make this decision they don't have any information on the system congestion upon arrival, but they know the implemented service policy. Since a tagged customer's expected delay is not monotone increasing in the arrival rate, the equilibrium strategy is not unique, and we show that the number of such strategies can vary from zero to three. Moreover, regarding the problem of maximizing the overall customer expected net benefit, we show numerically that, the optimal arrival rate that maximizes the customer's overall welfare lies between the extreme equilibrium arrival rates. Since the equilibrium arrival rates and the social optimal strategies do not coincide, we analyze this inefficiency considering the Price of Anarchy. We show that as the value of balking decreases, the price of anarchy becomes unbounded since customers are indifferent between joining and balking under any equilibrium strategy.The latter problem of social optimization can be viewed as one way of centrally controlling both admission and service rate. A more realistic setting to examine the impact of the service rate switch to a higher value on arrival rate is to assume that the system manager observes the queue length and dynamically sets both the arrival and the service rate. In the second part of this dissertation, we consider the effect of varying the service rate between a finite set of increasing values in an M/M/1 queue with admission control. Here, we formulate a Markov Decision Process model to analyze the joint admission and service control, considering both discounted and average expected profit maximization with the service payment being made upon admission or at the end of service. For each case, we derive a threshold-based optimal policy for both controls. We define the value of service rate flexibility as the difference in optimal profit between the joint control model and an admission control model with service rate set at the lowest value. Under a simple condition between the service payment and the relative cost of service rate increase, we show that the value of service rate flexibility is positive, and, increasing in the system congestion. Moreover, the optimal admission threshold increases, so, more customers are accepted due to service rate flexibility. Finally, sensitivity analysis with respect to the service payment for the different cases is pursued numerically.

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