Μάθημα : Ουρές Αναμονής (859)

Περιγραφή

Περιγραφή

Τυπικά παραδείγματα ουρών αναμονής που παρουσιάζονται στις εφαρμογές είναι τα ταμεία των τραπεζών και γενικότερα διαφόρων οργανισμών, τα τηλεφωνικά κέντρα εξυπηρέτησης πελατών, το τηλεφωνικό δίκτυο, το διαδίκτυο καθώς και τοπικά δίκτυα υπολογιστών, οι γραμμές παραγωγής μιας βιομηχανικής μονάδας, συγκοινωνιακά δίκτυα κλπ.

Στόχος της θεωρία των ουρών αναμονής είναι η ποσοτική περιγραφή τέτοιων συστημάτων και ο βέλτιστος σχεδιασμός τους. Έτσι η θεωρία ουρών απαντά σε προβλήματα του τύπου

• Πόσο περιμένει κάθε πελάτης κατά μέσο όρο;
• Πόσο είναι το μήκος της ουράς που σχηματίζεται κατά μέσο όρο;
• Πόσο θα μειωθεί κατά μέσο όρο η ουρά αν προστεθεί ένας επιπλέον υπηρέτης;
• Πόσοι υπηρέτες πρέπει να υπάρχουν ώστε η πιθανότητα να υπερχειλίσει το σύστημα να είναι μικρότερη από 1%;

Για την ουσιαστική μελέτη τέτοιων συστημάτων το βασικό εργαλείο είναι η Θεωρία Πιθανοτήτων και Στοχαστικών Ανελίξεων, αφού τα μαθηματικά πρότυπα των ουρών αναμονής είναι στοχαστικά (τυχαιοκρατικά). Για να είναι ένας φοιτητής σε θέση να παρακολουθήσει με επιτυχία το μάθημα θα πρέπει να έχει παρακολουθήσει και κατανοήσει επαρκώς τα μαθήματα Πιθανότητες Ι και Στοχαστικές Ανελίξεις. Επιθυμητή, αν και όχι απαραίτητη, είναι και η παρακολούθηση του μαθήματος Στοχαστικές Μέθοδοι στην Επιχειρησιακή Έρευνα Ι. Κατά τη διάρκεια της διδασκαλίας θα γίνει ανασκόπηση των εννοιών από τις στοχαστικές διαδικασίες που χρειάζονται ώστε να είναι δυνατό να παρακολουθήσει το μάθημα κάποιος φοιτητής, χωρίς να έχει ποτέ παρακολουθήσει τις Στοχαστικές Μεθόδους στην Επιχειρησιακή Έρευνα και/ή τις Στοχαστικές Ανελίξεις. Στην περίπτωση αυτή όμως θα πρέπει ο φοιτητής να καταβάλει επιπλέον προσπάθεια.

Βιβλιογραφία

1. Φακίνου Δ. (2003) Ουρές Αναμονής. Αθήνα. (Προτεινόμενο σύγγραμμα για όσους δηλώσουν το μάθημα)
2. Οικονόμου Α. (2017) Ουρές Αναμονής. Αθήνα. (Πρόχειρες σημειώσεις υπό διαμόρφωση διαθέσιμες από την παρούσα ηλεκτρονική τάξη του μαθήματος).

Βιντεοδιαλέξεις

Τα βίντεο του μαθήματος "Ουρές Αναμονής" για το ακαδημαϊκό έτους 2016-2017 υπάρχουν στην πλατφόρμα delos.uoa.gr. Δυστυχώς, λόγω κάποιου τεχνικού προβλήματος, τα βίντεο της πρώτης εβδομάδας δεν είναι ολόκληρα, ούτε έχουν ήχο.

Σημειώσεις φοιτητών

Οι σημειώσεις από τις παραδόσεις του ακαδημαϊκού έτους 2016-2017 βρίσκονται στα έγγραφα, όπως τις κρατά ο φοιτητής Κωνσταντίνος Ζαχαριάς, τον οποίο και ευχαριστώ θερμά.

Ύλη

1. Περιγραφή των ουρών αναμονής και γενικά αποτελέσματα: βασικά χαρακτηριστικά των ουρών αναμονής, μέτρα λειτουργικότητας και απόδοσης, η διαδικασία μήκους ουράς, εμφυτευμένες διαδικασίες του μήκους ουράς σε στιγμές αφίξεων και αναχωρήσεων, η ιδιότητα PASTA, το θεώρημα του Little.
2. Απλές Μαρκοβιανές Ουρές: το γενικό μοντέλο, η Μ/Μ/1/1 ουρά, η Μ/Μ/1 ουρά, τροποποιήσεις της Μ/Μ/1 ουράς, η Μ/Μ/k ουρά, το μοντέλο με πεπερασμένο αριθμό δυνητικών πελατών, η διαδικασία αναχωρήσεων της M/M/1 ουράς.
3. Μαρκοβιανές Ουρές: η Μ/Μ/1 ουρά με ομαδικές αφίξεις, η Μ/Μ/1 ουρά με ομαδικές αναχωρήσεις, η M/M/k ουρά με ετερογενείς υπηρέτες, η M/M/1/1 ουρά με επαναπροσπάθειες, η Er/Es/1 ουρά και η μέθοδος των φάσεων.
4. Μαρκοβιανά δίκτυα ουρών: απλές Μαρκοβιανές ουρές σε σειρά, απλά δίκτυα Μαρκοβιανών ουρών, ανοικτά και κλειστά δίκτυα Jackson.

