Μαθηματικά μοντέλα των απλούστερων συστημάτων ουράς. Οι συναρτήσεις p0(t) και p1(t) καθορίζουν τη διαδικασία μετάβασης σε ένα μονοκάναλο QS και περιγράφουν τη διαδικασία εκθετικής προσέγγισης του QS στην οριακή του κατάσταση με χαρακτηριστική χρονική σταθερά d

23 Οκτωβρίου 2013 στις 2:22 μ.μ

Squeak: Μοντελοποίηση Συστημάτων Ουρών

• Προγραμματισμός,
• OOP,
• Παράλληλος προγραμματισμός

Υπάρχουν πολύ λίγες πληροφορίες για το Habré σχετικά με μια τέτοια γλώσσα προγραμματισμού όπως το Squeak. Θα προσπαθήσω να μιλήσω για αυτό στο πλαίσιο της μοντελοποίησης συστημάτων ουράς. Θα σας δείξω πώς να γράψετε μια απλή τάξη, να εξηγήσετε τη δομή της και να τη χρησιμοποιήσετε σε ένα πρόγραμμα που θα εξυπηρετεί αιτήματα μέσω πολλών καναλιών.

Λίγα λόγια για το Squeak

Το Squeak είναι μια ανοιχτή υλοποίηση πολλαπλών πλατφορμών της γλώσσας προγραμματισμού Smalltalk-80 με δυναμική πληκτρολόγηση και συλλογή σκουπιδιών. Η διεπαφή είναι αρκετά συγκεκριμένη, αλλά αρκετά βολική για εντοπισμό σφαλμάτων και ανάλυση. Το Squeak ανταποκρίνεται πλήρως στην έννοια του OOP. Τα πάντα αποτελούνται από αντικείμενα, ακόμα και δομές αν-τότε-άλλο, για, ενώυλοποιούνται με τη βοήθειά τους. Ολόκληρη η σύνταξη καταλήγει στην αποστολή ενός μηνύματος στο αντικείμενο με τη μορφή:

<объект> <сообщение>

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

Συστήματα ουράς

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

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

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

Λίγα μαθηματικά

Για μια ροή Poisson, ο αριθμός των γεγονότων Χ, που εμπίπτει στο διάστημα μήκους τ (ταυ), παρακείμενο στο σημείο t, κατανεμημένο σύμφωνα με το νόμο του Poisson:
Οπου α(τ, τ)- μέσος αριθμός γεγονότων που συμβαίνουν κατά τη διάρκεια ενός χρονικού διαστήματος τ .
Ο μέσος αριθμός γεγονότων που συμβαίνουν ανά μονάδα χρόνου είναι λ(t). Επομένως, ο μέσος αριθμός γεγονότων σε ένα χρονικό διάστημα τ , δίπλα στη στιγμή του χρόνου t, θα ισούται με:

χρόνος Τανάμεσα σε δύο γεγονότα λ(t) = const = λκατανέμονται σύμφωνα με το νόμο:
Πυκνότητα κατανομής μιας τυχαίας μεταβλητής Τέχει τη μορφή:
Για να λάβετε ψευδοτυχαίες ακολουθίες Poisson χρονικών διαστημάτων t iλύσε την εξίσωση:
Οπου r i- ένας τυχαίος αριθμός ομοιόμορφα κατανεμημένος στο διάστημα.
Στην περίπτωσή μας αυτό δίνει την έκφραση:

Θα μπορούσαν να γραφτούν ολόκληροι τόμοι σε τυχαία παραγωγή αριθμών. Εδώ, για να δημιουργήσουμε ακέραιους αριθμούς ομοιόμορφα κατανεμημένους στο διάστημα, χρησιμοποιούμε τον ακόλουθο αλγόριθμο:
Οπου R i- άλλος ένας τυχαίος ακέραιος αριθμός.
R- κάποιο μεγάλο πρώτο αριθμό (για παράδειγμα 2311).
Q- ακέραιος - το ανώτερο όριο του διαστήματος, για παράδειγμα, 2 21 = 2097152.
rem- η πράξη απόκτησης του υπολοίπου από τη διαίρεση ακεραίων αριθμών.

Αρχική τιμή R0συνήθως ρυθμίζεται αυθαίρετα, για παράδειγμα, χρησιμοποιώντας μετρήσεις χρονοδιακόπτη:
Χρόνος σύνολοΔευτερόλεπτα
Για να λάβουμε αριθμούς ομοιόμορφα κατανεμημένους σε ένα διάστημα, χρησιμοποιούμε τον τελεστή γλώσσας:

Κατηγορία Rand

Για να λάβουμε τυχαίους αριθμούς ομοιόμορφα κατανεμημένους σε ένα διάστημα, δημιουργούμε μια κλάση - μια γεννήτρια πραγματικών αριθμών:

Float variableWordSubclass: #Rand "class name" instanceVariableNames: "" "instance variables" classVariableNames: "R" "class variables" pool Λεξικά: "" "γενικά λεξικά" Κατηγορία: "Δείγμα" "όνομα κατηγορίας"
Μέθοδοι:

