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

Βασικές παράμετροι του διαγράμματος δικτύου

Οι κύριες παράμετροι του διαγράμματος δικτύου είναι:

κρίσιμο μονοπάτι

Αποθεματικά χρόνου για την ολοκλήρωση των εκδηλώσεων

Αποθέματα χρόνου για την εκτέλεση εργασιών

Μονοπάτι - μια ακολουθία εργασιών στην οποία το συμβάν λήξης μιας εργασίας συμπίπτει με το συμβάν έναρξης μιας άλλης.

Πλήρης διαδρομή - ένα μονοπάτι, η αρχή του οποίου είναι το αρχικό γεγονός και το τέλος είναι το τελικό.

Η διάρκεια, το μήκος της διαδρομής, ισούται με το άθροισμα των διάρκειων της εργασίας. Τα συστατικά του.

κρίσιμο μονοπάτι - πλήρης διαδρομή. τη μεγαλύτερη από όλες τις διαδρομές του διαγράμματος δικτύου από το αρχικό συμβάν (I) έως το τελικό (C).

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

Τα πλήρη μονοπάτια μπορούν να πάνε έξω από το κρίσιμο ή να συμπίπτουν εν μέρει με αυτό. Αυτά τα μικρότερα ταξίδια ονομάζονται χαλαρή.Τα χαρακτηριστικά τους είναι. Ότι έχουν αποθέματα χρόνου. Η κρίσιμη διαδρομή δεν είναι. Για κάθε i-ο γεγονός καθορίζεται:

tpi– πρώιμη έναρξη- τον ελάχιστο δυνατό χρόνο εμφάνισης αυτού του συμβάντος για δεδομένη διάρκεια εργασίας.

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

R i – χαλαρό για μια εκδήλωση- το χρονικό διάστημα για το οποίο μπορεί να καθυστερήσει η έναρξη αυτού του συμβάντος χωρίς να παραβιαστεί ο χρόνος ανάπτυξης του σχεδιαζόμενου συγκροτήματος στο σύνολό του. Ορίζεται ως η διαφορά μεταξύ αργά ( t p i) και νωρίς ( t p i) το χρονοδιάγραμμα ολοκλήρωσης αυτής της εκδήλωσης.

Τα αποθέματα ενός γεγονότος στην κρίσιμη διαδρομή είναι ίσα με μηδέν, αφού σε αυτό t p i =t p i

Για κάθε έργο tij) ορίζεται:

ημερομηνία πρόωρης έναρξης (π.μ. ij)- τον ελάχιστο δυνατό χρόνο για την έναρξη αυτής της εργασίας.

ημερομηνία πρόωρης λήξης (t p.o. ij)- την ελάχιστη δυνατή προθεσμία για την ολοκλήρωση αυτής της εργασίας, για δεδομένη διάρκεια εργασίας

καθυστερημένη ημερομηνία έναρξης (t b.s. ij)- το μέγιστο των επιτρεπόμενων ημερομηνιών για την έναρξη αυτής της εργασίας

καθυστερημένη ημερομηνία λήξης (t p.o. ij)- το μέγιστο των επιτρεπόμενων προθεσμιών για την ολοκλήρωση αυτής της εργασίας, κατά τις οποίες είναι ακόμη δυνατή η εκτέλεση των ακόλουθων εργασιών, σύμφωνα με την καθορισμένη προθεσμία για την εμφάνιση του τελικού συμβάντος.

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

t r.n. ij = t p i

t r.o. ij = t p i + t ij

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

t p.o. ij = t p j

τ α.σ. ij = t p j – t ij

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

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

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

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

3.Υπολογισμός μοντέλων δικτύου

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

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

Ο ανώτερος τομέας είναι το απόθεμα χρόνου για την εμφάνιση του γεγονότος R i

αριστερός τομέας - πρώιμη ημερομηνία της εκδήλωσης tpi

δεξιός τομέας - η καθυστερημένη ημερομηνία του συμβάντος t p i

κάτω - αριθμός συμβάντος

Μέθοδος υπολογισμού παραμέτρων

1) Πρώιμος χρονισμός των γεγονότων . Η πρώιμη ημερομηνία ολοκλήρωσης του αρχικού (πρώτου ή μηδενικού) συμβάντος λαμβάνεται ίση με μηδέν. Οι πρώιμες ημερομηνίες για την ολοκλήρωση όλων των άλλων γεγονότων καθορίζονται με αυστηρή σειρά από αυξανόμενους αριθμούς γεγονότων. Για να καθοριστεί η ημερομηνία πρόωρης ολοκλήρωσης οποιουδήποτε συμβάντος j, λαμβάνονται υπόψη όλες οι εργασίες που περιλαμβάνονται σε αυτό το συμβάν, για κάθε εργασία η ημερομηνία πρόωρης ολοκλήρωσης του τελικού συμβάντος καθορίζεται ως το άθροισμα της ημερομηνίας πρόωρης ολοκλήρωσης του αρχικού γεγονότος της εργασίας και της διάρκεια αυτής της εργασίας tij,Από τις λαμβανόμενες τιμές επιλέγεται ο μέγιστος χρόνος πρόωρης ολοκλήρωσης του j-ου γεγονότος

t pj = (t pi +t ij) max και καταγράφεται στο γράφημα (αριστερός τομέας του συμβάντος)

