Εισαγωγή στη θεωρία των ουρών

Η θεωρία των ουρών είναι η μαθηματική μελέτη της ουράς αναμονής ή της αναμονής σε γραμμές. Οι ουρές περιέχω οι πελάτες (ή "αντικείμενα"), όπως άτομα, αντικείμενα ή πληροφορίες. Οι ουρές αποτελούν όταν υπάρχουν περιορισμένοι πόροι για την παροχή ενός υπηρεσία. Για παράδειγμα, εάν υπάρχουν 5 ταμειακές μηχανές σε ένα παντοπωλείο, θα δημιουργηθούν ουρές εάν περισσότεροι από 5 πελάτες επιθυμούν να πληρώσουν τα στοιχεία τους ταυτόχρονα.

Μια βασική σύστημα αναμονής αποτελείται από μια διαδικασία άφιξης (πώς φτάνουν οι πελάτες στην ουρά, πόσοι πελάτες υπάρχουν σύνολο), η ίδια η ουρά, η διαδικασία εξυπηρέτησης αυτών των πελατών και οι αναχωρήσεις από το Σύστημα.

Μαθηματικός μοντέλα αναμονής χρησιμοποιούνται συχνά στο λογισμικό και τις επιχειρήσεις για να καθορίσουν τον καλύτερο τρόπο χρήσης περιορισμένων πόρων. Τα μοντέλα ουράς μπορεί να απαντήσουν σε ερωτήματα όπως: Ποια είναι η πιθανότητα ότι ένας πελάτης θα περιμένει 10 λεπτά στη σειρά; Ποιος είναι ο μέσος χρόνος αναμονής ανά πελάτη;

Οι ακόλουθες περιπτώσεις είναι παραδείγματα για το πώς μπορεί να εφαρμοστεί η θεωρία ουρών:

• Αναμονή σε σειρά σε τράπεζα ή κατάστημα
• Αναμονή για έναν εκπρόσωπο εξυπηρέτησης πελατών να απαντήσει σε μια κλήση αφού τεθεί σε αναμονή η κλήση
• Περιμένοντας να έρθει ένα τρένο
• Αναμονή για έναν υπολογιστή να εκτελέσει μια εργασία ή να απαντήσει
• Αναμονή για αυτόματο πλυντήριο αυτοκινήτων για να καθαρίσετε μια σειρά αυτοκινήτων

Τα μοντέλα ουράς αναλύουν τον τρόπο με τον οποίο οι πελάτες (συμπεριλαμβανομένων των ατόμων, των αντικειμένων και των πληροφοριών) λαμβάνουν μια υπηρεσία. Ένα σύστημα αναμονής περιλαμβάνει:

• Διαδικασία άφιξης. Η διαδικασία άφιξης είναι απλά ο τρόπος με τον οποίο φθάνουν οι πελάτες. Μπορούν να έρθουν σε ουρά μόνο ή σε ομάδες, και μπορεί να φτάσουν σε ορισμένα χρονικά διαστήματα ή τυχαία.
• η ΣΥΜΠΕΡΙΦΟΡΑ. Πώς συμπεριφέρονται οι πελάτες όταν ευθυγραμμίζονται; Κάποιοι μπορεί να είναι πρόθυμοι να περιμένουν τη θέση τους στην ουρά. άλλοι μπορεί να γίνουν ανυπόμονοι και να φύγουν. Ωστόσο, άλλοι ενδέχεται να αποφασίσουν να επανέλθουν στην ουρά αργότερα, όπως όταν τεθούν σε αναμονή με την εξυπηρέτηση πελατών και αποφασίσουν να καλέσουν ξανά με την ελπίδα ότι θα λάβουν ταχύτερη εξυπηρέτηση.
• Πώς εξυπηρετούνται οι πελάτες. Αυτό περιλαμβάνει το χρονικό διάστημα που ο πελάτης εξυπηρετείται, ο αριθμός εξυπηρετητών που είναι διαθέσιμοι για να βοηθήσουν τους πελάτες, είτε οι πελάτες εξυπηρετούνται μία προς μία είτε σε παρτίδες, καθώς και η σειρά με την οποία εξυπηρετούνται οι πελάτες, που ονομάζονται επίσης υπηρεσία πειθαρχίας.
• Η πειθαρχία των υπηρεσιών αναφέρεται στον κανόνα με τον οποίο επιλέγεται ο επόμενος πελάτης. Παρόλο που πολλά σενάρια λιανικής πώλησης χρησιμοποιούν τον κανόνα "έρχονται πρώτα, εξυπηρετούνται για πρώτη φορά", άλλες καταστάσεις ενδέχεται να απαιτούν άλλους τύπους υπηρεσιών. Για παράδειγμα, οι πελάτες μπορούν να εξυπηρετούνται κατά σειρά προτεραιότητας ή βάσει του αριθμού των αντικειμένων που χρειάζονται συντήρηση (όπως σε μια ρητή λωρίδα σε ένα μπακάλικο). Μερικές φορές, ο τελευταίος πελάτης που θα φτάσει θα εξυπηρετηθεί πρώτα (όπως στην περίπτωση μιας στοίβας από βρώμικα πιάτα, όπου η κορυφή θα είναι η πρώτη που πλένεται).
• Αίθουσα αναμονής. Ο αριθμός των πελατών που επιτρέπεται να περιμένουν στην ουρά ενδέχεται να είναι περιορισμένος βάσει του διαθέσιμου χώρου.