"Initialization" init R:= Time totalSeconds.next "Επόμενος ψευδοτυχαίος αριθμός" επόμενο R:= (R * 2311 + 1) rem: 2097152. ^(R/2097152) asFloat
Για να ρυθμίσετε την αρχική κατάσταση του αισθητήρα, στείλτε ένα μήνυμα Rand init.
Για να λάβουμε τον επόμενο τυχαίο αριθμό στέλνουμε ραντ επόμενο.

Πρόγραμμα επεξεργασίας αιτήσεων

Λοιπόν, ως απλό παράδειγμα, ας κάνουμε τα εξής. Ας υποθέσουμε ότι πρέπει να μοντελοποιήσουμε την εξυπηρέτηση μιας κανονικής ροής αιτημάτων από μια πηγή με ένα τυχαίο χρονικό διάστημα μεταξύ των αιτημάτων. Υπάρχουν δύο κανάλια διαφορετικής απόδοσης, που σας επιτρέπουν να εξυπηρετείτε αιτήματα σε 2 και 7 μονάδες χρόνου, αντίστοιχα. Είναι απαραίτητο να καταχωρίσετε τον αριθμό των αιτημάτων που εξυπηρετούνται από κάθε κανάλι σε διάστημα 100 χρονικών μονάδων.

Κωδικός για Squeak

"Δήλωση προσωρινών μεταβλητών" | proc1 proc2 t1 t2 s1 s2 sysΟυρά προτεραιότητας συνέχεια r | "Αρχικές ρυθμίσεις μεταβλητής" Rand init. SysTime:= 0. s1:= 0. s2:= 0. t1:= -1. t2:= -1. συνέχεια:= αλήθεια. sysPriority:= Ενεργός επεξεργαστής Προτεραιότητα διαδικασίας. Ουρά "Τρέχουσα προτεραιότητα":= Σηματοφόρος νέος. "Μοντέλο ουράς αιτήματος" "Δημιουργία διεργασίας - μοντέλο καναλιού 1" (Διαδικασία forContext: [ proc1:= Processor activeProcess. whileTrue: "Service cycle" [ ουρά αναμονής. "Wait for request" t1:= SysTime + 2. "Επόμενη ενεργοποίηση time" s1:= s1 + 1. proc1 suspend. "Suspend the process ενώ περιμένει το τέλος της υπηρεσίας" ] proc1:= μηδέν. "Remove the reference to process 1" ] priority: (sysPriority + 1)) resume. "Η νέα προτεραιότητα είναι μεγαλύτερη από το φόντο" "Δημιουργία διεργασίας - μοντέλο καναλιού 2" (Διαδικασία forContext: [ proc2:= Processor activeProcess.. whileTrue: [ ουρά αναμονής. t2:= SysTime + 7. s2:= s2 + 1 . proc2 suspend. ] .proc2:= μηδέν. ] προτεραιότητα: (sysPriority + 1)) συνέχιση. "Συνέχεια της περιγραφής της κύριας διεργασίας και του μοντέλου πηγής" ενώ True: [ r:= (Rand next * 10) στρογγυλεμένο. (r = 0) αν Αληθές: . ((SysTime rem: r) = 0) ifTrue: . "Αποστολή αιτήματος" "Διακόπτης διαδικασίας υπηρεσίας" (t1 = SysTime) εάν True: . (t2 = SysTime) ifTrue: . SysTime:= SysTime + 1. "Η ώρα του μοντέλου χτυπά" ]. "Εμφάνιση κατάστασης μετρητή παραγγελιών" PopUpMenu ενημερώνει: "proc1: ",(s1 printString),", proc2: ",(s2 printString). συνέχεια:= ψευδής.

Κατά την εκκίνηση, βλέπουμε ότι η διαδικασία 1 κατάφερε να επεξεργαστεί 31 αιτήματα και η επεξεργασία 2 μόνο 11:

Ταξινόμηση, βασικές έννοιες, στοιχεία μοντέλου, υπολογισμός βασικών χαρακτηριστικών.

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

Κάθε QS περιλαμβάνει τέσσερα στοιχεία: εισερχόμενη ροή, ουρά, διακομιστής, εξερχόμενη ροή.

Απαίτηση(πελάτης, εφαρμογή) στο QS είναι κάθε μεμονωμένο αίτημα για την εκτέλεση οποιασδήποτε εργασίας.

Υπηρεσία- αυτή είναι η εκτέλεση της εργασίας για την ικανοποίηση της ληφθείσας απαίτησης. Το αντικείμενο που εκτελεί την εξυπηρέτηση των αιτημάτων ονομάζεται συσκευή εξυπηρέτησης (συσκευή) ή κανάλι εξυπηρέτησης.

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

Οι SMO ταξινομούνται σύμφωνα με διαφορετικά κριτήρια.

1. Με βάση τον αριθμό των καναλιών εξυπηρέτησης, τα QS χωρίζονται σε μονοκάναλα και πολυκάναλα.

2. Ανάλογα με τις συνθήκες αναμονής και την απαίτηση έναρξης σέρβις, γίνεται διάκριση μεταξύ QS με απώλειες (αστοχίες) και QS με αναμονή.

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

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

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

Για ένα QS με αναμονή, τα κύρια χαρακτηριστικά είναι οι μαθηματικές προσδοκίες του μήκους της ουράς και του χρόνου αναμονής.