2) Καθυστερημένες ημερομηνίες για εκδηλώσεις . Η καθυστερημένη ημερομηνία ολοκλήρωσης του τελικού γεγονότος θεωρείται ίση με την πρώιμη ημερομηνία του. Ο υπολογισμός των καθυστερημένων ημερομηνιών για την ολοκλήρωση όλων των άλλων γεγονότων πραγματοποιείται με αντίστροφη σειρά, σύμφωνα με τους φθίνοντες αριθμούς συμβάντων. Για τον καθορισμό της καθυστερημένης προθεσμίας για την ολοκλήρωση της προηγούμενης εκδήλωσης i, λαμβάνονται υπόψη όλες οι εργασίες που προέρχονται από την i-η εκδήλωση. Για κάθε εργασία υπολογίζεται η καθυστερημένη προθεσμία για την ολοκλήρωση της αρχικής εκδήλωσης t p i,ως τη διαφορά μεταξύ της καθυστερημένης ολοκλήρωσης της τελικής εκδήλωσης αυτής της εργασίας t p jκαι τη διάρκεια αυτής της εργασίας tij.Από την τιμή που προκύπτει, επιλέξτε τον ελάχιστο χρόνο καθυστερημένης ολοκλήρωσης του i-ου γεγονότος: t p i = (t p j - t ij)minκαι καταγράφεται στον σωστό τομέα.

3) Μήκος κρίσιμου μονοπατιού ισούται με την πρώιμη ημερομηνία του τελικού συμβάντος.

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

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

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

Αρχικά δεδομένα:

Πίνακας Μέθοδος

Οι κωδικοί εργασίας στον πίνακα είναι γραμμένοι σε αύξοντα ευρετήριο Εγώ.

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

Η στήλη 4 περιέχει τις τιμές της διάρκειας της εργασίας.

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

Η πρώιμη έναρξη δραστηριοτήτων που δεν έχουν προηγούμενες (στη στήλη 2 - μια παύλα) μπορεί να ληφθεί ως 0 εάν δεν έχει καθοριστεί άλλη τιμή. Η πρόωρη ολοκλήρωση της εργασίας καθορίζεται σύμφωνα με τον τύπο t r.o. ij = t pH ij + t ij και καταχωρήθηκε στη στήλη 6.

Η πρώιμη έναρξη των υπολοίπων μπορεί να οριστεί ως, για παράδειγμα, η εργασία 2.5, η οποία έχει αρχικό συμβάν 2, τότε ο χρόνος πρώιμης έναρξης της είναι ίσος με τον χρόνο πρόωρης λήξης της εργασίας 12, αφού έχει τέλος γεγονός του 2. Η τιμή από τη στήλη 6 ξαναγράφεται στη στήλη 5 Οι κωδικοί των προηγούμενων εργασιών αναφέρονται στη στήλη 2. Η πρόωρη ολοκλήρωση καθορίζεται επίσης από τον τύπο t r.o. ij = t pH ij + t ij

Εάν, στη στήλη 2, υποδεικνύεται ότι πριν από ένα συγκεκριμένο έργο προηγούνται περισσότερα από ένα έργα (το έργο 5.6 προηγείται από τα έργα 2.5 και 3.5), τότε είναι απαραίτητο να επιλέξετε την τιμή της πρώιμης εκκίνησης από διάφορες επιλογές αξίας (9 - έως την ώρα λήξης της εργασίας 2,5 ή 13 - έως το τέλος της εργασίας 3.5). Ο κανόνας επιλογής αντιστοιχεί στον τύπο t p .n. ij = (t pi + t ij) μέγ , δηλαδή, επιλέγεται η μέγιστη τιμή (στο παράδειγμα - 16). Οι πρώιμες καταλήξεις ορίζονται όπως παραπάνω.

Η μέγιστη τιμή του πρώιμου τέλους στη στήλη 6 αντιστοιχεί στην τιμή της διάρκειας της κρίσιμης διαδρομής (16).

Το δεύτερο πέρασμα κατά μήκος των σειρών του πίνακα από την εργασία που καταγράφηκε στην τελευταία γραμμή στην εργασία που καταγράφηκε στην πρώτη γραμμή σας επιτρέπει να προσδιορίσετε τις τιμές των καθυστερημένων δεικτών απόδοσης. Για εργασίες που δεν έχουν επόμενες εργασίες (στη στήλη 3 - μια παύλα, στο παράδειγμα της εργασίας 46, 5,6), η τιμή της κρίσιμης διαδρομής γράφεται στη στήλη καθυστερημένης ολοκλήρωσης (8). Για αυτές τις εργασίες, η τιμή καθυστερημένης έναρξης υπολογίζεται από τον τύπο τ α.σ. ij t από ij - t ij

Η καθυστερημένη ολοκλήρωση των υπολοίπων μπορεί να οριστεί ως, για παράδειγμα, η εργασία 3.5 θεωρηθεί, η οποία έχει συμβάν λήξης 5, τότε ο καθυστερημένος χρόνος τερματισμού της είναι ίσος με τον χρόνο καθυστερημένης έναρξης της εργασίας 5.6, αφού έχει τέλος γεγονός του 5. Η τιμή από τη στήλη 7 ξαναγράφεται στη στήλη 8. Οι κωδικοί των επόμενων εργασιών αναφέρονται στη στήλη 3. Η καθυστερημένη έναρξη καθορίζεται επίσης από τον τύπο τ α.σ. ij t από ij - t ij .