Η σημείωση του Kendall είναι μια συντομογραφία που καθορίζει τις παραμέτρους ενός βασικού μοντέλου ουράς. Η σημείωση του Kendall γράφεται με τη μορφή A / S / c / B / N / D, όπου κάθε ένα από τα γράμματα αντιπροσωπεύει διαφορετικές παραμέτρους.

• Ο όρος Α περιγράφει πότε φθάνουν οι πελάτες στην ουρά - ειδικότερα, ο χρόνος μεταξύ αφίξεων ή διαχρονικούς χρόνους. Μαθηματικά, αυτή η παράμετρος καθορίζει το κατανομή πιθανότητας ότι ακολουθούν οι εποχές του διακονισμού. Μια κοινή κατανομή πιθανότητας που χρησιμοποιείται για τον όρο Α είναι η Διανομή Poisson.
• Ο όρος S περιγράφει το χρόνο που χρειάζεται ο πελάτης για την εξυπηρέτησή του αφού εγκαταλείψει την ουρά. Μαθηματικά, αυτή η παράμετρος καθορίζει την κατανομή πιθανότητας αυτών χρόνους εξυπηρέτησης ακολουθηστε. Η κατανομή Poisson χρησιμοποιείται επίσης συνήθως για τον όρο S.
• Ο όρος c ορίζει τον αριθμό των εξυπηρετητών στο σύστημα αναμονής. Το μοντέλο υποθέτει ότι όλοι οι διακομιστές στο σύστημα είναι ίδιοι, έτσι ώστε να μπορούν να περιγραφούν όλοι από τον όρο S παραπάνω.
• Ο όρος Β ορίζει τον συνολικό αριθμό στοιχείων που μπορεί να υπάρχουν στο σύστημα και περιλαμβάνει στοιχεία που βρίσκονται ακόμα στην ουρά και αυτά που εξυπηρετούνται. Αν και πολλά συστήματα στον πραγματικό κόσμο έχουν περιορισμένη χωρητικότητα, το μοντέλο είναι ευκολότερο να αναλυθεί αν αυτή η χωρητικότητα θεωρείται άπειρη. Συνεπώς, αν η χωρητικότητα ενός συστήματος είναι αρκετά μεγάλη, το σύστημα θεωρείται συνήθως άπειρο.
• Ο όρος N προσδιορίζει τον συνολικό αριθμό δυνητικών πελατών - δηλ. Τον αριθμό των πελατών που θα μπορούσαν ποτέ να εισέλθουν στο σύστημα αναμονής - οι οποίοι μπορεί να θεωρηθούν πεπερασμένοι ή άπειροι.
• Ο όρος D καθορίζει την πειθαρχία της υπηρεσίας του συστήματος ουράς, όπως το πρώτο έρχονται, το πρώτο σερβίρισμα ή το last-in-first-out.

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