Ένα παράδειγμα συστήματος αναμονής είναι η διαδικασία επαναφοράς τηλεοράσεων σε ένα συνεργείο επισκευής.

Υπάρχουν συστήματα που βρίσκονται μεταξύ αυτών των δύο ομάδων ( μικτό SMO). Χαρακτηρίζονται από την παρουσία ορισμένων ενδιάμεσων συνθηκών: περιορισμοί μπορεί να είναι περιορισμοί στον χρόνο αναμονής για την έναρξη της υπηρεσίας, στη διάρκεια της ουράς κ.λπ.

Τα χαρακτηριστικά απόδοσης μπορούν να εφαρμοστούν στην πιθανότητα αστοχίας τόσο σε συστήματα με απώλειες (ή χαρακτηριστικά καθυστέρησης) όσο και σε συστήματα αναμονής.

3. Σύμφωνα με την πειθαρχία συντήρησης, τα συστήματα QS χωρίζονται σε συστήματα με προτεραιότητα στη συντήρηση και σε συστήματα χωρίς προτεραιότητα στη συντήρηση.

Τα αιτήματα μπορούν να εξυπηρετηθούν με τη σειρά που λαμβάνονται, είτε τυχαία είτε βάσει καθορισμένων προτεραιοτήτων.

4. Το SMO μπορεί να είναι μονοφασικό και πολυφασικό.

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

5. Με βάση τη θέση της πηγής των απαιτήσεων, τα συστήματα QS χωρίζονται σε ανοιχτά (όταν η πηγή της απαίτησης είναι εκτός συστήματος) και κλειστά (όταν η πηγή βρίσκεται στο ίδιο το σύστημα).

ΠΡΟΣ ΤΗΝ κλειστόΑυτά περιλαμβάνουν συστήματα στα οποία η εισερχόμενη ροή των απαιτήσεων είναι περιορισμένη. Για παράδειγμα, ένας εργοδηγός του οποίου η αποστολή είναι να στήνει μηχανές σε ένα συνεργείο πρέπει περιοδικά να τις επισκευάζει. Κάθε προσαρμοσμένο μηχάνημα γίνεται μια πιθανή πηγή απαιτήσεων προσαρμογής στο μέλλον. Σε τέτοια συστήματα, ο συνολικός αριθμός των απαιτήσεων κυκλοφορίας είναι πεπερασμένος και τις περισσότερες φορές σταθερός.

Εάν η πηγή τροφοδοσίας έχει άπειρο αριθμό απαιτήσεων, τότε τα συστήματα καλούνται Άνοιξε. Παραδείγματα τέτοιων συστημάτων περιλαμβάνουν καταστήματα, εκδοτήρια εισιτηρίων σε σιδηροδρομικούς σταθμούς, λιμάνια κ.λπ. Για αυτά τα συστήματα, η εισερχόμενη ροή των απαιτήσεων μπορεί να θεωρηθεί απεριόριστη.

Οι μέθοδοι και τα μοντέλα για την έρευνα του QS μπορούν να χωριστούν σε αναλυτικά και στατιστικά (μοντελοποίηση προσομοίωσης διαδικασιών ουράς).

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

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

Επί του παρόντος, οι πιο ανεπτυγμένες θεωρητικά και βολικές σε πρακτικές εφαρμογές είναι οι μέθοδοι για την επίλυση προβλημάτων ουράς στις οποίες η ροή των απαιτήσεων είναι η απλούστερη ( Poisson).

Για την απλούστερη ροή, η συχνότητα άφιξης απαιτήσεων στο σύστημα υπακούει στο νόμο του Poisson, δηλαδή, η πιθανότητα άφιξης σε χρόνο t ίση με k απαιτήσεις δίνεται από τον τύπο:

όπου λ είναι η παράμετρος ροής (βλ. παρακάτω).

Η απλούστερη ροή έχει τρεις κύριες ιδιότητες: συνηθισμένη, ακίνητη και έλλειψη επακόλουθου αποτελέσματος.

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

Ακίνητοςπου ονομάζεται ροή, για το οποίο η μαθηματική προσδοκία του αριθμού των απαιτήσεων που εισέρχονται στο σύστημα ανά μονάδα χρόνου (που συμβολίζεται με λ) δεν αλλάζει με την πάροδο του χρόνου. Έτσι, η πιθανότητα να εισέλθει ένας συγκεκριμένος αριθμός απαιτήσεων στο σύστημα κατά τη διάρκεια μιας δεδομένης χρονικής περιόδου Δt εξαρτάται από την τιμή του και δεν εξαρτάται από την έναρξη της μέτρησής του στον άξονα του χρόνου.

Χωρίς επακόλουθοσημαίνει ότι ο αριθμός των αιτήσεων που λαμβάνονται στο σύστημα πριν από τη στιγμή t δεν καθορίζει πόσες αιτήσεις θα εισέλθουν στο σύστημα κατά τη διάρκεια του χρόνου t + Δt.

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

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

F(t) = 1 – e -μt ,