Εάν, στη στήλη 3, υποδεικνύεται ότι περισσότερες από μία εργασίες ακολουθούν μια συγκεκριμένη εργασία (η εργασία 0.1 ακολουθείται από τις εργασίες 1.2 και 1.3), τότε είναι απαραίτητο να επιλέξετε την τιμή του καθυστερημένου φινιρίσματος από πολλές επιλογές (3 - σύμφωνα με η ώρα έναρξης της εργασίας 1,3 ή 7 - σύμφωνα με την ώρα έναρξης 1,2), επιλέγεται η ελάχιστη τιμή (στο παράδειγμα - 3). Η καθυστερημένη έναρξη καθορίζεται όπως παραπάνω από τον τύπο τ α.σ. ij t από ij - t ij .

Η τιμή της συνολικής χαλάρωσης (στήλη 9) υπολογίζεται από τον τύπο

R nij = t κατά ij - t pH ij - t ij.

Η τιμή ελεύθερης χαλάρωσης (στήλη 10) υπολογίζεται χρησιμοποιώντας τον τύπο

R με ij = t ро ij - t рр ij - t ij

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

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

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

Η διαδρομή που συνδέει οποιοδήποτε δεδομένο γεγονός με το τελικό ονομάζεται μεταγενέστεροςτρόπος. Αυτό το μεγαλύτερο μονοπάτι ονομάζεται όσο το δυνατόν μεταγενέστερακαι συμβολίζεται με το L 2 (i), και η διάρκειά του είναι t.

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

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

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

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

Σύμφωνα με την αρχή της βελτιστότητας Bellman, ο βέλτιστος έλεγχος σε κάθε στάδιο καθορίζεται από τον στόχο ελέγχου και την κατάσταση στην αρχή του σταδίου. Η κατάσταση του συστήματος είναι τα γεγονότα που βρίσκονται στις τάξεις. Για την ολοκλήρωση της τελικής διοργάνωσης Χ 16 είναι απαραίτητη η συμπλήρωση των προηγούμενων διοργανώσεων. Πιθανές καταστάσεις του συστήματος στην αρχή του τελευταίου σταδίου εργασίας - η εμφάνιση των γεγονότων Χ 14 και Χ 15. Στους κύκλους στα σημεία Χ 14 και Χ 15 βάζουμε τη μέγιστη διάρκεια εργασίας στο τελευταίο στάδιο: Χ 14 5 , Χ 15 7 . Ας βρούμε τη μέγιστη διάρκεια εργασίας στα δύο τελευταία στάδια. Η κατάσταση του συστήματος στην αρχή του προτελευταίου σταδίου οφείλεται στο γεγονός Χ 13. Η μέγιστη διάρκεια της διαδρομής που οδηγεί από το Χ 13 στο Χ 16 είναι .

Επομένως, ο αριθμός 14 θα πρέπει να τοποθετηθεί στον κύκλο κοντά στο συμβάν X 13 και ούτω καθεξής. Πραγματοποιώντας τα στάδια από το τέλος προς την αρχή, διαπιστώνουμε το μήκος της κρίσιμης διαδρομής t cr =96. Για να βρούμε την ίδια την κρίσιμη διαδρομή, ας περάσουμε από τη διαδικασία υπολογισμού από το αρχικό συμβάν X 1 έως το τελικό X 16 . Πήραμε τον αριθμό 96 στο πρώτο στάδιο (από την αρχή) προσθέτοντας το 16 στον αριθμό 80. Επομένως, η κρίσιμη διαδρομή σε αυτό το στάδιο θα είναι ίση με (Χ 1, Χ 3). Ο αριθμός 80 = 16 + 64. Επομένως, η κρίσιμη διαδρομή στο δεύτερο στάδιο περνά μέσα από το έργο (Χ 3 , Χ 4) κ.λπ. Στο γράφημα σημειώνεται με έντονη γραμμή:

Χ 1 - Χ 3 - Χ 4 - Χ 7 - Χ 8 - Χ 10 - Χ 11 - Χ 12 - Χ 13 - Χ 15 - Χ 16 .

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

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

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

ή

Για να βρείτε την πρώιμη ημερομηνία του συμβάντος j , πρέπει να γνωρίζετε την κρίσιμη διαδρομή του κατευθυνόμενου υπογράφου, που αποτελείται από το σύνολο των διαδρομών που προηγούνται του δεδομένου συμβάντος j . Ο πρώιμος όρος του αρχικού συμβάντος είναι ίσος με μηδέν: t p (1)=0.

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

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

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

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

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

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

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

Τα κρίσιμα γεγονότα έχουν μηδενική καθυστέρηση. Καθορίζουν τις κρίσιμες δραστηριότητες και την κρίσιμη διαδρομή.

Παράδειγμα 10.2. Αφήστε το διάγραμμα δικτύου που φαίνεται στην εικ. 10.8.

Λύση.Υπολογίστε τις πρώιμες ημερομηνίες για την ολοκλήρωση των γεγονότων:

