Εξισορρόπηση γραμμών συναρμολόγησης με πολλαπλούς αντικειμενικούς στόχους με τη χρήση γενετικών αλγορίθμων
Authors: Ζαχαρία Παρασκευή 
Published: September 2021

Η παρούσα διδακτορική διατριβή έχει ως αντικείμενο την ανάπτυξη μεθόδων για την επίλυση του Προβλήματος Εξισορρόπησης Γραμμών Συναρμολόγησης (ΠΕΓΣ). Το ΠΕΓΣ είναι ένα πρόβλημα απόφασης για βέλτιστη κατανομή του φόρτoυ των εργασιών συναρμολόγησης μεταξύ των σταθμών εργασίας της γραμμής σε σχέση με ορισμένους επιθυμητούς αντικειμενικούς στόχους που έχουν να κάνουν με τη δυναμικότητα της γραμμής ή/και τα κόστη επένδυσης και λειτουργίας της. Ιδιαίτερη έμφαση δόθηκε στην επίλυση των τριών παραλλαγών του βασικού προβλήματος, που είναι γνωστές ως ΠΕΓΣ-1, ΠΕΓΣ-2 και ΠΕΓΣ-Ε. Το ΠΕΓΣ-1 και το ΠΕΓΣ-2 έχουν διπλή συσχέτιση: το πρώτο ελαχιστοποιεί τον αριθμό των σταθμών με δεδομένο τον χρόνο κύκλου εργασίας, ενώ το δεύτερο ελαχιστοποιεί τον χρόνο κύκλου εργασίας με δεδομένο τον αριθμό των σταθμών. Η πρώτη κατηγορία χρησιμοποιείται όταν μια νέα γραμμή συναρμολόγησης θα πρέπει να υλοποιηθεί και να εγκατασταθεί, ενώ η δεύτερη κατηγορία χρησιμοποιείται σε μια υφιστάμενη γραμμή συναρμολόγησης όταν υπάρχουν αλλαγές στη διαδικασία παραγωγής και απαιτήσεις κατασκευής. Το ΠΕΓΣ-Ε συνίσταται στην εύρεση μιας έγκυρης λύσης εξισορρόπησης (ανάθεσης δηλαδή των εργασιών στους σταθμούς) για συγκεκριμένο επιθυμητό συνδυασμό τιμών του αριθμού σταθμών και χρόνου κύκλου εργασίας, έτσι ώστε να μεγιστοποιείται η αποδοτικότητα της γραμμής.Η έρευνα για την εκπόνηση της παρούσας διδακτορικής διατριβής επικεντρώθηκε στην ανάπτυξη αποτελεσματικών μεθόδων για την επίλυση των τριών πιο πάνω μορφών του ΠΕΓΣ σε σχέση (α) με ασαφείς (fuzzy) χρόνους επεξεργασίας των εργασιών συναρμολόγησης και (β) πολλαπλά κριτήρια βελτιστοποίησης που σχετίζονται με τη μεγιστοποίηση της χρησιμοποίησης της δυναμικότητας της γραμμής όπως είναι: ο χρόνος κύκλου εργασίας (cycle time), ο δείκτης ομαλότητας (smoothness index) και ο χρόνος καθυστέρησης της εξισορρόπησης (balance delay time).Κάθε παραλλαγή του ΠΕΓΣ ανήκει στην κατηγορία των δυσεπίλυτων (NP-hard) συνδυαστικών προβλημάτων βελτιστοποίησης. Αυτό σημαίνει ότι ΠΕΓΣ μεγάλου μεγέθους (που περιλαμβάνουν δηλαδή μεγάλο πλήθος εργασιών συναρμολόγησης) δεν μπορούν να αντιμετωπιστούν (σε εύλογο χρόνο) με κλασσικές μεθόδους μαθηματικού προγραμματισμού (ακριβείς αλγόριθμους βελτιστοποίησης) όπως είναι οι μέθοδοι κλάδου-φράγματος (branch and bound) και ο δυναμικός προγραμματισμός. Συνεπώς, για αυτά τα προβλήματα η χρήση ευρετικών αλγορίθμων (heuristics) είναι η πιο ενδεδειγμένη κατεύθυνση στην οποία πρέπει να στραφεί η όποια ερευνητική προσπάθεια.Με βάση αυτό το επιστημονικό περίγραμμα, στα πλαίσια της διατριβής μελετήθηκε η χρήση γενετικών αλγορίθμων (genetic algorithms) για την επίλυση πολυκριτηριακών ΠΕΓΣ με ασαφείς χρόνους επεξεργασίας των εργασιών. Οι γενετικοί αλγόριθμοι είναι προσεγγιστικοί πληθυσμιακοί αλγόριθμοι που ακολουθούν το παράδειγμα των γενετικών πληθυσμών και έχουν αποδειχθεί εύρωστοι και αρκετά αποτελεσματικοί στην αντιμετώπιση παρόμοια δύσκολων και υπολογιστικά δυσεπίλυτων προβλημάτων απόφασης. Επισημαίνεται ότι, η έρευνα που διεξήχθηκε στα πλαίσια της διατριβής οδήγησε στα πρώτα στη σχετική βιβλιογραφία αποτελέσματα που αφορούν τις συγκεκριμένες μορφές ΠΕΓΣ με ασαφείς χρόνους εκτέλεσης των εργασιών.Επιπλέον, εκτός από τις πιο πάνω παραλλαγές του ΠΕΓΣ η διατριβή καταπιάνεται με μια επιπρόσθετη παραλλαγή του προβλήματος στην οποία ο χρόνος επεξεργασίας της κάθε εργασίας συναρμολόγησης διαφέρει ανάλογα με το ποιος εργαζόμενος έχει ανατεθεί για την εκτέλεση της. Η συγκεκριμένη παραλλαγή μόλις πολύ πρόσφατα άρχισε να απασχολεί τους ερευνητές και τα αποτελέσματα που παράχθηκαν στα πλαίσια της διατριβής είναι από τα ελάχιστα πρώτα που έχουν πρόσφατα δημοσιευτεί. Η συγκεκριμένη έκδοση του βασικού προβλήματος, που είναι γνωστή στη βιβλιογραφία ως ΠΕΓΣ με ανάθεση εργατών, αναζήτά τη βέλτιστη ανάθεση των εργασιών συναρμολόγησης στους εργάτες, όπως επίσης και των εργατών στους σταθμούς λαμβάνοντας υπόψη κάποιους επιθυμητούς αντικειμενικούς στόχους. Μελετάται το πρόβλημα δύο κριτηρίων με στόχο την ελαχιστοποίηση του χρόνου κύκλου εργασίας και της ομαλότητας του φόρτου εργασίας μεταξύ των σταθμών. Εξ’ όσων γνωρίζουμε δεν υπάρχει δημοσιευμένη εργασία που να μελετά το πρόβλημα εξισορρόπησης γραμμών συναρμολόγησης με εργάτες στο πλαίσιο της πολυκριτηριακής βελτιστοποίησης.Τέλος, σημειώνεται ότι για την πειραματική μελέτη της απόδοσης των αλγορίθμων που αναπτύχθηκαν, χρησιμοποιήθηκαν γνωστά δύσκολα (benchmarks) προβλήματα αναφοράς που υπάρχουν στη βιβλιογραφία και των οποίων οι βέλτιστες τιμές της αντικειμενικής συνάρτησης είναι γνωστές. Τα αποτελέσματα καταδεικνύουν υψηλή απόδοση για τους προτεινόμενους αλγορίθμους τόσο σε όρους ποιότητας λύσεων, όσο και σε όρους υπολογιστικού χρόνου.