Σχέδιο Μαθήματος

Η ύλη αναπτύσσεται σε 2 δίωρα μαθήματα την εβδομάδα. Η κατανομή της ύλης ανά εβδομάδα αναμένεται να είναι περίπου ως εξής:

1. Βασικές έννοιες στα συστήματα εξυπηρέτησης. Συμβολισμός Kendall. Θεμελιώδεις στοχαστικές διαδικασίες και μέτρα απόδοσης. Γενική συνθήκη ευστάθειας. Εμφυτευμένες διαδικασίες μήκους ουράς σε στιγμές αφίξεων και αναχωρήσεων. Σχέση των κατανομών ισορροπίας των εμφυτευμένων διαδικασιών στην περίπτωση των μεμονωμένων αφίξεων και αναχωρήσεων. Η ιδιότητα PASTA.
2. Το θεώρημα Little. Εφαρμογές της ιδιότητας PASTA και του θεωρήματος Little για υπολογισμούς μέτρων απόδοσης. Επανάληψη βασικών εννοιών και αποτελεσμάτων από τη θεωρία των Μαρκοβιανών αλυσίδων συνεχούς χρόνου, εξισώσεις πλήρους και γενικευμένης ισορροπίας.
3. Απλές Μαρκοβιανές Ουρές: Ορισμοί και μορφή γινομένου της στάσιμης κατανομής. Η Μ/Μ/1/1 ουρά. Η Μ/Μ/1 ουρά: κατανομή πλήθους πελατών, κατανομή χρόνου παραμονής πελάτη στο σύστημα. Τροποποιήσεις της Μ/Μ/1 ουράς: γενική σχέση των κατανομών ισορροπίας σε συνεχή χρόνο, σε στιγμές αφίξεων και αναχωρήσεων, υπολογισμός μέσου ρυθμού αφίξεων και αναχωρήσεων και ποσοστού χαμένων πελατών σε συστήματα με απώλειες. Η Μ/Μ/1/s ουρά. Η Μ/Μ/1 ουρά με αποθαρρυνόμενους πελάτες.
4. H Μ/Μ/1 ουρά με μεταβλητό ρυθμό εξυπηρέτησης. Η Μ/Μ/k ουρά. Τροποποιήσεις της Μ/Μ/k ουράς: η M/M/k/s και η M/M/k/k ουρά. Το μοντέλο με πεπερασμένο αριθμό δυνητικών πελατών.
5. Η μέθοδος των πιθανογεννητριών για την εύρεση της στάσιμης κατανομής Μαρκοβιανών ουρών με πολλαπλές μεταβάσεις. Η Μ/Μ/1 ουρά με ομαδικές αφίξεις. Η ειδική περίπτωση της γεωμετρικής κατανομής για το μέγεθος των αφικνούμενων ομάδων. Η Μ/Μ/1 ουρά με ομαδικές αναχωρήσεις. Ασκήσεις.
6. Αντίστροφες στοχαστικές διαδικασίες. Αντιστρέψιμες Μαρκοβιανές αλυσίδες. Η διαδικασία αναχώρησης της Μ/Μ/1 ουράς. Η Μ/Μ/k ουρά με ετερογενείς υπηρέτες. Ασκήσεις.
7. Η Μ/Μ/1 ουρά με επαναπροσπάθειες. Ασκήσεις.
8. Η Er/Es/1 ουρά και η μέθοδος των φάσεων. H Ε2/Μ/1 ουρά. Η Ε2/Ε2/1/1 ουρά. Η M/Es/1 ουρά. Η Er/M/1 ουρά. Η M/Er/1/1 ουρά. Η M/E2/2/2 ουρά.
9. Εισαγωγή στα Μαρκοβιανά δίκτυα ουρών. Βασικοί συμβολισμοί. Πιθανοθεωρητική ανάλυση Μ/Μ/1 ουρών σε σειρά. Δίκτυα Jackson (ανοικτά και κλειστά). Στάσιμη κατανομή δικτύων Jackson. Άλλες κλάσεις Μαρκοβιανών δικτύων: δίκτυα με περιορισμένη χωρητικότητα και πρωτόκολλα παρεμπόδισης. Ασκήσεις.
10. Μαρκοβιανά συστήματα εξυπηρέτησης με ιδιαίτερα χαρακτηριστικά. Συστήματα με χρόνους εκκίνησης, συστήματα με υπηρέτες που υπόκεινται σε βλάβες και επισκευές, συστήματα με μεταβλητό αριθμό υπηρετών και πολιτικές υστέρησης για την ενεργοποίηση τους. Ασκήσεις.
11. Δομές αμοιβής-κόστους σε συστήματα εξυπηρέτησης και σχετικοί υπολογισμοί.
12. Εφαρμογές.
13. Ανασκόπηση του μαθήματος και επαναληπτικές ασκήσεις.