Έτσι, το τελικό γεγονός μπορεί να συμβεί μόνο τη 14η ημέρα από την έναρξη του έργου. Αυτός είναι ο μέγιστος χρόνος στον οποίο μπορούν να ολοκληρωθούν όλες οι δραστηριότητες του έργου. Καθορίζεται από το μεγαλύτερο μονοπάτι. Η ημερομηνία πρόωρης ολοκλήρωσης του έργου 6 =14 συμπίπτει με τον κρίσιμο χρόνο kp - τη συνολική διάρκεια της εργασίας που βρίσκεται στην κρίσιμη διαδρομή. Τώρα μπορείτε να επισημάνετε τις δραστηριότητες που ανήκουν στην κρίσιμη διαδρομή, επιστρέφοντας από το τελικό συμβάν στο αρχικό. Από τις δύο εργασίες που περιλαμβάνονται στο συμβάν 6 , , το μήκος της κρίσιμης διαδρομής καθόρισε τις εργασίες (5, 6), αφού (5 + 56)=14. Επομένως, η εργασία (5, 6) είναι κρίσιμη και ούτω καθεξής. Τα έργα (1, 3), (3, 4), (4, 5), (5, 6) καθόρισαν την κρίσιμη διαδρομή: cr = (1-3-4-5-6).

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

Δεδομένου ότι μετά την εκδήλωση 5, για να ολοκληρωθεί το έργο, οι εργασίες (5, 6) πρέπει να ολοκληρωθούν για 3 ημέρες. Δύο εργασίες βγαίνουν από το συμβάν 4, οπότε:

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

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

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

Πρόωρη ώρα έναρξηςισούται με την πρώιμη ημερομηνία του συμβάντος: .

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

Καθυστερημένο τέλος εργασίαςσυμπίπτει με την καθυστερημένη ολοκλήρωση της τελικής εκδήλωσης του: .

Καθυστερημένη ώρα έναρξηςισούται με τη διαφορά μεταξύ της καθυστερημένης ημερομηνίας ολοκλήρωσης της τελικής εκδήλωσης και της αξίας αυτής της εργασίας:

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

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

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

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

Ο υπολογισμός του γραφήματος δικτύου με πίνακα γίνεται σύμφωνα με τους τύπους που αναφέρθηκαν προηγουμένως στην ενότητα 4 (1-10). Κατά τον προσδιορισμό των παραμέτρων των μοντέλων δικτύου με αναλυτικό τρόπο, ο υπολογισμός γίνεται με τη μορφή πίνακα. Εξετάστε τα χαρακτηριστικά του υπολογισμού των μοντέλων δικτύου με αυτόν τον τρόπο (εφαρμογή 1) χρησιμοποιώντας το παράδειγμα υπολογισμού των παραμέτρων του διαγράμματος δικτύου που εμφανίζεται στην εργασία για αυτήν την εργασία μαθήματος (επιλογή 15).

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

Ο υπολογισμός του χρονοδιαγράμματος δικτύου ξεκινά με τον προσδιορισμό των τιμών των πρώιμων παραμέτρων της εργασίας. Η πρώιμη έναρξη της εργασίας 1-2 ισούται με μηδέν (τύπος 1) και το πρόωρο τέλος της σύμφωνα με τον τύπο 2.

Η πρώιμη έναρξη των δραστηριοτήτων 2-6 και 2-7 (σύμφωνα με τον τύπο 3) ισούται με το πρόωρο τέλος της δραστηριότητας 1-2.

Η μέγιστη τιμή πρόωρης ολοκλήρωσης της εργασίας 19-21, ίση με 36, καθορίζει τη διάρκεια της κρίσιμης διαδρομής και, επομένως, τη συνολική διάρκεια εκτέλεσης όλων των δραστηριοτήτων στο αρχικό μοντέλο δικτύου. Η προκύπτουσα τιμή της πρόωρης ολοκλήρωσης αυτής της εργασίας 19-21 = 36 μεταφέρεται στη στήλη της καθυστερημένης ολοκλήρωσης της τελικής εργασίας 20-21.

Η καθυστερημένη έναρξη της εργασίας 20-21 καθορίζεται σύμφωνα με τον τύπο 5 (= 34)

Η καθυστερημένη έναρξη της εργασίας 20-21 είναι η καθυστερημένη λήξη της εργασίας 15-20 (=) που προηγείται.

Περαιτέρω, ο υπολογισμός των καθυστερημένων παραμέτρων πραγματοποιείται με τον ίδιο τρόπο, εκτός από τις περιπτώσεις όπου η εργασία έχει πολλές επόμενες εργασίες (για παράδειγμα, η εργασία 6-9 έχει δύο επόμενες - 9-10 και 9-14). Σε αυτήν την περίπτωση, σύμφωνα με τον τύπο 4, η καθυστερημένη ολοκλήρωση της εργασίας 6-9 ισούται με την ελάχιστη τιμή της καθυστερημένης έναρξης των επόμενων εργασιών 9-10 και 9-14.

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

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

Η μερική χαλάρωση του χρόνου εργασίας, σύμφωνα με τον τύπο 10, ορίζεται ως η διαφορά μεταξύ της τιμής της πρώιμης έναρξης της επόμενης δραστηριότητας και της τιμής του πρώιμου τερματισμού για αυτήν τη δραστηριότητα. Για παράδειγμα, για την εργασία 6-7:

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

Γραφική Μέθοδος Υπολογισμού Διαγραμμάτων Δικτύου

Ο υπολογισμός του γραφήματος δικτύου με γραφικό τρόπο πραγματοποιείται παρόμοια με τη μέθοδο του πίνακα (τύποι 1-10), ωστόσο, η γραφική μέθοδος ή η μέθοδος τομέα για τον υπολογισμό των παραμέτρων του γραφήματος δικτύου περιλαμβάνει την καταγραφή τους απευθείας στο μοντέλο (Παράρτημα 2). Κάθε συμβάν (κύκλος) χωρίζεται σε τέσσερις τομείς. Ο χαρακτηρισμός των τομέων φαίνεται στο παρακάτω σχήμα:

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