εκείνοι. η πιθανότητα ο χρόνος υπηρεσίας να μην υπερβαίνει μια ορισμένη τιμή t καθορίζεται από τον τύπο (1 – e -μt), όπου μ είναι η παράμετρος του εκθετικού νόμου του χρόνου υπηρεσίας για απαιτήσεις στο σύστημα - το αντίστροφο της μέσης υπηρεσίας χρόνος, δηλ. .

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

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

Η γενική διατύπωση του προβλήματος έχει ως εξής.

Το σύστημα αποτελείται από n κανάλια εξυπηρέτησης. Κάθε ένα από αυτά μπορεί να εξυπηρετήσει μόνο μία απαίτηση κάθε φορά. Το σύστημα λαμβάνει μια απλή (Poisson) ροή απαιτήσεων με παράμετρο λ. Εάν, τη στιγμή της άφιξης του επόμενου αιτήματος, υπάρχουν ήδη τουλάχιστον n αιτήματα στο σύστημα για σέρβις (δηλαδή, όλα τα κανάλια είναι απασχολημένα), τότε αυτό το αίτημα μπαίνει στην ουρά και περιμένει να ξεκινήσει η εξυπηρέτηση.

Ο χρόνος εξυπηρέτησης κάθε αιτήματος t about είναι μια τυχαία μεταβλητή που υπακούει σε έναν νόμο εκθετικής κατανομής με την παράμετρο μ.

Όπως σημειώθηκε παραπάνω, το QS με προσδοκία μπορεί να χωριστεί σε δύο μεγάλες ομάδες: κλειστές και ανοιχτές.

Οι ιδιαιτερότητες της λειτουργίας καθενός από αυτούς τους δύο τύπους συστημάτων επιβάλλουν τη δική τους απόχρωση στη μαθηματική συσκευή που χρησιμοποιείται. Ο υπολογισμός των χαρακτηριστικών λειτουργίας διαφόρων τύπων QS μπορεί να πραγματοποιηθεί με βάση τον υπολογισμό των πιθανοτήτων καταστάσεων QS (τύποι Erlang).

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

Ως κύρια κριτήρια που χαρακτηρίζουν την ποιότητα λειτουργίας του υπό εξέταση συστήματος, θα επιλέξουμε: 1) την αναλογία του μέσου μήκους της ουράς προς τον μεγαλύτερο αριθμό απαιτήσεων που βρίσκονται ταυτόχρονα στο σύστημα εξυπηρέτησης - το ποσοστό διακοπής λειτουργίας του εξυπηρετούμενου αντικειμένου. 2) η αναλογία του μέσου αριθμού καναλιών σε αδράνεια προς τον συνολικό αριθμό τους - η αναλογία αδράνειας του εξυπηρετούμενου καναλιού.

Ας εξετάσουμε τον υπολογισμό των απαραίτητων πιθανολογικών χαρακτηριστικών (δείκτες απόδοσης) ενός κλειστού QS.

1. Η πιθανότητα να υπάρχουν k απαιτήσεις στο σύστημα, με την προϋπόθεση ότι ο αριθμός τους δεν υπερβαίνει τον αριθμό των συσκευών εξυπηρέτησης n:

P k = α k P 0 , (1 ≤ k ≤ n),

Οπου

λ είναι η συχνότητα (ένταση) των απαιτήσεων που εισέρχονται στο σύστημα από μία πηγή.

Μέση διάρκεια εξυπηρέτησης ενός αιτήματος.

m είναι ο μεγαλύτερος δυνατός αριθμός απαιτήσεων που βρίσκονται ταυτόχρονα στο σύστημα εξυπηρέτησης.

n - αριθμός συσκευών εξυπηρέτησης.

P 0 είναι η πιθανότητα ότι όλες οι συσκευές σέρβις είναι δωρεάν.

2. Η πιθανότητα να υπάρχουν k απαιτήσεις στο σύστημα, με την προϋπόθεση ότι ο αριθμός τους είναι μεγαλύτερος από τον αριθμό των συσκευών εξυπηρέτησης:

P k = α k P 0 , (n ≤ k ≤ m),

Οπου

3. Η πιθανότητα να είναι δωρεάν όλες οι συσκευές σέρβις καθορίζεται από την κατάσταση

ως εκ τούτου,

4. Μέσος αριθμός αιτημάτων σε αναμονή για την έναρξη της υπηρεσίας (μέση διάρκεια ουράς):

5. Αίτημα αναμονής για το ποσοστό διακοπής λειτουργίας:

6. Πιθανότητα ότι όλες οι συσκευές σέρβις είναι απασχολημένες:

7. Μέσος αριθμός απαιτήσεων στο σύστημα εξυπηρέτησης (εξυπηρέτηση και αναμονή υπηρεσίας):

8. Ποσοστό πλήρους διακοπής λειτουργίας των απαιτήσεων συντήρησης και αναμονής συντήρησης:

9. Μέσος χρόνος διακοπής λειτουργίας ενός αιτήματος στην ουρά για εξυπηρέτηση:

10. Μέσος αριθμός συσκευών δωρεάν υπηρεσίας:

11. Αναλογία χρόνου διακοπής λειτουργίας των συσκευών εξυπηρέτησης:

12. Η πιθανότητα ότι ο αριθμός των αιτήσεων που περιμένουν για σέρβις είναι μεγαλύτερος από έναν ορισμένο αριθμό B (η πιθανότητα να υπάρχουν περισσότερες από B απαιτήσεις στην ουρά για εξυπηρέτηση):

