Σε αυτό το άρθρο θα σας πούμε πώς λύσαμε το πρόβλημα της έλλειψης ελεύθερων κυψελών σε μια αποθήκη και την ανάπτυξη ενός διακριτού αλγορίθμου βελτιστοποίησης για την επίλυση ενός τέτοιου προβλήματος. Ας μιλήσουμε για το πώς «χτίσαμε» το μαθηματικό μοντέλο του προβλήματος βελτιστοποίησης και για τις δυσκολίες που συναντήσαμε απροσδόκητα κατά την επεξεργασία δεδομένων εισόδου για τον αλγόριθμο.
Εάν ενδιαφέρεστε για εφαρμογές των μαθηματικών στις επιχειρήσεις και δεν φοβάστε τους άκαμπτους μετασχηματισμούς ταυτότητας των τύπων στο επίπεδο της 5ης τάξης, τότε καλώς ήρθατε στη γάτα!
Το άρθρο θα είναι χρήσιμο σε όσους εφαρμόζουν WMS-συστήματα, εργασίες στη βιομηχανία logistics αποθήκης ή παραγωγής, καθώς και προγραμματιστές που ενδιαφέρονται για εφαρμογές μαθηματικών στις επιχειρήσεις και βελτιστοποίηση διαδικασιών σε μια επιχείρηση.
Εισαγωγικό μέρος
Αυτή η δημοσίευση συνεχίζει τη σειρά άρθρων στα οποία μοιραζόμαστε την επιτυχημένη εμπειρία μας στην εφαρμογή αλγορίθμων βελτιστοποίησης σε διαδικασίες αποθήκης.
В περιγράφει τις ιδιαιτερότητες της αποθήκης όπου υλοποιήσαμε WMS-σύστημα και εξηγεί επίσης γιατί χρειαζόμασταν να λύσουμε το πρόβλημα της ομαδοποίησης παρτίδων των υπόλοιπων αγαθών κατά την υλοποίηση WMS-συστήματα και πώς το κάναμε.
Όταν ολοκληρώσαμε τη σύνταξη του άρθρου σχετικά με τους αλγόριθμους βελτιστοποίησης, αποδείχθηκε ότι ήταν πολύ μεγάλο, οπότε αποφασίσαμε να χωρίσουμε το συσσωρευμένο υλικό σε 2 μέρη:
- Στο πρώτο μέρος (αυτό το άρθρο) θα μιλήσουμε για το πώς «χτίσαμε» το μαθηματικό μοντέλο του προβλήματος και για τις μεγάλες δυσκολίες που απροσδόκητα συναντήσαμε κατά την επεξεργασία και τη μετατροπή των δεδομένων εισόδου για τον αλγόριθμο.
- Στο δεύτερο μέρος θα εξετάσουμε αναλυτικά την υλοποίηση του αλγορίθμου στη γλώσσα C + +, θα πραγματοποιήσουμε ένα υπολογιστικό πείραμα και θα συνοψίσουμε την εμπειρία που αποκτήσαμε κατά την εφαρμογή τέτοιων «έξυπνων τεχνολογιών» στις επιχειρηματικές διαδικασίες του πελάτη.
Πώς να διαβάσετε ένα άρθρο. Εάν διαβάσετε το προηγούμενο άρθρο, τότε μπορείτε να μεταβείτε αμέσως στο κεφάλαιο "Επισκόπηση των υπαρχουσών λύσεων", εάν όχι, τότε η περιγραφή του προβλήματος που επιλύεται βρίσκεται στο παρακάτω spoiler.
Περιγραφή του προβλήματος που επιλύεται στην αποθήκη του πελάτη
Συμφόρηση στις διαδικασίες
Το 2018 ολοκληρώσαμε ένα έργο προς υλοποίηση WMS-συστήματα στην αποθήκη "Trading House "LD" στο Chelyabinsk. Υλοποιήσαμε το προϊόν «1C-Logistics: Warehouse Management 3» για 20 χώρους εργασίας: χειριστές WMS, αποθηκάριοι, οδηγοί περονοφόρων. Η μέση αποθήκη είναι περίπου 4 χιλιάδες m2, ο αριθμός των κυψελών είναι 5000 και ο αριθμός των SKU είναι 4500. Η αποθήκη αποθηκεύει σφαιρικές βαλβίδες δικής μας παραγωγής διαφόρων μεγεθών από 1 kg έως 400 kg. Το απόθεμα στην αποθήκη αποθηκεύεται σε παρτίδες, καθώς υπάρχει ανάγκη επιλογής προϊόντων σύμφωνα με το FIFO.
Κατά τον σχεδιασμό των σχημάτων αυτοματισμού διεργασιών αποθήκης, αντιμετωπίσαμε το υπάρχον πρόβλημα της μη βέλτιστης αποθήκευσης αποθεμάτων. Οι ιδιαιτερότητες της αποθήκευσης και της τοποθέτησης γερανών είναι τέτοιες που μια μονάδα αποθήκευσης μπορεί να περιέχει αντικείμενα μόνο από μία παρτίδα (βλ. Εικ. 1). Τα προϊόντα φτάνουν στην αποθήκη καθημερινά και κάθε άφιξη είναι ξεχωριστή παρτίδα. Συνολικά, ως αποτέλεσμα 1 μήνα λειτουργίας της αποθήκης, δημιουργούνται 30 ξεχωριστές παρτίδες, παρά το γεγονός ότι η καθεμία πρέπει να αποθηκευτεί σε ξεχωριστό κελί. Τα προϊόντα συχνά επιλέγονται όχι σε ολόκληρες παλέτες, αλλά σε τεμάχια, και ως αποτέλεσμα, στη ζώνη επιλογής τεμαχίων σε πολλά κελιά παρατηρείται η ακόλουθη εικόνα: σε ένα κελί με όγκο μεγαλύτερο από 1 m3 υπάρχουν πολλά κομμάτια γερανών που καταλαμβάνουν λιγότερο από 5-10% του όγκου των κυττάρων.
Εικ. 1. Φωτογραφία πολλών κομματιών σε ένα κελί
Είναι σαφές ότι η χωρητικότητα αποθήκευσης δεν χρησιμοποιείται με τον βέλτιστο τρόπο. Για να φανταστώ την κλίμακα της καταστροφής, μπορώ να δώσω αριθμούς: κατά μέσο όρο, υπάρχουν από 1 έως 3 κελιά τέτοιων κυψελών με όγκο μεγαλύτερο από 100 m300 με «μικροσκοπικά» υπόλοιπα σε διαφορετικές περιόδους λειτουργίας της αποθήκης. Δεδομένου ότι η αποθήκη είναι σχετικά μικρή, κατά τη διάρκεια των πολυάσχολων εποχών της αποθήκης αυτός ο παράγοντας γίνεται «συμφόρηση» και επιβραδύνει σε μεγάλο βαθμό τις διαδικασίες αποδοχής και αποστολής της αποθήκης.
Ιδέα λύσης προβλήματος
Προέκυψε μια ιδέα: οι παρτίδες υπολειμμάτων με τις πλησιέστερες ημερομηνίες θα πρέπει να μειωθούν σε μία μόνο παρτίδα και τέτοια υπολείμματα με ενοποιημένη παρτίδα θα πρέπει να τοποθετούνται συμπαγώς μαζί σε ένα κελί ή σε πολλά, εάν δεν υπάρχει αρκετός χώρος σε ένα για να φιλοξενήσει το ολόκληρη την ποσότητα των υπολειμμάτων. Ένα παράδειγμα τέτοιας «συμπίεσης» φαίνεται στο σχήμα 2.
Εικ.2. Σχέδιο συμπίεσης υπολειμμάτων σε κύτταρα
Αυτό σας επιτρέπει να μειώσετε σημαντικά τον κατειλημμένο χώρο αποθήκης που θα χρησιμοποιηθεί για την τοποθέτηση νέων εμπορευμάτων. Σε μια κατάσταση όπου η χωρητικότητα της αποθήκης είναι υπερφορτωμένη, ένα τέτοιο μέτρο είναι εξαιρετικά απαραίτητο, διαφορετικά μπορεί απλώς να μην υπάρχει αρκετός ελεύθερος χώρος για την υποδοχή νέων αγαθών, γεγονός που θα οδηγήσει σε διακοπή των διαδικασιών τοποθέτησης και αναπλήρωσης της αποθήκης και, κατά συνέπεια, να σταματήσει η παραλαβή και η αποστολή. Παλαιότερα, πριν από την εφαρμογή του συστήματος WMS, μια τέτοια λειτουργία γινόταν χειροκίνητα, η οποία ήταν αναποτελεσματική, αφού η διαδικασία αναζήτησης κατάλληλων ισορροπιών σε κελιά ήταν αρκετά μεγάλη. Τώρα, με την εισαγωγή ενός συστήματος WMS, αποφασίσαμε να αυτοματοποιήσουμε τη διαδικασία, να την επιταχύνουμε και να την κάνουμε έξυπνη.
Η διαδικασία επίλυσης ενός τέτοιου προβλήματος χωρίζεται σε 2 στάδια:
- στο πρώτο στάδιο βρίσκουμε ομάδες παρτίδων κοντά στην ημερομηνία συμπίεσης (αφιερωμένη σε αυτήν την εργασία );
- στο δεύτερο στάδιο, για κάθε ομάδα παρτίδων υπολογίζουμε την πιο συμπαγή τοποθέτηση των υπόλοιπων προϊόντων στα κελιά.
Στο παρόν άρθρο θα επικεντρωθούμε στο δεύτερο στάδιο του αλγορίθμου.
Ανασκόπηση υφιστάμενων λύσεων
Πριν προχωρήσουμε στην περιγραφή των αλγορίθμων που έχουμε αναπτύξει, αξίζει να κάνουμε μια σύντομη επισκόπηση των συστημάτων που υπάρχουν ήδη στην αγορά WMS, τα οποία εφαρμόζουν παρόμοια λειτουργικότητα βέλτιστης συμπίεσης.
Πρώτα απ 'όλα, είναι απαραίτητο να σημειώσετε το προϊόν "1C: Enterprise 8. WMS Logistics. Warehouse management 4", το οποίο ανήκει και αντιγράφεται από την 1C και ανήκει στην τέταρτη γενιά WMS-συστήματα που αναπτύχθηκαν από την AXELOT. Αυτό το σύστημα διεκδικεί λειτουργία συμπίεσης, η οποία έχει σχεδιαστεί για να ενώνει ανόμοια υπολείμματα προϊόντων σε ένα κοινό κελί. Αξίζει να αναφέρουμε ότι η λειτουργία συμπίεσης σε ένα τέτοιο σύστημα περιλαμβάνει και άλλες δυνατότητες, για παράδειγμα, τη διόρθωση της τοποθέτησης αγαθών σε κελιά σύμφωνα με τις κατηγορίες ABC τους, αλλά δεν θα σταθούμε σε αυτές.
Εάν αναλύσετε τον κωδικό του συστήματος 1C: Enterprise 8. WMS Logistics. Διαχείριση αποθήκης 4" (η οποία είναι ανοιχτή σε αυτό το τμήμα της λειτουργικότητας), μπορούμε να συμπεράνουμε τα εξής. Ο αλγόριθμος υπολειπόμενης συμπίεσης εφαρμόζει μια μάλλον πρωτόγονη γραμμική λογική και δεν μπορεί να γίνει λόγος για οποιαδήποτε «βέλτιστη» συμπίεση. Φυσικά, δεν προβλέπει ομαδοποίηση κομμάτων. Αρκετοί πελάτες που είχαν εφαρμόσει ένα τέτοιο σύστημα παραπονέθηκαν για τα αποτελέσματα του σχεδιασμού συμπίεσης. Για παράδειγμα, συχνά στην πράξη κατά τη συμπίεση συνέβη η ακόλουθη κατάσταση: 100 τεμ. Προβλέπεται η μεταφορά των υπόλοιπων εμπορευμάτων από το ένα κελί στο άλλο, όπου βρίσκεται 1 τεμάχιο. αγαθών, αν και είναι βέλτιστο από την άποψη της κατανάλωσης χρόνου να γίνει το αντίθετο.
Επίσης, η λειτουργικότητα της συμπίεσης των υπολοίπων αγαθών σε κύτταρα δηλώνεται σε πολλές χώρες του εξωτερικού. WMS-συστήματα, αλλά, δυστυχώς, δεν έχουμε πραγματική ανατροφοδότηση για την αποτελεσματικότητα των αλγορίθμων (αυτό είναι εμπορικό μυστικό), πολύ λιγότερο μια ιδέα για το βάθος της λογικής τους (ιδιόκτητο λογισμικό κλειστού κώδικα), επομένως δεν μπορούμε να κρίνουμε.
Αναζήτηση για ένα μαθηματικό μοντέλο του προβλήματος
Για να σχεδιάσουμε αλγόριθμους υψηλής ποιότητας για την επίλυση ενός προβλήματος, είναι απαραίτητο πρώτα να διατυπώσουμε με σαφήνεια αυτό το πρόβλημα μαθηματικά, κάτι που θα κάνουμε.
Υπάρχουν πολλά κύτταρα , που περιέχουν τα υπολείμματα ορισμένων αγαθών. Στη συνέχεια, θα ονομάσουμε τέτοια κύτταρα κύτταρα δότη. Ας υποδηλώσουμε όγκος αγαθών στο κελί $.
Είναι σημαντικό να πούμε ότι μόνο ένα προϊόν μιας παρτίδας ή πολλές παρτίδες που είχαν προηγουμένως συνδυαστεί σε ένα σύμπλεγμα (διαβάστε: ), η οποία οφείλεται στις ιδιαιτερότητες αποθήκευσης και αποθήκευσης εμπορευμάτων. Διαφορετικά προϊόντα ή διαφορετικές ομάδες παρτίδων θα πρέπει να εκτελούν τη δική τους ξεχωριστή διαδικασία συμπίεσης.
Υπάρχουν πολλά κύτταρα , στο οποίο μπορούν ενδεχομένως να τοποθετηθούν υπολείμματα από κύτταρα δότες. Θα ονομάσουμε περαιτέρω τέτοια κελιά κελιά δοχείων. Αυτά μπορεί να είναι είτε ελεύθερα κύτταρα στην αποθήκη είτε κύτταρα δότη από μια ποικιλία . Πάντα άφθονο είναι ένα υποσύνολο .
Για κάθε κύτταρο από πολλούς Έχουν τεθεί περιορισμοί χωρητικότητας , μετρημένο σε dm3. Ένα dm3 είναι ένας κύβος με πλευρές 10 εκ. Τα προϊόντα που αποθηκεύονται στην αποθήκη είναι αρκετά μεγάλα, οπότε σε αυτή την περίπτωση μια τέτοια διακριτοποίηση είναι αρκετά.
Δίνεται ένας πίνακας με τις μικρότερες αποστάσεις σε μέτρα μεταξύ κάθε ζεύγους κελιών Όπου и ανήκουν σε σύνολα и αντιστοίχως.
Ας υποδηλώσουμε «κόστος» μετακίνησης αγαθών από το κελί σε ένα κελί . Ας υποδηλώσουμε «κόστος» επιλογής κοντέινερ να μεταφέρει υπολείμματα από άλλα κύτταρα σε αυτό. Πώς ακριβώς και σε ποιες μονάδες μέτρησης θα υπολογιστούν οι τιμές и θα εξετάσουμε περαιτέρω (δείτε την ενότητα προετοιμασία δεδομένων εισόδου), προς το παρόν αρκεί να πούμε ότι τέτοιες τιμές θα είναι ευθέως ανάλογες με τις τιμές и αντιστοίχως.
Ας υποδηλώσουμε με μια μεταβλητή που παίρνει την τιμή 1 εάν το υπόλοιπο είναι από το κελί μεταφέρθηκε σε κοντέινερ , και 0 διαφορετικά. Ας υποδηλώσουμε με μια μεταβλητή που παίρνει την τιμή 1 εάν το κοντέινερ περιέχει τα υπόλοιπα αγαθά και 0 διαφορετικά.
Η εργασία αναφέρεται ως εξής: πρέπει να βρεις τόσα πολλά δοχεία και έτσι «προσαρτούν» κύτταρα δότη σε κύτταρα δοχείων προκειμένου να ελαχιστοποιηθεί η λειτουργία
υπό περιορισμούς
Συνολικά, κατά τον υπολογισμό της λύσης του προβλήματος, προσπαθούμε:
- Πρώτον, για εξοικονόμηση χωρητικότητας αποθήκευσης.
- δεύτερον, για εξοικονόμηση χρόνου των αποθηκάριων.
Ο τελευταίος περιορισμός σημαίνει ότι δεν μπορούμε να μεταφέρουμε εμπορεύματα σε ένα εμπορευματοκιβώτιο που δεν επιλέξαμε εμείς και επομένως δεν «επιβαρύναμε το κόστος» για την επιλογή του. Αυτός ο περιορισμός σημαίνει επίσης ότι ο όγκος των αγαθών που μετακινούνται από τα κελιά στο δοχείο δεν πρέπει να υπερβαίνει τη χωρητικότητα του εμπορευματοκιβωτίου. Με τον όρο επίλυση ενός προβλήματος εννοούμε ένα σύνολο δοχείων και μεθόδους προσάρτησης κυττάρων δότη σε δοχεία.
Αυτή η διατύπωση του προβλήματος βελτιστοποίησης δεν είναι νέα και έχει μελετηθεί από πολλούς μαθηματικούς από τις αρχές της δεκαετίας του '80 του περασμένου αιώνα. Στην ξένη βιβλιογραφία υπάρχουν 2 προβλήματα βελτιστοποίησης με κατάλληλο μαθηματικό μοντέλο: и (θα μιλήσουμε για τις διαφορές στις εργασίες αργότερα). Αξίζει να πούμε ότι στη μαθηματική βιβλιογραφία, η διατύπωση τέτοιων δύο προβλημάτων βελτιστοποίησης διατυπώνεται ως προς τη θέση των επιχειρήσεων στο έδαφος, εξ ου και η ονομασία «Τοποθεσία Εγκατάστασης». Ως επί το πλείστον, πρόκειται για φόρο τιμής στην παράδοση, αφού για πρώτη φορά η ανάγκη επίλυσης τέτοιων συνδυαστικών προβλημάτων προήλθε από τον τομέα της εφοδιαστικής, κυρίως από τον στρατιωτικό-βιομηχανικό τομέα τη δεκαετία του '50 του περασμένου αιώνα. Όσον αφορά την τοποθεσία της επιχείρησης, τέτοιες εργασίες διατυπώνονται ως εξής:
- Υπάρχει ένας πεπερασμένος αριθμός πόλεων όπου είναι δυνητικά δυνατός ο εντοπισμός μεταποιητικών επιχειρήσεων (εφεξής καλούμενες πόλεις παραγωγής). Για κάθε πόλη παραγωγής, καθορίζονται τα κόστη ανοίγματος μιας επιχείρησης σε αυτήν, καθώς και περιορισμός στην παραγωγική ικανότητα της επιχείρησης που ανοίγει σε αυτήν.
- Υπάρχει ένα πεπερασμένο σύνολο πόλεων όπου βρίσκονται πραγματικά οι πελάτες (εφεξής καλούμενες πόλεις πελάτες). Για κάθε τέτοια πόλη πελατών, προσδιορίζεται ο όγκος της ζήτησης για προϊόντα. Για απλότητα, θα υποθέσουμε ότι υπάρχει μόνο ένα προϊόν που παράγεται από επιχειρήσεις και καταναλώνεται από πελάτες.
- Για κάθε ζεύγος πόλης-κατασκευαστή και πόλη-πελάτη, προσδιορίζεται η αξία του κόστους μεταφοράς για την παράδοση του απαιτούμενου όγκου προϊόντων από τον κατασκευαστή στον πελάτη.
Πρέπει να βρείτε σε ποιες πόλεις να ανοίξετε επιχειρήσεις και πώς να συνδέσετε πελάτες σε τέτοιες επιχειρήσεις για να:
- Το συνολικό κόστος ανοίγματος επιχειρήσεων και το κόστος μεταφοράς ήταν ελάχιστο.
- Ο όγκος της ζήτησης από πελάτες που ανατέθηκαν σε οποιαδήποτε ανοιχτή επιχείρηση δεν υπερέβαινε την παραγωγική ικανότητα αυτής της επιχείρησης.
Τώρα αξίζει να αναφέρουμε τη μόνη διαφορά σε αυτά τα δύο κλασικά προβλήματα:
- Πρόβλημα θέσης εγκατάστασης με χωρητικότητα μίας πηγής – ο πελάτης τροφοδοτείται μόνο από μία ανοιχτή εγκατάσταση.
- Πρόβλημα τοποθεσίας εγκατάστασης με χωρητικότητα πολλαπλών πηγών – ο πελάτης μπορεί να τροφοδοτείται από πολλές ανοιχτές εγκαταστάσεις ταυτόχρονα.
Μια τέτοια διαφορά μεταξύ των δύο προβλημάτων είναι ασήμαντη με την πρώτη ματιά, αλλά, στην πραγματικότητα, οδηγεί σε μια εντελώς διαφορετική συνδυαστική δομή τέτοιων προβλημάτων και, κατά συνέπεια, σε εντελώς διαφορετικούς αλγόριθμους για την επίλυσή τους. Οι διαφορές μεταξύ των εργασιών φαίνονται στο παρακάτω σχήμα.
Εικ.3. α) Πρόβλημα θέσης εγκατάστασης με χωρητικότητα πολλαπλών πηγών
Εικ.3. β) Πρόβλημα θέσης εγκατάστασης χωρητικότητας μίας πηγής
Και τα δύο καθήκοντα -δύσκολο, δηλαδή δεν υπάρχει ακριβής αλγόριθμος που θα έλυνε ένα τέτοιο πρόβλημα σε ένα χρονικό πολυώνυμο στο μέγεθος των δεδομένων εισόδου. Με πιο απλά λόγια, όλοι οι ακριβείς αλγόριθμοι για την επίλυση ενός προβλήματος θα λειτουργούν σε εκθετικό χρόνο, αν και ίσως πιο γρήγορα από μια πλήρη αναζήτηση επιλογών. Από το καθήκον -δύσκολο, τότε θα εξετάσουμε μόνο κατά προσέγγιση ευρετικές, δηλαδή αλγόριθμους που θα υπολογίζουν με συνέπεια λύσεις πολύ κοντά στη βέλτιστη και θα λειτουργούν αρκετά γρήγορα. Εάν ενδιαφέρεστε για μια τέτοια εργασία, μπορείτε να βρείτε μια καλή επισκόπηση στα ρωσικά εδώ.
Αν στραφούμε στην ορολογία του προβλήματος μας της βέλτιστης συμπίεσης αγαθών στα κύτταρα, τότε:
- Οι πόλεις-πελάτες είναι κύτταρα δωρητών με τα υπόλοιπα αγαθά,
- κατασκευαστικές πόλεις – κυψέλες εμπορευματοκιβωτίων , στο οποίο υποτίθεται ότι τοποθετούνται τα υπολείμματα από άλλα κελιά,
- κόστος μεταφοράς - κόστος χρόνου αποθηκευτή για να μετακινήσει τον όγκο των αγαθών από το κελί του δότη σε ένα κελί δοχείου ;
- κόστος ανοίγματος επιχείρησης - κόστος επιλογής κοντέινερ , ίσο με τον όγκο του κελιού του δοχείου , πολλαπλασιαζόμενο με έναν ορισμένο συντελεστή για την εξοικονόμηση ελεύθερων όγκων (η τιμή του συντελεστή είναι πάντα > 1) (δείτε την ενότητα προετοιμασία δεδομένων εισόδου).
Αφού σχεδιαστεί η αναλογία με τις γνωστές κλασσικές λύσεις του προβλήματος, είναι απαραίτητο να απαντηθεί ένα σημαντικό ερώτημα από το οποίο εξαρτάται η επιλογή της αρχιτεκτονικής του αλγορίθμου λύσης: η μετακίνηση των υπολοίπων από το κελί δότη είναι δυνατή μόνο σε ένα και μόνο ένα κοντέινερ (Single-Source), ή είναι δυνατόν να μετακινηθούν τα υπόλοιπα σε πολλά κελιά κοντέινερ (Multi-Source);
Αξίζει να σημειωθεί ότι στην πράξη λαμβάνουν χώρα και οι δύο διατυπώσεις του προβλήματος. Παρακάτω παρουσιάζουμε όλα τα πλεονεκτήματα και τα μειονεκτήματα για κάθε τέτοια ρύθμιση:
| Παραλλαγή προβλήματος | Πλεονεκτήματα της επιλογής | Μειονεκτήματα της επιλογής |
|---|---|---|
| Μοναδική πηγή | Πράξεις διακίνησης αγαθών που υπολογίζονται χρησιμοποιώντας αυτήν την παραλλαγή του προβλήματος:
|
|
| Πολλαπλών Πηγών | Οι συμπιέσεις που υπολογίζονται χρησιμοποιώντας αυτήν την έκδοση του προβλήματος είναι συνήθως 10-15% πιο συμπαγείς σε σύγκριση με τις συμπιέσεις που υπολογίζονται χρησιμοποιώντας την επιλογή "Μονής πηγής". Αλλά σημειώνουμε επίσης ότι όσο μικρότερος είναι ο αριθμός των υπολειμμάτων στα κύτταρα δότες, τόσο μικρότερη είναι η διαφορά στη συμπαγή | Πράξεις διακίνησης αγαθών που υπολογίζονται χρησιμοποιώντας αυτήν την παραλλαγή του προβλήματος:
|
Πίνακας 1. Πλεονεκτήματα και μειονεκτήματα των επιλογών Single-Source και Multi-Source.
Δεδομένου ότι η επιλογή Single-Source έχει περισσότερα πλεονεκτήματα και λαμβάνοντας επίσης υπόψη το γεγονός ότι όσο μικρότερος είναι ο αριθμός των υπολειμμάτων στα κύτταρα δότη, τόσο μικρότερη είναι η διαφορά στον βαθμό συμπίεσης που υπολογίζεται και για τις δύο παραλλαγές του προβλήματος, η επιλογή μας έπεσε στην την επιλογή Single-Source.
Αξίζει να πούμε ότι η λύση στην επιλογή Multi-Source επίσης λαμβάνει χώρα. Υπάρχει ένας μεγάλος αριθμός αποτελεσματικών αλγορίθμων για την επίλυσή του, οι περισσότεροι από τους οποίους καταλήγουν στην επίλυση ενός αριθμού προβλημάτων μεταφοράς. Υπάρχουν επίσης όχι μόνο αποτελεσματικοί αλγόριθμοι, αλλά και κομψοί, για παράδειγμα,
Προετοιμασία δεδομένων εισόδου
Πριν αρχίσουμε να αναλύουμε και να αναπτύσσουμε έναν αλγόριθμο για την επίλυση ενός προβλήματος, είναι απαραίτητο να αποφασίσουμε ποια δεδομένα και σε ποια μορφή θα τα τροφοδοτήσουμε ως είσοδο. Δεν υπάρχουν προβλήματα με τον όγκο των εναπομεινάντων αγαθών στις κυψέλες δότη και τη χωρητικότητα των κυψελών δοχείων, καθώς αυτό είναι ασήμαντο - τέτοιες ποσότητες θα μετρηθούν σε m3, αλλά με το κόστος χρήσης μιας κυψέλης κοντέινερ και τη μήτρα κινούμενου κόστους, όχι τα πάντα είναι τόσο απλό!
Ας δούμε πρώτα τον υπολογισμό κόστος μετακίνησης εμπορευμάτων από το κύτταρο δότη στο κύτταρο δοχείου. Πρώτα απ 'όλα, είναι απαραίτητο να αποφασίσουμε σε ποιες μονάδες μέτρησης θα υπολογίσουμε το κόστος μετακίνησης. Οι δύο πιο προφανείς επιλογές είναι τα μέτρα και τα δευτερόλεπτα. Δεν έχει νόημα να υπολογίζουμε το κόστος ταξιδιού σε «καθαρά» μέτρα. Ας το δείξουμε αυτό με ένα παράδειγμα. Αφήστε το κελί που βρίσκεται στην πρώτη βαθμίδα, κελί αφαιρείται κατά 30 μέτρα και βρίσκεται στη δεύτερη βαθμίδα:
- Μετακίνηση από в πιο ακριβά από τη μετακόμιση από в , αφού το να κατέβεις από τη δεύτερη βαθμίδα (1,5-2 μέτρα από το πάτωμα) είναι πιο εύκολο από το να ανέβεις στη δεύτερη, αν και η απόσταση θα είναι ίδια.
- Μετακίνηση 1 τεμ. αγαθά από το κελί в Θα είναι πιο εύκολο από το να μετακινήσετε 10 κομμάτια. το ίδιο προϊόν, αν και η απόσταση θα είναι ίδια.
Είναι καλύτερο να λάβετε υπόψη το κόστος μετακίνησης σε δευτερόλεπτα, καθώς αυτό σας επιτρέπει να λάβετε υπόψη τόσο τη διαφορά στα επίπεδα όσο και τη διαφορά στην ποσότητα των αγαθών που μετακινήθηκαν. Για να υπολογίσουμε το κόστος της κίνησης σε δευτερόλεπτα, πρέπει να αποσυνθέσουμε τη λειτουργία κίνησης σε βασικά στοιχεία και να λάβουμε μετρήσεις χρόνου για την εκτέλεση κάθε στοιχειώδους στοιχείου.
Αφήστε από το κελί κινείται Η/Υ. εμπορεύματα σε κοντέινερ . ας – η μέση ταχύτητα κίνησης ενός εργάτη στην αποθήκη, μετρημένη σε m/sec. Αφήνω и – οι μέσες ταχύτητες των εφάπαξ εργασιών παίρνουν και βάζουν, αντίστοιχα, για όγκο εμπορευμάτων ίσο με 4 dm3 (ο μέσος όγκος που παίρνει ένας εργαζόμενος κάθε φορά σε μια αποθήκη όταν εκτελεί εργασίες). Αφήνω и το ύψος των κυψελών από τα οποία εκτελούνται οι λειτουργίες λήψης και τοποθέτησης, αντίστοιχα. Για παράδειγμα, το μέσο ύψος της πρώτης βαθμίδας (ορόφου) είναι 1 m, της δεύτερης βαθμίδας είναι 2 m, κ.λπ. Τότε ο τύπος για τον υπολογισμό του συνολικού χρόνου για την ολοκλήρωση μιας πράξης μετακίνησης είναι Επόμενο:
Ο Πίνακας 2 παρουσιάζει στατιστικά στοιχεία για το χρόνο εκτέλεσης κάθε στοιχειώδους λειτουργίας, που συλλέγονται από τους υπαλλήλους της αποθήκης, λαμβάνοντας υπόψη τις ιδιαιτερότητες των αποθηκευμένων εμπορευμάτων.
| Όνομα επιχείρησης | Ονομασία | Σημαίνω |
|---|---|---|
| Μέση ταχύτητα ενός εργάτη που κινείται γύρω από την αποθήκη | |
1,5 m/s |
| Μέση ταχύτητα μίας λειτουργίας προς εκτέλεση (για όγκο προϊόντος 4 dm3) | |
2,4 sec |
Πίνακας 2. Μέσος χρόνος για την ολοκλήρωση των εργασιών της αποθήκης
Αποφασίσαμε τη μέθοδο υπολογισμού του κόστους μετακόμισης. Τώρα πρέπει να καταλάβουμε πώς να υπολογίσουμε κόστος επιλογής κυψέλης δοχείου. Όλα εδώ είναι πολύ, πολύ πιο περίπλοκα από ό,τι με το κόστος μετακίνησης, γιατί:
- Πρώτον, το κόστος θα πρέπει να εξαρτάται άμεσα από τον όγκο του κυττάρου - ο ίδιος όγκος υπολειμμάτων που μεταφέρεται από τα κύτταρα δότη τοποθετείται καλύτερα σε δοχείο μικρότερου όγκου από ό,τι σε μεγάλο δοχείο, υπό την προϋπόθεση ότι αυτός ο όγκος ταιριάζει πλήρως και στα δύο δοχεία. Έτσι, ελαχιστοποιώντας το συνολικό κόστος της επιλογής εμπορευματοκιβωτίων, προσπαθούμε να εξοικονομήσουμε «σπάνια» δωρεάν χωρητικότητα αποθήκευσης στην περιοχή επιλογής για να εκτελέσουμε επακόλουθες εργασίες τοποθέτησης αγαθών σε κελιά. Το Σχήμα 4 δείχνει τις επιλογές για τη μεταφορά υπολειμμάτων σε μεγάλα και μικρά δοχεία και τις συνέπειες αυτών των επιλογών μεταφοράς σε επακόλουθες εργασίες αποθήκης.
- Δεύτερον, εφόσον για την επίλυση του αρχικού προβλήματος πρέπει να ελαχιστοποιήσουμε ακριβώς το συνολικό κόστος, και αυτό είναι το άθροισμα τόσο του κόστους μετακίνησης όσο και του κόστους επιλογής δοχείων, τότε οι όγκοι των κυψελών σε κυβικά μέτρα πρέπει να συνδέονται με κάποιο τρόπο με δευτερόλεπτα. που κάθε άλλο παρά ασήμαντο.
Ρύζι. 4. Επιλογές μεταφοράς υπολειμμάτων σε δοχεία διαφορετικής χωρητικότητας.
Το σχήμα 4 δείχνει με κόκκινο τον όγκο των υπολειμμάτων που δεν χωρούν πλέον στο δοχείο στο δεύτερο στάδιο της τοποθέτησης των επόμενων εμπορευμάτων.
Θα σας βοηθήσει να συνδέσετε τα κυβικά μέτρα κόστους για την επιλογή ενός δοχείου με τα δευτερόλεπτα κόστους για τη μετακίνηση των ακόλουθων απαιτήσεων για υπολογισμένες λύσεις στο πρόβλημα:
- Είναι απαραίτητο τα υπόλοιπα από τον κάδο δότη να μετακινηθούν στον κάδο του δοχείου σε κάθε περίπτωση, εάν αυτό μειώνει τον συνολικό αριθμό των κάδων δοχείων που περιέχουν το προϊόν.
- Είναι απαραίτητο να διατηρείται μια ισορροπία μεταξύ του όγκου των εμπορευματοκιβωτίων και του χρόνου που αφιερώνεται στη μετακίνηση: για παράδειγμα, εάν σε μια νέα λύση σε ένα πρόβλημα σε σύγκριση με την προηγούμενη λύση, το κέρδος σε όγκο είναι μεγάλο, αλλά η απώλεια σε χρόνο είναι μικρή , τότε είναι απαραίτητο να επιλέξετε μια νέα επιλογή.
Ας ξεκινήσουμε με την τελευταία απαίτηση. Προκειμένου να διευκρινιστεί η διφορούμενη λέξη «υπόλοιπο», πραγματοποιήσαμε μια έρευνα σε υπαλλήλους της αποθήκης για να μάθουμε τα ακόλουθα. Αφήστε να υπάρχει ένα κελί δοχείου όγκου , στην οποία εκχωρείται η μετακίνηση των υπόλοιπων αγαθών από τα κύτταρα δωρητών και ο συνολικός χρόνος αυτής της μετακίνησης είναι ίσος με . Ας υπάρχουν πολλές εναλλακτικές επιλογές για την τοποθέτηση της ίδιας ποσότητας αγαθών από τα ίδια κύτταρα δότη σε άλλα δοχεία, όπου κάθε τοποθέτηση έχει τις δικές της εκτιμήσεις Όπου < и Όπου >.
Τίθεται το ερώτημα: ποιο είναι το ελάχιστο κέρδος σε όγκο αποδεκτή, για δεδομένη τιμή απώλειας χρόνου ? Ας εξηγήσουμε με ένα παράδειγμα. Αρχικά, τα υπολείμματα έπρεπε να τοποθετηθούν σε δοχείο με όγκο 1000 dm3 (1 m3) και ο χρόνος μεταφοράς ήταν 70 δευτερόλεπτα. Υπάρχει δυνατότητα τοποθέτησης των υπολειμμάτων σε άλλο δοχείο με όγκο 500 dm3 και χρόνο 130 δευτερόλεπτα. Ερώτηση: είμαστε έτοιμοι να αφιερώσουμε επιπλέον 60 δευτερόλεπτα από τον χρόνο του αποθηκευτή για τη μετακίνηση των εμπορευμάτων προκειμένου να εξοικονομήσουμε 500 dm3 δωρεάν όγκου; Με βάση τα αποτελέσματα έρευνας των υπαλλήλων της αποθήκης, συντάχθηκε το παρακάτω διάγραμμα.
Ρύζι. 5. Διάγραμμα εξάρτησης της ελάχιστης επιτρεπόμενης εξοικονόμησης όγκου από την αύξηση της διαφοράς στο χρόνο λειτουργίας
Δηλαδή, εάν το επιπλέον κόστος χρόνου είναι 40 δευτερόλεπτα, τότε είμαστε έτοιμοι να τα ξοδέψουμε μόνο όταν το κέρδος σε όγκο είναι τουλάχιστον 500 dm3. Παρά το γεγονός ότι υπάρχει μια μικρή μη γραμμικότητα στην εξάρτηση, για την απλότητα των περαιτέρω υπολογισμών θα υποθέσουμε ότι η εξάρτηση μεταξύ των ποσοτήτων είναι γραμμική και περιγράφεται από την ανισότητα
Στο παρακάτω σχήμα, εξετάζουμε τις ακόλουθες μεθόδους τοποθέτησης εμπορευμάτων σε δοχεία.
Ρύζι. 6. Επιλογή (α): 2 δοχεία, συνολικός όγκος 400 dm3, συνολικός χρόνος 150 sec.
Ρύζι. 6. Επιλογή (β): 2 δοχεία, συνολικός όγκος 600 dm3, συνολικός χρόνος 190 sec.
Ρύζι. 6. Επιλογή (γ): 1 δοχείο, συνολικός όγκος 400 dm3, συνολικός χρόνος 200 sec.
Η επιλογή (α) για την επιλογή δοχείων είναι προτιμότερη από την αρχική επιλογή, καθώς ισχύει η ανισότητα: (800-400)/10>=150-120, που σημαίνει 40 >= 30. Η επιλογή (β) είναι λιγότερο προτιμότερη από την αρχική επιλογή , αφού η ανισότητα δεν ισχύει: (800-600)/10>=190-150 που σημαίνει 20 >= 40. Αλλά η επιλογή (γ) δεν ταιριάζει σε τέτοια λογική! Ας εξετάσουμε αυτή την επιλογή με περισσότερες λεπτομέρειες. Από τη μία πλευρά, η ανισότητα (800-400)/10>=200-120, που σημαίνει ότι η ανισότητα 40 >= 80 δεν ικανοποιείται, γεγονός που υποδηλώνει ότι το κέρδος σε όγκο δεν αξίζει μια τόσο μεγάλη απώλεια στο χρόνο.
Αλλά από την άλλη πλευρά, σε αυτήν την επιλογή (γ) όχι μόνο μειώνουμε τον συνολικό κατειλημμένο όγκο, αλλά μειώνουμε επίσης τον αριθμό των κατειλημμένων κελιών, που είναι η πρώτη από τις δύο σημαντικές απαιτήσεις για υπολογιστικές λύσεις στα προβλήματα που αναφέρονται παραπάνω. Προφανώς, για να αρχίσει να εκπληρώνεται αυτή η απαίτηση, είναι απαραίτητο να προστεθεί κάποια θετική σταθερά στην αριστερή πλευρά της ανισότητας , και μια τέτοια σταθερά χρειάζεται να προστεθεί μόνο όταν ο αριθμός των δοχείων μειωθεί. Ας το θυμηθούμε είναι μια μεταβλητή ίση με 1 όταν το δοχείο επιλεγμένο και 0 όταν κοντέινερ μη επιλεγμένο. Ας υποδηλώσουμε – πολλά δοχεία στο αρχικό διάλυμα και – πολλά δοχεία στη νέα λύση. Γενικά, η νέα ανισότητα θα μοιάζει με αυτό:
Μετασχηματίζοντας την παραπάνω ανισότητα, παίρνουμε
Με βάση αυτό, έχουμε έναν τύπο για τον υπολογισμό του συνολικού κόστους κάποια λύση στο πρόβλημα:
Τώρα όμως τίθεται το ερώτημα: τι τιμή πρέπει να έχει μια τέτοια σταθερά; ? Προφανώς, η αξία του πρέπει να είναι αρκετά μεγάλη ώστε να καλύπτεται πάντα η πρώτη απαίτηση για λύσεις στο πρόβλημα. Μπορείτε, φυσικά, να πάρετε την τιμή της σταθεράς ίση με 103 ή 106, αλλά θα ήθελα να αποφύγω τέτοιους «μαγικούς αριθμούς». Εάν λάβουμε υπόψη τις ιδιαιτερότητες της εκτέλεσης εργασιών αποθήκης, μπορούμε να υπολογίσουμε αρκετές καλά τεκμηριωμένες αριθμητικές εκτιμήσεις της τιμής μιας τέτοιας σταθεράς.
Αφήστε – η μέγιστη απόσταση μεταξύ κυψελών αποθήκης μιας ζώνης ABC, ίση στην περίπτωσή μας με 100 m. Έστω – ο μέγιστος όγκος μιας κυψέλης εμπορευματοκιβωτίων σε μια αποθήκη, ίσος στην περίπτωσή μας με 1000 dm3.
Ο πρώτος τρόπος υπολογισμού της τιμής . Ας εξετάσουμε μια κατάσταση όπου υπάρχουν 2 εμπορευματοκιβώτια στην πρώτη βαθμίδα, στα οποία τα αγαθά βρίσκονται ήδη φυσικά, δηλαδή τα ίδια είναι κύτταρα δότη και το κόστος μετακίνησης των αγαθών στα ίδια κελιά είναι φυσικά ίσο με 0. είναι απαραίτητο για να βρεθεί μια τέτοια τιμή για τη σταθερά , στο οποίο θα ήταν πλεονεκτικό να μετακινούνται πάντα τα υπολείμματα από το δοχείο 1 στο δοχείο 2. Αντικαθιστώντας τις τιμές и Στην ανισότητα που δίνεται παραπάνω παίρνουμε:
από το οποίο προκύπτει
Αντικαθιστώντας τις τιμές του μέσου χρόνου για την εκτέλεση στοιχειωδών πράξεων στον παραπάνω τύπο παίρνουμε
Ο δεύτερος τρόπος υπολογισμού της τιμής . Ας εξετάσουμε μια κατάσταση όπου υπάρχει κελιά δότη από τα οποία σχεδιάζεται η μεταφορά των αγαθών στο δοχείο 1. Ας υποδηλώσουμε – απόσταση από το κύτταρο δότη στο δοχείο 1. Υπάρχει επίσης το δοχείο 2, το οποίο περιέχει ήδη εμπορεύματα και ο όγκος του οποίου σας επιτρέπει να φιλοξενήσετε το υπόλοιπο όλων κύτταρα. Για λόγους απλότητας, θα υποθέσουμε ότι ο όγκος των αγαθών που μετακινήθηκαν από τα κελιά δότη σε δοχεία είναι ο ίδιος και ίσος με . Απαιτείται να βρεθεί μια τέτοια τιμή της σταθεράς , στο οποίο η τοποθέτηση όλων των υπολοίπων από κελιά στο δοχείο 2 θα ήταν πάντα πιο κερδοφόρα από την τοποθέτησή τους σε διαφορετικά δοχεία:
Μετασχηματίζοντας την ανισότητα που έχουμε
Για να «ενισχύουμε» την αξία της ποσότητας , ας υποθέσουμε ότι = 0. Ο μέσος αριθμός κυψελών που συνήθως εμπλέκονται στη διαδικασία συμπίεσης των υπολοίπων της αποθήκης είναι 10. Αντικαθιστώντας τις γνωστές τιμές των ποσοτήτων, έχουμε την ακόλουθη τιμή της σταθεράς
Παίρνουμε τη μεγαλύτερη τιμή που υπολογίζεται για κάθε επιλογή, αυτή θα είναι η αξία της ποσότητας για τις δεδομένες παραμέτρους της αποθήκης. Τώρα, για πληρότητα, ας γράψουμε τον τύπο για τον υπολογισμό του συνολικού κόστους για κάποια εφικτή λύση :
Τώρα, άλλωστε τιτανικές προσπάθειες Μετασχηματίζοντας τα δεδομένα εισόδου, μπορούμε να πούμε ότι όλα τα δεδομένα εισόδου έχουν μετατραπεί στην επιθυμητή μορφή και είναι έτοιμα για χρήση στον αλγόριθμο βελτιστοποίησης.
Συμπέρασμα
Όπως δείχνει η πρακτική, η πολυπλοκότητα και η σημασία του σταδίου προετοιμασίας και μετατροπής δεδομένων εισόδου για έναν αλγόριθμο συχνά υποτιμάται. Σε αυτό το άρθρο, δώσαμε ιδιαίτερη προσοχή σε αυτό το στάδιο για να δείξουμε ότι μόνο υψηλής ποιότητας και έξυπνα προετοιμασμένα δεδομένα εισόδου μπορούν να κάνουν τις αποφάσεις που υπολογίζονται από τον αλγόριθμο πραγματικά πολύτιμες για τον πελάτη. Ναι, υπήρχαν πολλές παράγωγες τύπων, αλλά σας προειδοποιήσαμε ακόμη και πριν από το kata :)
Στο επόμενο άρθρο θα καταλήξουμε επιτέλους σε αυτό για το οποίο προορίζονταν οι 2 προηγούμενες δημοσιεύσεις - έναν διακριτό αλγόριθμο βελτιστοποίησης.
Ετοίμασε το άρθρο
Roman Shangin, προγραμματιστής του τμήματος έργων,
Η εταιρεία First Bit, Chelyabinsk
Πηγή: www.habr.com