Για να ελέγξετε την ορθότητα των υπολογισμών που πραγματοποιήθηκαν, θα πρέπει να βεβαιωθείτε ότι:

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

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

Υπολογισμός βασικοί δείκτες του μοντέλου δικτύουμπορεί να γίνει με τον ακόλουθο τρόπο.

• 1. Υπολογισμός πρώιμων ημερομηνιών:
  • ? πρόωρη έναρξη της εργασίαςκαθορίζεται από τη διάρκεια της μεγαλύτερης διαδρομής από το συμβάν έναρξης έως την έναρξη της εκτέλεσης αυτής της εργασίας,
  • ? ημερομηνίες πρόωρης ολοκλήρωσης- αυτή είναι η συντομότερη δυνατή ημερομηνία ολοκλήρωσης του έργου. Ο χρόνος πρόωρης λήξης της εργασίας ισούται με το άθροισμα του χρόνου πρόωρης έναρξης της εργασίας και της διάρκειας της ίδιας της εργασίας.
• 2.Υπολογισμός της κρίσιμης διαδρομής.Η διάρκειά του ορίζεται ως ο συνολικός χρόνος των δραστηριοτήτων στην κρίσιμη διαδρομή, δηλ. ο χρόνος ολοκλήρωσης του συνόλου των έργων με τον μεγαλύτερο παραλληλισμό όλων των έργων. Αυτός ο χρόνος είναι ίσος με τον μεγαλύτερο από τους χρόνους πρόωρης ολοκλήρωσης των ολοκληρώσεων του γραφήματος δικτύου. Η κρίσιμη διαδρομή διέρχεται από γεγονότα που δεν έχουν αποθέματα χρόνου (μέσω κρίσιμων δραστηριοτήτων).
• 3.Υπολογισμός καθυστερημένων ημερομηνιών έναρξης και λήξηςκαθορίζονται από τις δυνατότητες της οριακής μετατόπισης προς τα δεξιά κατά τον αριθμητικό άξονα των προθεσμιών ολοκλήρωσης των εργασιών ώστε να μην μεταβάλλεται ο χρόνος της κρίσιμης διαδρομής. Επομένως, είναι λογικό να πραγματοποιούνται υπολογισμοί από το τελευταίο γεγονός έως το πρώτο και να προσδιορίζεται πρώτα ο χρόνος καθυστερημένης ολοκλήρωσης της εργασίας και στη συνέχεια να υπολογιστεί ο χρόνος καθυστερημένης έναρξης της εργασίας:
  • ?καθυστερημένη ημερομηνία έναρξης (ij) ορίζεται ως η διαφορά μεταξύ της καθυστερημένης ολοκλήρωσης της εργασίας και της διάρκειας της ίδιας της εργασίας,
  • ? καθυστερημένη ημερομηνία ολοκλήρωσηςκαθορίζεται από την τιμή της διαδρομής ελάχιστης διάρκειας που οδηγεί σε αυτήν από το συμβάν τέλους και υπολογίζεται ως η διαφορά μεταξύ της κρίσιμης διαδρομής και της μέγιστης διάρκειας εργασίας από το συμβάν τέλους του δικτύου έως το συμβάν λήξης αυτής της εργασίας.
• 4. Υπολογισμός αποθεμάτων χρόνου».

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

• ? ιδιωτικός (δωρεάν) αποθεματικά χρόνου».
• 1)ιδιωτικό λουκούμι πρώτου είδουςκαθορίζεται από την ικανότητα αλλαγής του χρόνου καθυστερημένης έναρξης ( ij)σε προγενέστερες ημερομηνίες χωρίς αλλαγή των καθυστερημένων προθεσμιών για την ολοκλήρωση των αμέσως προηγούμενων εργασιών,
• 2) ιδιωτική χαλυβουργία δεύτερου είδουςκαθορίζεται από την ικανότητα αλλαγής της πρόωρης λήξης της εργασίας (ij)σε μεταγενέστερες ημερομηνίες χωρίς αλλαγή των πρώιμων ημερομηνιών για την έναρξη των αμέσως επόμενων εργασιών· καθορίζεται από τη διαφορά μεταξύ της πρώιμης έναρξης της επόμενης δραστηριότητας και του πρόωρου τερματισμού αυτής της δραστηριότητας.

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

Ρύζι. 7.5.

Για να υπολογίσουμε τις παραμέτρους, θα χρησιμοποιήσουμε τη μέθοδο του πίνακα και για να απλοποιήσουμε την αντίληψη, θα συνοψίσουμε τα πάντα σε έναν πίνακα. 7.1.

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