Σε πολλούς τομείς της οικονομίας, των οικονομικών, της παραγωγής και της καθημερινής ζωής, τα συστήματα που εφαρμόζουν την επαναλαμβανόμενη εκτέλεση παρόμοιων εργασιών παίζουν σημαντικό ρόλο. Τέτοια συστήματα ονομάζονται συστήματα ουράς ( SMO ). Παραδείγματα QS είναι: τράπεζες διαφόρων τύπων, ασφαλιστικοί οργανισμοί, φορολογικές επιθεωρήσεις, ελεγκτικές υπηρεσίες, διάφορα συστήματα επικοινωνίας, συγκροτήματα φόρτωσης και εκφόρτωσης, βενζινάδικα, διάφορες επιχειρήσεις και οργανισμοί παροχής υπηρεσιών.

3.1.1 Γενικές πληροφορίες σχετικά με τα συστήματα αναμονής

Κάθε QS έχει σχεδιαστεί για να εξυπηρετεί (εκπληρώνει) μια συγκεκριμένη ροή εφαρμογών (απαιτήσεων) που φτάνουν στην είσοδο του συστήματος, κυρίως όχι τακτικά, αλλά σε τυχαίους χρόνους. Η εξυπηρέτηση των αιτήσεων επίσης δεν διαρκεί σταθερό, προκαθορισμένο χρόνο, αλλά τυχαίο, που εξαρτάται από πολλούς τυχαίους, ενίοτε άγνωστους σε εμάς, λόγους. Μετά την εξυπηρέτηση του αιτήματος, το κανάλι ελευθερώνεται και είναι έτοιμο να λάβει το επόμενο αίτημα. Η τυχαία φύση της ροής των εφαρμογών και ο χρόνος εξυπηρέτησής τους οδηγεί σε ανομοιόμορφο φόρτο εργασίας του QS. Σε ορισμένα χρονικά διαστήματα, οι αιτήσεις μπορεί να συσσωρεύονται στην είσοδο του QS, γεγονός που οδηγεί σε υπερφόρτωση του QS· σε ορισμένα άλλα χρονικά διαστήματα, όταν υπάρχουν ελεύθερα κανάλια (συσκευές εξυπηρέτησης) στην είσοδο του QS, δεν θα υπάρχει αιτήματα, που οδηγεί σε υποφόρτωση του QS, δηλ. στην αδράνεια των καναλιών του. Οι αιτήσεις που συσσωρεύονται στην είσοδο του QS είτε «μπαίνουν» στην ουρά, είτε για κάποιο λόγο δεν μπορούν να συνεχίσουν να μένουν στην ουρά, αφήνουν το QS αδιάθετο.

Το σχήμα 3.1 δείχνει το διάγραμμα QS.

Τα κύρια στοιχεία (χαρακτηριστικά) των συστημάτων ουράς είναι:

Μονάδα εξυπηρέτησης (μπλοκ),

Ροή εφαρμογών

Ουράεν αναμονή της υπηρεσίας (πειθαρχία στην ουρά).

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

Ρύζι. 3.1 Διάγραμμα συστήματος ουράς

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

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

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

1. Εμφάνιση αίτησης (απαίτησης) επίδοσης. Ο λόγος για την τυχαιότητα αυτού του συμβάντος είναι συχνά η μαζική φύση της ανάγκης για εξυπηρέτηση.

2. Λήξη εξυπηρέτησης της επόμενης αίτησης. Οι λόγοι για την τυχαιότητα αυτού του συμβάντος είναι τόσο η τυχαιότητα της έναρξης της υπηρεσίας όσο και η τυχαία διάρκεια της ίδιας της υπηρεσίας.

Αυτά τα τυχαία συμβάντα αποτελούν ένα σύστημα δύο ροών στο QS: τη ροή εισόδου των εφαρμογών για εξυπηρέτηση και τη ροή εξόδου των εξυπηρετούμενων εφαρμογών.

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

Κάθε QS, ανάλογα με τις παραμέτρους του για τη φύση της ροής των εφαρμογών, τον αριθμό των καναλιών εξυπηρέτησης και την παραγωγικότητά τους, και τους κανόνες οργάνωσης της εργασίας, έχει μια συγκεκριμένη λειτουργική αποτελεσματικότητα (throughput) που του επιτρέπει να αντιμετωπίσει με επιτυχία τη ροή εφαρμογές.

Ειδικό πεδίο εφαρμοσμένων μαθηματικών θεωρία της μάζαςσυντήρηση (TMO)– ασχολείται με την ανάλυση διεργασιών σε συστήματα ουράς. Το αντικείμενο μελέτης της θεωρίας της ουράς είναι το QS.

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

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

Ως χαρακτηριστικά της αποτελεσματικότητας του συστήματος QS επιλέγονται συνήθως οι ακόλουθες τρεις κύριες ομάδες δεικτών (συνήθως μέσοι όροι):

Δείκτες αποτελεσματικότητας της χρήσης QS:

Η απόλυτη χωρητικότητα του QS είναι ο μέσος αριθμός αιτημάτων που μπορεί να εξυπηρετήσει το QS ανά μονάδα χρόνου.

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

