Συστήματα αλγορίθμων λεπτομερειακού χρονικού προγραμματισμού παραγωγής
Authors: Σπανός Αθανάσιος 
Published: August 2021

Σκοπός της παρούσας διατριβής είναι να διερευνήσει ενδελεχώς τις δυνατότητες εφαρμογής των σύνθετων και πολύπλοκων υβριδικών μεταευρετικών αλγορίθμων του θεωρητικού λεπτομερειακού προγραμματισμού παραγωγής σε πρακτικά προβλήματα. Η ντετερμινιστική μορφή του λεπτομερειακού προγραμματισμού παραγωγής, το λεγόμενο και JSSP (Job Shop Scheduling Problem), έχει απασχολήσει ερευνητές ανά τον κόσμο συστηματικά τις τελευταίες πέντε δεκαετίες. Η βιβλιογραφική ανασκόπηση και υπολογιστική σύγκριση μεταξύ state-of-the-art αλγορίθμων κατέδειξε πως δεν υπάρχει μεμονωμένη στρατηγική που να δύναται να επιλύσει αυτό το δυσεπίλυτο και πολύπλοκο πρόβλημα. Ως εκ τούτου, η έρευνα έχει στραφεί σε γενικευμένους υβριδικούς μεταευρετικούς αλγορίθμους και ειδικούς ευρετικούς μηχανισμούς. Οι μεν πρώτοι αξιοποιούνται κατά κύριο λόγο για τον απεγκλωβισμό της αναζήτησης από τοπικά βέλτιστα, ενώ οι δε δεύτεροι αξιοποιούν γνώση συσχετιζόμενη με το χώρο λύσεων του JSSP. Οι σύγχρονοι state-of-the-art αλγόριθμοι υποβοηθούμενοι πάντα από τη διαρκή εξέλιξη των επεξεργαστών και την επαύξηση της υπολογιστικής ισχύος, έχουν κατορθώσει να επιτυγχάνουν πολύ υψηλή απόδοση και σταθερότητα με μικρό σχετικά υπολογιστικό κόστος για την πλειοψηφία των προβλημάτων μέτρησης απόδοσης του JSSP. Μολαταύτα, γεννάται το ερώτημα: τέτοιου είδους αλγόριθμοι είναι εφαρμόσιμοι και εξίσου αποδοτικοί στην πράξη; Μια πρώτη απάντηση δίνεται από το περιεχόμενο αυτής της διατριβής και συνοψίζεται ως εξής: δεν είναι εφαρμόσιμοι, παρεκτός αν παραμετροποιηθούν σε σημαντικό βαθμό, αλλοιώνοντας την πλειοψηφία των αρχικών τους χαρακτηριστικών, και συνδυαστούν με πρόσθετους ευρετικούς μηχανισμούς και εργαλεία υποστήριξης αποφάσεων. Στην απάντηση αυτή συνηγορεί και η αρχιτεκτονική των συστημάτων APS (Advanced Planning Scheduling) που στοχεύουν στην επίλυση δυναμικών προβλημάτων λεπτομερειακού προγραμματισμού παραγωγής. Τα συστήματα αυτά ενσωματώνουν είτε αναλυτικούς, είτε γενικευμένους προσεγγιστικούς αλγορίθμους και τους ενισχύουν με μια σειρά εργαλείων για την υποστήριξη του χρήστη στη λήψη αποφάσεων. Δυστυχώς, χαρακτηρίζονται από μια σειρά μειονεκτημάτων όπως το υψηλό κόστος κτήσης και παραμετροποίησης, η εξαιρετικά χρονοβόρα διαδικασία δημιουργίας πλάνων παραγωγής, η περιττή λειτουργικότητα, η αδυναμία αφομοίωσης των ιδιαιτεροτήτων της παραγωγής από τους διαθέσιμους αλγόριθμους κ.α.. Συνεπώς, είναι προφανές πως ιδίως για SMEs (Small to Medium Enterprises) τα APS καθίστανται απαγορευτικά και είναι σκόπιμη μια εναλλακτική προσέγγιση. Αυτή είναι και η κύρια συνεισφορά της διατριβής: μια προσέγγιση για την καλύτερη δυνατή εφαρμογή λίαν αποδοτικών αλγορίθμων του JSSP σε πρακτικά προβλήματα υπό τη μορφή ολοκληρωμένων συστημάτων υποστήριξης αποφάσεων DSS (Decision Support Systems). Προκειμένου να καταστρωθεί αυτή η προσέγγιση η ερευνητική διαδικασία χωρίστηκε σε δύο μέρη. Το πρώτο μέρος σχετίζεται με θεματικές ενότητες που άπτονται του ντετερμινιστικού λεπτομερειακού προγραμματισμού παραγωγής. Αρχικά, μελετώνται οι ιδιότητες και το θεωρητικό υπόβαθρο του χώρου λύσεων του JSSP και αναλύονται όλοι οι διαθέσιμοι αλγόριθμοι για την επίλυση προβλημάτων διακριτής βελτιστοποίησης. Εν συνεχεία, τα χρήσιμα συμπεράσματα της ανασκόπησης αξιοποιούνται για την ανάπτυξη ενός παράλληλου υβριδικού μεταευρετικού αλγορίθμου που συνδυάζει γενετικούς αλγόριθμους με αναζήτηση tabu. Τέλος, η αποδοτικότητα του αλγοριθμικού μοντέλου αξιολογείται κατά την εφαρμογή του σε 242 προβλήματα μέτρησης απόδοσης διακριτής παραγωγής (JSSP) και 40 ροϊκής (FSSP- Flow Shop Scheduling Problem). Είναι άξιο μνείας πως ο εν λόγω αλγόριθμος αποδείχθηκε state-of-the-art για το FSSP και ως η state-of-the-art μέθοδος γενετικής τοπικής αναζήτησης για το JSSP. Κατά το δεύτερο μέρος εξετάζεται ποια είναι η προτιμητέα ατραπός για την προσαρμογή του προτεινόμενού αλγορίθμου σε δυναμικά προβλήματα λεπτομερειακού προγραμματισμού. Αρχικά, μελετάται η διάσταση μεταξύ θεωρίας και πράξης και υπερτονίζονται τα σημεία που χρίζουν ιδιαίτερης προσοχής. Κατόπιν, διενεργείται βιβλιογραφική ανασκόπηση αναφορικά με τους αλγόριθμους, τη λειτουργικότητα και τις εφαρμογές των συστημάτων APS. Βάσει των προκύπτοντων συμπερασμάτων, ο προτεινόμενος αλγόριθμος μορφοποιείται ως το DSS eGantt. Η αποδοτικότητα του eGantt αξιολογείται καθολικά από την εφαρμογή του σε μελέτη περίπτωσης, προερχόμενη από τον κλάδο μεταποίησης μετάλλου και ειδικότερα την κλειθροποιḯα. Τα συγκεντρωτικά αποτελέσματα του πρώτου και του δεύτερου μέρους επικυρώνουν την προτεινόμενη προσέγγιση της διατριβής.