• 1. Για να είναι ίσα τα συνολικά και μερικά αποθεματικά του έργου (y), είναι απαραίτητο και αρκετό το τελικό γεγονός Υ του εν λόγω έργου να είναι γεγονός στην κρίσιμη διαδρομή.
• 2. Εάν είναι πλήρης ρεζέρβα (Εγώ και]1)κάποιου έργου ισούται με μηδέν, τότε το ιδιωτικό απόθεμα του δεύτερου τύπου (ζ "στ)ισούται επίσης με μηδέν. Μεταξύ αυτών των αποθεμάτων υπάρχει πάντα μια αναλογία R(IJ) > r"ijyΤα συνολικά και ιδιωτικά αποθεματικά χρόνου είναι πάντα μεγαλύτερα ή ίσα με μηδέν.
• 3. Προκειμένου το μερικό απόθεμα χρόνου εργασίας (y) να είναι ίσο με μηδέν, είναι απαραίτητο και αρκετό αυτό το έργο να βρίσκεται στη διαδρομή μέγιστου μήκους από το πρώτο συμβάν στο γεγονός y.
• 4. Αν η διάρκεια της εργασίας (y) αυξηθεί κατά p, δηλ. p τότε η ημερομηνία πρόωρης έναρξης της επόμενης εργασίας θα αυξηθεί κατά την τιμή του p - ζ" ("uu
• 5. Αν η διάρκεια της εργασίας (υ) αυξηθεί κατά το ποσό του συνολικού αποθεματικού χρόνου για την εργασία αυτή, τότε διαμορφώνεται νέα κρίσιμη διαδρομή, η διάρκεια της οποίας είναι ίση με τη διάρκεια της παλιάς.
• 6. Το συνολικό αποθεματικό χρόνου εργασίας (y) ισούται με το άθροισμα του μερικού αποθεματικού χρόνου του δεύτερου τύπου αυτής της εργασίας και το ελάχιστο του συνολικού αποθεματικού όλων των αμέσως επόμενων εργασιών.

Τα αποτελέσματα του υπολογισμού των παραμέτρων του διαγράμματος δικτύου

Πίνακας 7.1

	Διάρκεια	Νωρίς	όροι, η	Καθυστερημένες ημερομηνίες, h		Χρονικά αποθέματα, h
	έργα, η	Αρχές	καταλήξεις	Αρχές	καταλήξεις	Γεμάτος	Ελεύθερος
	Κρίσιμη διαδρομή, η		(εργασίες 1-3

7. Εάν η διάρκεια της εργασίας (r /) αυξηθεί κατά p, τότε θα εμφανιστεί μια νέα κρίσιμη διαδρομή, η διάρκεια της οποίας θα υπερβαίνει τη διάρκεια της παλιάς κρίσιμης διαδρομής κατά p -

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

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

Λύση

Για να λύσουμε το πρόβλημα, εφαρμόζουμε τον ακόλουθο συμβολισμό.

Στοιχείο δικτύου	Όνομα παραμέτρου	Σύμβολο παραμέτρου
Γεγονός i	Πρόωρη ημερομηνία ολοκλήρωσης της εκδήλωσης
Καθυστερημένη ημερομηνία ολοκλήρωσης της εκδήλωσης
Χαλαρή εκδήλωση
Εργασία (i, j)	Ωρα εργασίας
Πρόωρη ώρα έναρξης
Πρόωρο τέλος εργασίας
Καθυστερημένη ώρα έναρξης
Καθυστερημένο τέλος εργασίας
Πλήρης κράτηση χρόνου εκτέλεσης
	Χρόνος ταξιδιού
Μήκος κρίσιμου μονοπατιού
Απόθεμα χρόνου ταξιδιού

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

t p (i) = max(t(L ni)) (1)

όπου L ni είναι οποιαδήποτε διαδρομή που προηγείται του i-ου συμβάντος, δηλαδή, η διαδρομή από το αρχικό στο i-ο γεγονός του δικτύου.

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

t p (j) = max (2)

Η καθυστέρηση στην ολοκλήρωση της εκδήλωσης i σε σχέση με την πρώιμη ημερομηνία της δεν θα επηρεάσει τον χρόνο ολοκλήρωσης της τελικής εκδήλωσης (και, επομένως, τον χρόνο ολοκλήρωσης του συγκροτήματος των έργων) μέχρι το άθροισμα του χρόνου ολοκλήρωσης αυτής της εκδήλωσης και η διάρκεια (μήκος) του μέγιστου των διαδρομών που το ακολουθούν δεν υπερβαίνει το μήκος της κρίσιμης διαδρομής. Επομένως, ο όψιμος (ή οριακός) όρος t p (i) της ολοκλήρωσης του i-ου γεγονότος είναι ίσος με:

t p (i) = t kp - max(t(L ci)) (3)

όπου Lci είναι οποιοδήποτε μονοπάτι που ακολουθεί το i-ο γεγονός, δηλ. η διαδρομή από το i-ο στο τελικό συμβάν δικτύου.

Εάν το συμβάν i έχει πολλά επόμενα μονοπάτια, και επομένως πολλά επόμενα συμβάντα j, τότε η καθυστερημένη ημερομηνία ολοκλήρωσης του συμβάντος i μπορεί εύκολα να βρεθεί χρησιμοποιώντας τον τύπο:

t p (i) = min

Το απόθεμα χρόνου R(i) του i-ου γεγονότος ορίζεται ως η διαφορά μεταξύ των καθυστερήσεων και των πρώιμων ημερομηνιών ολοκλήρωσής του:

R(i) = t p (i) - t p (i)

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

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

Κατά τον προσδιορισμό του πρώιμου χρονισμού των γεγονότων tp(i), μετακινούμαστε κατά μήκος του γραφήματος δικτύου από αριστερά προς τα δεξιά και χρησιμοποιούμε τους τύπους (1), (2).

Υπολογισμός του χρόνου των γεγονότων.

Για i=0 (αρχικό συμβάν), προφανώς tp(0)=0.

i=1: t p (1) = t p (0) + t(0,1) = 0 + 0 = 0.

i=2: t p (2) = t p (1) + t(1,2) = 0 + 8 = 8.

i=3: t p (3) = t p (1) + t(1,3) = 0 + 3 = 3.

i=4: max(t p (2) + t(2,4);t p (3) + t(3,4)) = max(8 + 6;3 + 3) = 14.

i=5: tp(5) = tp(4) + t(4,5) = 14 + 0 = 14.

i=6: max(t p (4) + t(4,6);t p (5) + t(5,6)) = max(14 + 5;14 + 3) = 19.

i=7: t p (7) = t p (6) + t(6,7) = 19 + 9 = 28.

i=8: max(t p (2) + t(2.8);t p (6) + t(6.8);t p (7) + t(7.8)) = max(8 + 18;19 + 5; 28 + 4 ) = 32.

i=9: max(t p (5) + t(5,9);t p (7) + t(7,9)) = max(14 + 2;28 + 4) = 32.

i=10: max(t p (4) + t(4,10);t p (7) + t(7,10);t p (9) + t(9,10)) = max(14 + 4;28 + 2; 32 + 0) = 32.

i=11: max(t p (8) + t(8,11);t p (10) + t(10,11)) = max(32 + 12;32 + 4) = 44.

Το μήκος της κρίσιμης διαδρομής είναι ίσο με την ημερομηνία πρόωρης ολοκλήρωσης του τελικού γεγονότος 11: t kp =tp(11)=44

Κατά τον καθορισμό των καθυστερημένων ημερομηνιών για την ολοκλήρωση των γεγονότων t p (i), κινούμαστε μέσω του δικτύου προς την αντίθετη κατεύθυνση, δηλαδή από δεξιά προς τα αριστερά, και χρησιμοποιούμε τους τύπους (3), (4).

Για i=11 (το τελικό συμβάν), η καθυστερημένη ημερομηνία του συμβάντος πρέπει να είναι ίση με την πρώιμη ημερομηνία του (διαφορετικά, το μήκος της κρίσιμης διαδρομής θα αλλάξει): t p (11)= t p (11)=44

i=10: t p (10) = t p (11) - t(10,11) = 44 - 4 = 40.

i=9: t p (9) = t p (10) - t(9,10) = 40 - 0 = 40.

Εξετάζονται όλες οι γραμμές που ξεκινούν με τον αριθμό 8.

i=8: t p (8) = t p (11) - t(8,11) = 44 - 12 = 32.

Εξετάζονται όλες οι γραμμές που ξεκινούν με τον αριθμό 7.

i=7: min(t p (8) - t(7.8);t p (9) - t(7.9);t p (10) - t(7.10)) = min(32 - 4;40 - 4;40 - 2 ) = 28.

i=6: min(t p (7) - t(6.7);t p (8) - t(6.8)) = min (28 - 9; 32 - 5) = 19.

Εξετάζονται όλες οι γραμμές που ξεκινούν με τον αριθμό 5.

i=5: min(t p (6) - t(5.6);t p (9) - t(5.9)) = min (19 - 3; 40 - 2) = 16.

i=4: min(t p (5) - t(4.5);t p (6) - t(4.6);t p (10) - t(4.10)) = min(16 - 0;19 - 5;40 - 4 ) = 14.

Εξετάζονται όλες οι γραμμές που ξεκινούν με τον αριθμό 3.

i=3: t p (3) = t p (4) - t(3,4) = 14 - 3 = 11.

i=2: min(t p (4) - t(2,4);t p (8) - t(2,8)) = min (14 - 6; 32 - 18) = 8.

i=1: min(t p (2) - t(1,2);t p (3) - t(1,3)) = min(8 - 8;11 - 3) = 0.

(0,1): 0 - 0 = 0;

Πίνακας 1 - Υπολογισμός του αποθεματικού γεγονότων

Αριθμός εκδήλωσης	Χρόνος εκδήλωσης: νωρίς tp(i)	Ημερομηνίες εκδήλωσης: late tp(i)	Απόθεμα χρόνου, R(i)

Συμπλήρωση πίνακα 2.

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

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

Έτσι, για το έργο (1,2) στη στήλη 1 βάζουμε τον αριθμό 1, γιατί αριθμός 1 τελειώνει 1 εργασία: (0,1).

Η στήλη 4 λαμβάνεται από τον πίνακα 1 (t p (i)). Η στήλη 7 λαμβάνεται από τον πίνακα 1 (t p (i)).

Οι τιμές στη στήλη 5 λαμβάνονται αθροίζοντας τις στήλες 3 και 4.

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

Το περιεχόμενο της στήλης 8 (συνολική χαλάρωση R(ij)) είναι ίσο με τη διαφορά μεταξύ των στηλών 6 και 4 ή των στηλών 7 και 5. Εάν το R(ij) είναι ίσο με μηδέν, τότε η εργασία είναι κρίσιμη

Πίνακας 2 - Ανάλυση του μοντέλου δικτύου σε βάθος χρόνου

Εργασία (i,j)	Αριθμός προηγούμενων εργασιών	Διάρκεια tij	Πρώιμες ημερομηνίες: έναρξη tijR.N.	Πρώιμες ημερομηνίες: κατάληξη tijР.О.	Καθυστερημένες ημερομηνίες: έναρξη tijP.N.	Καθυστερημένες ημερομηνίες: τέλος tijP.O.	Αποθέματα χρόνου: πλήρης RijP	Ανεξάρτητος αποθεματικός χρόνου Rij	Ιδιωτικό αποθεματικό 1ου είδους, Rij1	Private Reserve Type II, RijC

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

R(i,j)= R p (i,j) - R(i)

Η μερική χαλάρωση του δεύτερου τύπου ή η ελεύθερη χαλάρωση Rc της εργασίας (i, j) είναι ένα μέρος της συνολικής χαλάρωσης, κατά την οποία η διάρκεια της εργασίας μπορεί να αυξηθεί χωρίς να αλλάξει η πρώιμη ημερομηνία του συμβάντος λήξης της. Το Rc βρίσκεται με τον τύπο:

R(i,j)= R n (i,j) - R(j)

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

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

R(i,j)= Rп(i,j) - R(i) - R(j)

κρίσιμο μονοπάτι: (0,1)(1,2)(2,4)(4,6)(6,7)(7,8)(8,11)

Διάρκεια Κρίσιμης Διαδρομής: 44

Ας βρούμε τον συντελεστή έντασης εργασίας του προτελευταίου έργου. Δεδομένου ότι το μήκος της κρίσιμης διαδρομής είναι 44, η μέγιστη διαδρομή μέσω του έργου (1,10) είναι 32, τότε

Κ(1,10)=(32-28)/(44-28)=0,296.

4. Ένας ISP σε μια μικρή πόλη έχει 5 αποκλειστικά κανάλια εξυπηρέτησης. Κατά μέσο όρο, χρειάζονται 25 λεπτά για να εξυπηρετηθεί ένας πελάτης. Το σύστημα λαμβάνει κατά μέσο όρο 6 aczas ανά ώρα. Εάν δεν υπάρχουν δωρεάν κανάλια, ακολουθεί άρνηση. Προσδιορίστε τα χαρακτηριστικά της υπηρεσίας: την πιθανότητα αστοχίας, τον μέσο αριθμό γραμμών επικοινωνίας που καταλαμβάνει η υπηρεσία, την απόλυτη και σχετική απόδοση, την πιθανότητα εξυπηρέτησης. Βρείτε τον αριθμό των αποκλειστικών καναλιών για τα οποία η σχετική απόδοση του συστήματος θα είναι τουλάχιστον 0,95. Ας υποθέσουμε ότι οι ροές των αιτημάτων και των υπηρεσιών είναι οι απλούστερες

Ένταση ροής υπηρεσίας:

Ένταση φορτίου:

c \u003d l * t obs \u003d 6 * 25/60 \u003d 2,5

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

Η πιθανότητα η υπηρεσία:

το κανάλι 1 είναι απασχολημένο:

p 1 = με 1 / 1! p 0 = 2,5 1/1! * 0,0857 = 0,214

2 κανάλια είναι κατειλημμένα:

p 2 \u003d c 2 / 2! p 0 = 2,5 2 /2! * 0,0857 = 0,268

3 κανάλια είναι κατειλημμένα:

p 3 \u003d c 3 / 3! p 0 = 2,5 3/3! * 0,0857 = 0,223

4 κανάλια είναι κατειλημμένα:

p 4 = με 4 / 4! p 0 = 2,5 4 /4! * 0,0857 = 0,139

5 κανάλια είναι κατειλημμένα:

p 5 = με 5 / 5! p 0 = 2,5 5 /5! * 0,0857 = 0,0697

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

Αυτό σημαίνει ότι το 7% των αιτήσεων που ελήφθησαν δεν γίνονται δεκτές για επίδοση.

Πιθανότητα εξυπηρέτησης εισερχόμενων αιτημάτων-πιθανότητα να εξυπηρετηθεί ο πελάτης:

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

p open + p obs = 1

Σχετική διεκπεραίωση Q = p obs .

p obs \u003d 1 - p otk \u003d 1 - 0,0697 \u003d 0,93

Κατά συνέπεια, θα εξυπηρετηθεί το 93% των αιτήσεων που θα υποβληθούν. Μέσος αριθμός καναλιών που καταλαμβάνει η υπηρεσία

n s \u003d s * p obs \u003d 2,5 * 0,93 \u003d 2,326 κανάλια.

Μέσος όρος αδράνειας καναλιών.

n pr \u003d n - n z \u003d 5 - 2.326 \u003d 2.7 κανάλια.

Ποσοστό πληρότητας καναλιού εξυπηρέτησης.

Επομένως, το σύστημα είναι απασχολημένο κατά 50% με συντήρηση.

Απόλυτο εύρος ζώνης

A \u003d pobs * l \u003d 0,93 * 6 \u003d 5,581 εφαρμογές / ώρα.

Μέσος χρόνος αδράνειας του QS.

t pr \u003d p otk * t obs \u003d 0,0697 * 0,417 \u003d 0,029 ώρες.

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

L obs \u003d s * Q \u003d 2,5 * 0,93 \u003d 2,326 μονάδες.

Μέσος χρόνος παραμονής αίτησης στον ΚΟΑ(Ο τύπος του Little).

Αριθμός αιτημάτων που απορρίφθηκαν εντός μίας ώρας: l * p 1 = 0,418 αιτήματα ανά ώρα.

Ονομαστική απόδοση QS: 5 / 0,417 = 12.002 εφαρμογές ανά ώρα.

Η πραγματική απόδοση του ΚΟΑ: 5.581 / 12.002 = 47% της ονομαστικής απόδοσης.

Ας προσδιορίσουμε τον αριθμό των καναλιών που απαιτούνται για τη διασφάλιση της λειτουργικότητας του συστήματος με την πιθανότητα P ? 0,95

Για να γίνει αυτό, βρίσκουμε n από την συνθήκη:

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