Μέση διάρκεια της περιόδου απασχόλησης της ΚΟΑ.

Το ποσοστό χρήσης QS είναι το μέσο μερίδιο του χρόνου κατά το οποίο το QS είναι απασχολημένο με αιτήματα εξυπηρέτησης κ.λπ.

Δείκτες ποιότητας για αιτήματα εξυπηρέτησης:

Μέσος χρόνος αναμονής για μια εφαρμογή στην ουρά.

Μέσος χρόνος παραμονής μιας αίτησης στον ΚΟΑ.

Η πιθανότητα να απορριφθεί η εξυπηρέτηση ενός αιτήματος χωρίς αναμονή.

Η πιθανότητα μια ληφθείσα αίτηση να γίνει άμεσα αποδεκτή για επίδοση.

Ο νόμος της κατανομής του χρόνου που μια εφαρμογή μένει στην ουρά.

Ο νόμος κατανομής του χρόνου παραμονής μιας αίτησης στο QS.

Ο μέσος αριθμός εφαρμογών στην ουρά.

Μέσος αριθμός αιτήσεων στην ΚΟΑ κ.λπ.

Δείκτες της αποτελεσματικότητας του ζεύγους «SMO - καταναλωτής», όπου «καταναλωτής» νοείται ως ολόκληρο το σύνολο των εφαρμογών ή ορισμένες από αυτές

Οι λειτουργίες ή η αποτελεσματικότητα του συστήματος αναμονής είναι οι εξής.

Για QS με αστοχίες:

Για SMO με απεριόριστη αναμονήΤόσο η απόλυτη όσο και η σχετική απόδοση χάνουν το νόημά τους, αφού κάθε εισερχόμενο αίτημα αργά ή γρήγορα θα εξυπηρετηθεί. Για ένα τέτοιο QS, οι σημαντικοί δείκτες είναι:

Για Μικτού τύπου QSχρησιμοποιούνται και οι δύο ομάδες δεικτών: τόσο σχετικοί όσο και απόλυτη απόδοσηκαι χαρακτηριστικά της προσδοκίας.

Ανάλογα με το σκοπό της λειτουργίας ουράς, οποιοσδήποτε από τους συγκεκριμένους δείκτες (ή ένα σύνολο δεικτών) μπορεί να επιλεγεί ως κριτήριο αποτελεσματικότητας.

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

Δεν υπάρχει γενικό αναλυτικό μοντέλο για ένα αυθαίρετο QS. Αναλυτικά μοντέλα έχουν αναπτυχθεί για περιορισμένο αριθμό ειδικών περιπτώσεων QS. Τα αναλυτικά μοντέλα που αντικατοπτρίζουν λίγο πολύ με ακρίβεια πραγματικά συστήματα είναι συνήθως πολύπλοκα και δύσκολο να απεικονιστούν.

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

Ας δούμε παραδείγματα μερικών QS.

2.5.1. Πολυκαναλικό QS με βλάβες

Παράδειγμα 2.5. Τρεις επιθεωρητές τροχαίας ελέγχουν τις φορτωτικές των οδηγών φορτηγών. Εάν τουλάχιστον ένας επιθεωρητής είναι ελεύθερος, το διερχόμενο φορτηγό σταματά. Εάν όλοι οι επιθεωρητές είναι απασχολημένοι, το φορτηγό περνάει χωρίς να σταματήσει. Η ροή των φορτηγών είναι απλή, ο χρόνος ελέγχου είναι τυχαίος με εκθετική κατανομή.

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

Περιγραφή πολιτειών:

Όλοι οι επιθεωρητές είναι ελεύθεροι.

Ένας επιθεωρητής είναι απασχολημένος.

Δύο επιθεωρητές είναι απασχολημένοι.

Τρεις επιθεωρητές είναι απασχολημένοι.

Το γράφημα κατάστασης συστήματος φαίνεται στο Σχ. 2.11.

Ρύζι. 2.11.

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

Πραγματοποιείται προσομοίωση για τον προσδιορισμό του τμήματος των οχημάτων που δεν θα δοκιμαστούν.

Λύση

Το απαιτούμενο μέρος της πιθανότητας είναι η πιθανότητα απασχόλησης και των τριών επιθεωρητών. Εφόσον το γράφημα κατάστασης αντιπροσωπεύει ένα τυπικό σχήμα «θάνατος και αναπαραγωγής», θα βρούμε τη χρήση εξαρτήσεων (2.2).

Η ικανότητα διεκπεραίωσης αυτής της θέσης επιθεωρητή κυκλοφορίας μπορεί να χαρακτηριστεί σχετική απόδοση:

Παράδειγμα 2.6. Για τη λήψη και επεξεργασία εκθέσεων από την ομάδα αναγνώρισης, ορίστηκε ομάδα τριών αξιωματικών στο τμήμα πληροφοριών του συλλόγου. Η αναμενόμενη ένταση της ροής των αναφορών είναι 15 αναφορές ανά ώρα. Ο μέσος χρόνος για την επεξεργασία μιας αναφοράς από έναν αξιωματικό είναι . Κάθε αξιωματικός μπορεί να λάβει αναφορές από οποιαδήποτε ομάδα αναγνώρισης. Ο απελευθερωμένος αξιωματικός επεξεργάζεται την τελευταία από τις ληφθείσες αναφορές. Οι εισερχόμενες αναφορές πρέπει να υποβάλλονται σε επεξεργασία με πιθανότητα τουλάχιστον 95%.