• Στη μαθηματική μνεία, ο νόμος του Μικρού είναι: L = λW
• L είναι ο μέσος αριθμός στοιχείων, λ είναι ο μέσος ρυθμός άφιξης των στοιχείων στο σύστημα αναμονής και W είναι ο μέσος χρόνος που τα στοιχεία δαπανώνται στο σύστημα αναμονής.
• Ο νόμος του Little υποθέτει ότι το σύστημα βρίσκεται σε «σταθερή κατάσταση» - οι μαθηματικές μεταβλητές που χαρακτηρίζουν το σύστημα δεν αλλάζουν με την πάροδο του χρόνου.

Αν και ο νόμος του Little έχει μόνο τρεις εισροές, είναι αρκετά γενική και μπορεί να εφαρμοστεί σε πολλούς συστήματα αναμονής, ανεξάρτητα από τους τύπους των στοιχείων στην ουρά ή τον τρόπο επεξεργασίας των στοιχείων στο Ουρά. Ο νόμος του Little μπορεί να είναι χρήσιμος για την ανάλυση του τρόπου με τον οποίο έχει εκτελεστεί μια ουρά σε κάποιο χρονικό διάστημα ή για να μετρήσει γρήγορα τον τρόπο με τον οποίο εκτελείται αυτή τη στιγμή μια ουρά.

Για παράδειγμα: μια εταιρεία shoebox θέλει να καταλάβει τον μέσο αριθμό παπουτσιών που αποθηκεύονται σε μια αποθήκη. Η εταιρεία γνωρίζει ότι ο μέσος όρος άφιξης των κιβωτίων στην αποθήκη είναι 1.000 παπούτσια / έτος και ότι ο μέσος χρόνος που περνούν στην αποθήκη είναι περίπου 3 μήνες ή ¼ του χρόνου. Έτσι, ο μέσος αριθμός κουτιών παπουτσιών στην αποθήκη δίνεται από (1000 παπούτσια / έτος) x (¼ έτος) ή 250 παπούτσια.

• Η θεωρία των ουρών είναι η μαθηματική μελέτη της ουράς αναμονής ή της αναμονής σε γραμμές.
• Οι ουρές περιέχουν "πελάτες" όπως άτομα, αντικείμενα ή πληροφορίες. Οι ουρές αποτελούν όταν υπάρχουν περιορισμένοι πόροι για την παροχή μιας υπηρεσίας.
• Η θεωρία των ουρών μπορεί να εφαρμοστεί σε καταστάσεις που κυμαίνονται από την αναμονή σε σειρά στο κατάστημα παντοπωλείων έως την αναμονή ενός υπολογιστή να εκτελέσει μια εργασία. Συχνά χρησιμοποιείται σε λογισμικό και επιχειρηματικές εφαρμογές για να καθορίσει τον καλύτερο τρόπο χρήσης περιορισμένων πόρων.
• Η σημείωση του Kendall μπορεί να χρησιμοποιηθεί για τον προσδιορισμό των παραμέτρων ενός συστήματος αναμονής.
• Ο νόμος του Little είναι μια απλή, αλλά γενική έκφραση που μπορεί να παρέχει μια γρήγορη εκτίμηση του μέσου αριθμού των στοιχείων σε μια ουρά.

• Beasley, J. ΜΙ. "Η θεωρία των ουρών."
• Boxma, Ο. J. "Στοχαστική μοντελοποίηση επιδόσεων." 2008.
• Lilja, D. Μέτρηση της απόδοσης του υπολογιστή: Ένας οδηγός πρακτικής, 2005.
• Little, J., and Graves, S. "Κεφάλαιο 5: Ο νόμος του Μικρού." Σε Διαλογιστική δομή: Στοιχεία από τα βασικά μοντέλα και αρχές διαχείρισης λειτουργιών. Springer Science + Business Media, 2008.
• Mulholland, Β. "Νόμος του μικρού: Πώς να αναλύσετε τις διαδικασίες σας (με βομβαρδιστικά stealth)."Process.st, 2017.