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

Abstract

The objective of this thesis is the development of solution methods for the simple assembly line balancing problem (SALBP). The SALBP is a decision problem of optimally partitioning (balancing) the assembly work among the stations with respect to some objectives associated with the line capacity or/and the investment and operation costs. Most of the research work has been devoted to the solution of three main versions of the problem termed SALBP-1, SALBP-2 and SALBP-E. SALBP-1 and SALBP-2 have a dual relationship: the first minimizes the number of stations for a given fixed cycle time; the second minimizes the cycle time of the line for a given number of stations. The former type is used when a new assembly line has to be implemented and installed, while the latter type is used in an existing assembly line when changes in the production process and manufacturing requirements occur. SALBP-E consists of finding a combination of the number of workstations and the cycle time as well as a respective line balance such that the efficiency of the line is maximized.The research for this thesis has been focused on the development of effective methods for the solution of the aforementioned three versions of the problem with respect to (a) the fuzzy processing times and (b) multiple optimization criteria associated with the maximization of the capacity of the line such as the cycle time, the smoothness index and the balance delay time. Any variant of SALBP is of combinatorial nature and belongs to the NP-hard class of combinatorial optimization problems. This implies that the large problem instances (consisting of a large number of assembly tasks) can not be solved (in reasonable time) using the traditional programming methods, such as branch and bound methods and dynamic programming. Therefore, the right way to proceed and focus our research effort is through the use of heuristics techniques.On top of these versions of the SALBP, this thesis tackles a further version of the problem in which the processing times differ depending on the worker assigned to each task. This version known as the assembly line worker assignment and balancing problem (ALWABP) seeks the best assignment of the assembly tasks to workers as well as the workers to workstations in accordance with some desired objectives. A bi-objective ALWABP is studied aiming to minimize both the cycle time and workload smoothness among the stations. In all our knowledge no previous work in the literature studied ALWABP in the context of multi-objective optimization.To this end, in the context of this thesis, the use of genetic algorithms was studied for the solution of the multi-objective ALBPs with fuzzy processing times. Genetic algorithms are population-based approximation algorithms that follow the example of populations genetics and have been proved robust and effective in solving such difficult and computationally intractable decision problems. Note that the research conducted in this thesis led to the first results in the relevant literature concerning the specific versions of ALBP with fuzzy processing times.Finally, it is should be noted that the existing benchmark problems given in the literature were used for the experimental study of the algorithms’ performance for which the best values for the objective functions are known. The results showed high efficiency for the proposed methods concerning the quality of the produced solutions and the computational time.

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