Προσδιορίστε εάν η ομάδα των τριών αξιωματικών στην οποία έχει ανατεθεί είναι επαρκής για την ολοκλήρωση της αποστολής που της έχει ανατεθεί.

Λύση

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

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

Η περιγραφή των καταστάσεων και το γράφημα καταστάσεων του QS θα είναι παρόμοια με αυτά που δίνονται στο παράδειγμα 2.5.

Δεδομένου ότι το γράφημα κατάστασης είναι ένα σχήμα «θανάτου και αναπαραγωγής», υπάρχουν έτοιμες εκφράσεις για τις περιοριστικές πιθανότητες της κατάστασης:

Η στάση λέγεται δεδομένης της έντασης της ροής των αιτήσεων. Η φυσική του σημασία είναι η εξής: η τιμή αντιπροσωπεύει τον μέσο αριθμό αιτημάτων που φτάνουν στο QS κατά τη διάρκεια του μέσου χρόνου εξυπηρέτησης ενός αιτήματος.

Στο παράδειγμα .

Στο υπό εξέταση QS, μια αποτυχία συμβαίνει όταν και τα τρία κανάλια είναι απασχολημένα, δηλαδή. Επειτα:

Επειδή πιθανότητα αποτυχίαςκατά την επεξεργασία των αναφορών είναι περισσότερο από 34% (), τότε είναι απαραίτητο να αυξηθεί το προσωπικό του ομίλου. Ας διπλασιάσουμε τη σύνθεση του γκρουπ, δηλαδή ο ΚΟΑ θα έχει πλέον έξι κανάλια, και ας υπολογίσουμε:

Έτσι, μόνο μια ομάδα έξι αξιωματικών θα μπορεί να επεξεργάζεται εισερχόμενες αναφορές με πιθανότητα 95%.

2.5.2. Πολυκαναλικό QS με αναμονή

Παράδειγμα 2.7. Στο τμήμα διέλευσης του ποταμού υπάρχουν 15 παρόμοιες εγκαταστάσεις διέλευσης. Η ροή του εξοπλισμού που φτάνει στη διάβαση είναι κατά μέσο όρο 1 μονάδα/λεπτό, ο μέσος χρόνος για τη διέλευση μιας μονάδας εξοπλισμού είναι 10 λεπτά (συμπεριλαμβανομένης της επιστροφής του οχήματος διέλευσης).

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

Λύση

Απόλυτη απόδοση, δηλαδή οτιδήποτε πλησιάζει στη διάβαση πρακτικά διασταυρώνεται αμέσως.

Μέσος αριθμός λειτουργικών εγκαταστάσεων διέλευσης:

Χρεώσεις χρήσης πλοίων και διακοπής λειτουργίας:

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

Τα ποσοστά χρήσης της διέλευσης μετά από 50 διαδρομές είναι σχεδόν τα ίδια: .

ΕΙΣΑΓΩΓΗ

ΚΕΦΑΛΑΙΟ Ι. ΔΙΑΜΟΡΦΩΣΗ ΠΡΟΒΛΗΜΑΤΩΝ ΥΠΗΡΕΣΙΑΣ ΟΥΡΑΣ

1.1 Γενική έννοια της θεωρίας αναμονής

1.2 Μοντελοποίηση συστημάτων ουράς

1.3 Γραφήματα καταστάσεων QS

1.4 Τυχαίες διαδικασίες

Κεφάλαιο II. ΕΞΙΣΩΣΕΙΣ ΠΟΥ ΠΕΡΙΓΡΑΦΟΥΝ ΣΥΣΤΗΜΑΤΑ ΟΥΡΩΝ

2.1 Εξισώσεις Kolmogorov

2.2 Διαδικασίες «γέννησης – θανάτου»

2.3 Οικονομική και μαθηματική διατύπωση προβλημάτων ουράς

Κεφάλαιο III. ΜΟΝΤΕΛΑ ΣΥΣΤΗΜΑΤΩΝ ΟΥΡΩΝ

3.1 Μονοκαναλικό QS με άρνηση υπηρεσίας

3.2 Πολυκαναλικό QS με άρνηση εξυπηρέτησης

3.3 Μοντέλο πολυφασικού συστήματος τουριστικής εξυπηρέτησης

3.4 Μονοκάναλο QS με περιορισμένο μήκος ουράς

3.5 Μονοκάναλο QS με απεριόριστη ουρά

3.6 Πολυκαναλικό QS με περιορισμένο μήκος ουράς

3.7 Πολυκαναλικό QS με απεριόριστη ουρά

3.8 Ανάλυση του συστήματος ουράς σούπερ μάρκετ

ΣΥΜΠΕΡΑΣΜΑ

Εισαγωγή

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

Η θεωρία της ουράς βασίζεται στη θεωρία πιθανοτήτων και στη μαθηματική στατιστική. Η αρχική ανάπτυξη της θεωρίας της ουράς συνδέεται με το όνομα του Δανό επιστήμονα A.K. Erlang (1878-1929), με έργα του στον τομέα του σχεδιασμού και της λειτουργίας τηλεφωνικών κέντρων.

