Optimization methods for production scheduling
Authors: Κασαπίδης Γρηγόριος 
Published: December 2022

Αυτή η διδακτορική διατριβή προτείνει νέες μεθόδους βελτιστοποίησης για την επίλυση πληθώρας παραλλαγών του Προβλήματος Χρονοπρογραμματισμού σε Συστήματα Ευέλικτων Εργασιών (ΠΧΣΕΕ). Το ΠΧΣΕΕ είναι ένα πρόβλημα βελτιστοποίησης με NP-δυσκολία που εισήχθει από τον Brucker et. al. 1990. Η βασική διατύπωση του ΠΧΣΕΕ είναι γενική, επεκτάσιμη και έχει χρησιμοποιηθεί για την μοντελοποίηση πληθώρας λειτουργικών χαρακτηριστικών και ρεαλιστικών διεργασιών παραγωγής που εμφανίζονται σε μεγάλο αριθμό περιβαλλόντων παραγωγής (Li et. al. 2020). Επιπρόσθετα και λόγω της δυσκολίας του, το ΠΧΣΕΕ αποτελεί το κύριο αντικείμενο μελέτης πολλαπλών ερευνητικών εργασιών οι οποίες αποσκοπούν στην ανάπτυξη αποδοτικών αλγορίθμων (μετα-ευρετικοί αλγόριθμοι) για την παραγωγή υψηλής ποιότητας λύσεων σε μικρούς υπολογιστικούς χρόνους. Η κλασσική εκδοχή του ΠΧΣΕΕ ορίζεται ως εξής: Υπάρχει ένα σύνολο εργασιών, όπου κάθε εργασία αποτελείται από μια ή περισσότερες διαδικασίες/δραστηριότητες. Κάθε διαδικασία μπορεί να εκτελεστεί από μία ή περισσότερες μηχανές με διαφορετικούς χρόνους επεξεργασίας. Κάθε διαδικασία μπορεί να έχει το πολύ μια διάδοχη ή προκάτοχη διαδικασία. Ακόμη, κάθε μηχανή μπορεί να εκτελεί μία διαδικασία σε κάθε χρονική στιγμή, ενώ δεν επιτρέπεται η κατακερματισμένη εκτέλεση οποιασδήποτε διαδικασίας. Ο σκοπός είναι η ελαχιστοποίηση του χρόνου ολοκλήρωσης της αργότερης διαδικασίας. Μία από τις παραλλαγές του ΠΧΣΕΕ στην οποία επικεντρώνεται αυτή η διατριβή, είναι το ΠΧΣΕΕ με αυθαίρετους γράφους προτεραιοτήτων. Αυτή η παραλλαγή αποσκοπεί στην γενίκευση του ΠΧΣΕΕ θεωρώντας αυθαίρετους γράφους προτεραιοτήτων οι οποίοι μπορούν να χρησιμοποιηθούν για την περιγραφή των συσχετίσεων των σχέσεων διαδοχής μεταξύ των διεργασιών μιας εργασίας. Για αυτό το πρόβλημα παρουσιάζονται μοντέλα μικτού ακέραιου προγραμματισμού, καθώς και προγραμματισμού περιορισμών (ΠΠ). Επιπρόσθετα, για την επίλυση του προβλήματος, προτείνεται ένας καινοτόμος εξελικτικός αλγόριθμος (ΕΑ). Αυτό το σχήμα υιοθετεί έναν μηχανισμό διασύνδεσης διαδρομών που βοηθά στον ανασυνδυασμό δύο ή παραπάνω λύσεων κατά τη διαδικασία εξέλιξης του πληθυσμού των λύσεων. Η εντατικοποίηση της αναζήτησης πραγματοποιείται χρησιμοποιώντας έναν αλγόριθμο απαγορευμένης έρευνας που είναι εξοπλισμένος με αποδοτικές μεθόδους εκτίμησης κόστους καθώς και εφικτότητας μιας κίνησης. Πιο συγκεκριμένα, για την εκτίμηση της εφικτότητας μιας κίνησης παρουσιάζονται νέα θεωρητικά αποτελέσματα τα οποία αποτελούν προεκτάσεις προηγούμενων θεωρητικών αποτελεσμάτων για το ΠΧΣΕΕ (Dauzere-Perez et.al. 1997). Λεπτομερή υπολογιστικά πειράματα σε γνωστά προβλήματα δείχνουν ότι ο ΕΑ που αναπτύχθηκε ξεπερνά σε απόδοση τους μέχρι στιγμής καλύτερους αλγόριθμους της βιβλιογραφίας. Ο ΕΑ παρήγαγε 59 βελτιωμένες λύσεις σε ένα σύνολο 228 προβλημάτων, ενώ ταυτόχρονα παρουσιάζονται 61 βελτιωμένα κατώτατα όρια. Για την εξερεύνηση της επίδρασης των αυθαίρετων γράφων προτεραιοτήτων στη ποιότητα των παραγόμενων προγραμμάτων παραγωγής, παρουσιάζονται λεπτομερή πειράματα σε ένα μικρού και μεγάλου μεγέθους προβλήματα. Σκοπός είναι η μελέτη της επίδρασης της ευελιξιμότητας του προβλήματος καθώς και της πυκνότητας των αυθαίρετων γράφων στην αντικειμενική συνάρτηση καθώς και στην δυσκολία παραγωγής καλών ανώτατων ορίων. Στη συνέχεια, σε μια προσπάθεια να καλυφθούν βιβλιογραφικά κενά σχετικά με προβλήματα που μελετούν συνδυασμούς διαφορετικών ειδών πόρων, τίθεται υπό μελέτη το πρόβλημα ΠΧΣΕΕ με πολλαπλούς περιορισμούς πόρων. Αυτή η παραλλαγή περιλαμβάνει ανανεώσιμες, μη ανανεώσιμες και συσσωρευτικούς πόρους με τη μορφή εργαλείων, ωφελιμοτήτων, ρυθμιστών περιορισμένης χωρητικότητας, ρυθμιστών για εν εξελίξει εργασίες καθώς και αυθαίρετων υλικών πόρων. Για την επίλυση αυτού του προβλήματος, προτείνεται ένας εξελικτικός αλγόριθμος βασισμένος σε ΠΠ. Αυτό το αλγοριθμικό πλαίσιο χρησιμοποιεί δομές μνήμης μεγάλης διάρκειας για την αποθήκευση πληροφοριών σχετικών με την ανάθεση διεργασιών σε μηχανές καθώς και ζευγών διεργασιών σε μηχανές, εφόσον αυτές έχουν εντοπισθεί σε υψηλής ποιότητας και διαφορετικές λύσεις κατά τη διάρκεια της εξερεύνησης του χώρου των λύσεων. Ακόμη προτείνονται χειριστές εξαγωγής περιορισμών οι οποίοι χρησιμοποιούν αυτές τις πληροφορίες προκειμένου να δημιουργήσουν συγκεκριμένες εξισώσεις περιορισμών οι οποίες λαμβάνονται υπόψιν από τον εκάστοτε επιλύτη ΠΠ προκειμένου να καθοδηγηθεί η εξερεύνηση σε υποσχόμενες περιοχές του χώρου των λύσεων. Η εμπεριστατωμένη πειραματική μελέτη πάνω σε γνωστά προβλήματα της βιβλιογραφίας υποδεικνύει την αποδοτικότητα και την υψηλή ανταγωνιστικότητα του αλγοριθμικού σχήματος σε σύγκριση με τους καλύτερους αλγορίθμους της βιβλιογραφίας. Επιπρόσθετα, παρουσιάζονται 34 νέες βελτιωμένες λύσεις για βιβλιογραφικά προβλήματα του ΠΧΣΕΕ, του Φραγμένου Προβλήματος Χρονοπρογραμματισμού Συστημάτων Εργασιών (ΦΠΧΣΕ) και του Προβλήματος Χρονοπρογραμματισμού σε μη Συσχετισμένες Παράλληλες Μηχανές με Πόρους (ΠΧΣΠΧ). Για την μελέτη της επίδρασης των διαφορετικών ειδών πόρων στην αντικειμενική συνάρτηση, διεξάγονται λεπτομερή υπολογιστικά πειράματα σε νέα μικρού και μεγάλου μεγέθους προβλήματα. Ένα ακόμα αντικείμενο της παρούσας διατριβής είναι η ενσωμάτωση μεθόδων βελτιστοποίησης σε συστήματα παραγωγής. Αρχικά, παρουσιάζεται η ενσωμάτωση μιας διαδικασίας βελτιστοποίησης σε ένα πλαίσιο Γνωστικού Ψηφιακού Διδύμου (ΓΨΔ). Αυτή η μέθοδος βελτιστοποίησης αναπτύσσεται ούτως ώστε να παρέχει λύσεις για το πρόβλημα χρονοπρογραμματισμού μιας αυτοκινητοβιομηχανίας. Το συγκεκριμένο πρόβλημα βελτιστοποίησης μοντελοποιείται σαν ένα ΠΧΣΕΕ με ανανεώσιμους και συσσωρευτικούς πόρους όπου επίσης συνυπολογίζονται προγραμματισμένες και μη διεργασίες συντήρησης. Σκοπός είναι η ελαχιστοποίηση της επίδρασης βλαβών μηχανών ή γραμμών παραγωγής στην ολοκλήρωση παραγγελιών μέσω του προσεκτικού χρονοπρογραμματισμού των διεργασιών συντήρησης. Ένα μοντέλο ΠΠ προτείνεται για την επίλυση του προβλήματος, ενώ επίσης παρουσιάζεται τόσο ο σχεδιασμός όσο και η ενσωμάτωση της μεθόδου βελτιστοποίησης σε ένα γενικότερο πλαίσιο ενός ΓΨΔ συστήματος. Για την εκτίμηση της αποδοτικότητας και της επίδοσης της προτεινόμενης μεθόδου βελτιστοποίησης, πραγματοποιούνται πειράματα τόσο σε πραγματικά όσο και σε συνθετικά δεδομένα. Ακόμη, παρουσιάζεται λεπτομερή υπολογιστικά πειράματα προκειμένου να γίνει μελέτη της επίδρασης των διεργασιών συντήρησης και των περιορισμών πόρων σε πληθώρα μετρικών παραγωγής όπως ο αργότερος χρόνος ολοκλήρωσης του προγράμματος, ο συνολικός χρόνος ροής καθώς και ο συνολικός χρόνος αδράνειας των μηχανών. Τέλος, παρουσιάζεται ένα Σύστημα Παραγωγής με Επίγνωση Καταστάσεων (ΣΠΕΚ). Το ΣΠΕΚ στοχεύει στην αναγνώριση και αντίδραση σε διαταραχές που μπορούν να συμβούν σε πραγματικά περιβάλλοντα παραγωγής, χρησιμοποιώντας νέες τεχνολογίες της Βιομηχανίας 4.0 όπως προγνωστική ανάλυση, εξομοίωση και βελτιστοποίηση. Το ΣΠΕΚ υιοθετεί μια προσέγγιση Έρευνας Επιστήμης Σχεδιασμού (ΕΕΣ) σε μια προσπάθεια να ενεργοποίηση την αναγνώριση και την διαχείριση διαταραχών, την απαρίθμηση των απαιτήσεων του χρήση καθώς και την επικύρωση της αποτελεσματικότητάς του συστήματος σε πρακτικό επίπεδο. Δύο εκδοχές του ΣΠΕΚ παρουσιάζονται οι οποίες αντιστοιχούν σε δύο πραγματικά περιβάλλοντα παραγωγής από τους χώρους των ηλεκτρονικών και της αυτοκινητοβιομηχανίας. Μια λεπτομερής υπολογιστική μελέτη παρουσιάζει την αποτελεσματικότητα και την επάρκεια του συστήματος και στις δύο περιπτώσεις.