Η θεωρία ουρών είναι ένα πεδίο των εφαρμοσμένων μαθηματικών που ασχολείται με την ανάλυση διαδικασιών σε συστήματα παραγωγής, υπηρεσιών και διαχείρισης στα οποία ομοιογενή γεγονότα επαναλαμβάνονται πολλές φορές, για παράδειγμα, σε επιχειρήσεις εξυπηρέτησης καταναλωτών. σε συστήματα λήψης, επεξεργασίας και μετάδοσης πληροφοριών· αυτόματες γραμμές παραγωγής κλπ. Μεγάλη συμβολή στην ανάπτυξη αυτής της θεωρίας είχαν οι Ρώσοι μαθηματικοί A.Ya. Khinchin, B.V. Gnedenko, A.N. Kolmogorov, E.S. Οι Wentzel et al.

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

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

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

Κεφάλαιο Εγώ . Ρύθμιση εργασιών ουράς

1.1 Γενική έννοια της θεωρίας ουρών

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

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

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

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

Τα προβλήματα που αναφέρονται μπορούν να επιλυθούν με επιτυχία χρησιμοποιώντας μεθόδους και μοντέλα θεωρίας ουρών (QST) που έχουν δημιουργηθεί ειδικά για αυτούς τους σκοπούς. Αυτή η θεωρία εξηγεί ότι είναι απαραίτητο να εξυπηρετηθεί κάποιος ή κάτι, το οποίο ορίζεται από την έννοια του «αίτημα υπηρεσίας (ζήτηση)», και οι λειτουργίες εξυπηρέτησης εκτελούνται από κάποιον ή κάτι που ονομάζονται κανάλια εξυπηρέτησης (κόμβοι). Ο ρόλος των αιτημάτων στις εμπορικές δραστηριότητες παίζεται από αγαθά, επισκέπτες, χρήματα, ελεγκτές, έγγραφα και τον ρόλο των καναλιών εξυπηρέτησης παίζουν πωλητές, διαχειριστές, μάγειρες, ζαχαροπλάστες, σερβιτόροι, ταμίες, εμπειρογνώμονες εμπορευμάτων, φορτωτές, εμπορικός εξοπλισμός κ.λπ. Είναι σημαντικό να σημειωθεί ότι σε μια υλοποίηση, για παράδειγμα, ένας μάγειρας στη διαδικασία προετοιμασίας των πιάτων είναι ένα κανάλι εξυπηρέτησης και σε μια άλλη ενεργεί ως αίτημα για σέρβις, για παράδειγμα προς τον διευθυντή παραγωγής για να παραλάβει αγαθά.

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

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

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

Πράγματι, η διάρκεια παραμονής ενός αγοραστή σε ένα σούπερ μάρκετ εξαρτάται, αφενός, από τις προσωπικές ιδιότητες του αγοραστή, τα αιτήματά του, από το εύρος των προϊόντων που πρόκειται να αγοράσει και, αφετέρου, από τη μορφή της οργάνωσης υπηρεσιών και του προσωπικού εξυπηρέτησης, γεγονός που μπορεί να επηρεάσει σημαντικά την παραμονή του αγοραστή.στο σούπερ μάρκετ και την ένταση εξυπηρέτησης. Για παράδειγμα, η γνώση της «τυφλής» μεθόδου εργασίας σε ταμειακή μηχανή από ταμίες-ελεγκτές επέτρεψε να αυξηθεί η απόδοση των κόμβων πληρωμής κατά 1,3 φορές και να εξοικονομηθεί ο χρόνος που δαπανάται σε διακανονισμούς με πελάτες σε κάθε ταμειακή μηχανή κατά περισσότερο από 1,5 ώρες ανά μέρα. Η εισαγωγή ενός ενιαίου κέντρου πληρωμών σε ένα σούπερ μάρκετ παρέχει απτά οφέλη στον αγοραστή. Έτσι, εάν με τον παραδοσιακό τρόπο πληρωμής ο χρόνος για την εξυπηρέτηση ενός πελάτη ήταν κατά μέσο όρο 1,5 λεπτό, τότε με την εισαγωγή μιας ενιαίας μονάδας πληρωμής ήταν 67 δευτερόλεπτα. Από αυτά, 44 δευτερόλεπτα δαπανώνται για την πραγματοποίηση μιας αγοράς στην ενότητα και 23 δευτερόλεπτα απευθείας για πληρωμές για αγορές. Εάν ο αγοραστής κάνει πολλές αγορές σε διαφορετικά τμήματα, τότε η απώλεια χρόνου μειώνεται κατά την αγορά δύο αγορών κατά 1,4 φορές, τρεις κατά 1,9, πέντε κατά 2,9 φορές.

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

Εάν τα κανάλια υπηρεσίας είναι ικανά να ικανοποιήσουν τα ίδια αιτήματα, τότε τα κανάλια εξυπηρέτησης ονομάζονται ομοιογενή. Ένα σύνολο ομοιογενών καναλιών εξυπηρέτησης ονομάζεται σύστημα εξυπηρέτησης.

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