Αλγόριθμος βελτιστοποίησης τύπου Nested Partitions για τη σχεδίαση βιομηχανικών συστημάτων: συγκριτική μελέτη με άλλους αλγορίθμους
Creators: name: Παπακρίβος, Χρήστος Παναγιώτη
Publisher: name: Aristotle University of Thessaloniki
Year: 2009
Subjects: Σειριακές γραμμές παραγωγής
Αξιόπιστες γραμμές παραγωγής
Πρόβλημα κατανομής αποθηκευτικών χώρων
Αλγόριθμος Βελτιστοποίησης Nested Partitions
Υβριδική μέθοδος NP-Gradient
Serial production lines
Reliable production lines
Buffer allocation problem
Nested partitions
optimisation algorithm
Hybrid method NP-Gradient

description: Η εργασία αυτή ασχολείται με την ανάπτυξη και υλοποίηση ενός υβριδικού αλγορίθμου για την επίλυση του προβλήματος της βέλτιστης κατανομής των αποθηκευτικών χώρων σε μια γραμμή παραγωγής. Ο προτεινόμενος αλγόριθμος βασίζεται στον αλγόριθμο Nested Partitions (NP) που προτάθηκε από τους Shi και Olafsson (2000), ο οποίος τροποποιήθηκε έτσι ώστε να μπορεί να λειτουργεί με την εκτιμητική μέθοδο που αναπτύχθηκε από τους Diamantidis, Heavey και Papadopoulos (2005). Υλοποιήθηκε ένας υβριδικός αλγόριθμος που συνδυάζει τον προτεινόμενο αλγόριθμο NP με μια τροποποίηση έκδοση του αλγορίθμου Gradient. Επειδή ο προτεινόμενος αλγόριθμος χρησιμοποιεί τυχαία δειγματοληψία, δοκιμάσθηκε με πολλούς διαφορετικούς αριθμούς δειγμάτων, όπου διαπιστώθηκαν τα όρια του αλγορίθμου και πραγματοποιήθηκε πειραματισμός σε σειριακές, διακριτές και αξιόπιστες γραμμές παραγωγής μικρού και μεσαίου μεγέθους (έως 12 και έως 20 σταθμούς εργασίας αντίστοιχα), με παράλληλες μηχανές στους σταθμούς εργασίας. Από τα αποτελέσματα των δοκιμών προκύπτει ότι ο υβριδικός αλγόριθμος έχει πολύ καλή συμπεριφορά σε γραμμές παραγωγής μικρού μεγέθους με σφάλματα απόδοσης που δεν ξεπερνούν το 0,2%, ενώ στις μεσαίου μεγέθους γραμμές η ακρίβεια υπολογισμού δεν είναι αρκετά καλή αφού το σφάλμα πλησίασε το 9,7%. Όσον αφορά στο χρόνο σύγκλισης του αλγορίθμου, στις μικρές γραμμές παραγωγής ο χρόνος είναι ικανοποιητικός ενώ στις μεσαίου μεγέθους είναι υπερβολικός.
description: This work deals with the development and implementation of a hybrid algorithm for the resolution of the Buffer Allocation Problem (BAP), in industrial systems with linear production lines. The proposed algorithm is based in the Nested Partitions (NP) algorithm that proposed by Shi and Olafsson (2000), which was modified so as to functions with the estimative function proposed by Diamantidis, Heavey and Papadopoulos (2005). A hybrid algorithm was implemented that combines the proposed NP algorithm with a modified version of Gradient algorithm. The proposed algorithm uses random sampling, so it was tested with a lot of different numbers of samples and determined algorithm’s limits. The algorithm tested in small and medium size serial, distinguishable and reliable production lines (until 12 and 20 work stations respectively), with parallel machines in each work station. The results shows that the algorithm work well in small size production lines, with faults that do not exceed the 0,2%, while in intermediate size lines the precision of solutions is not good enough because the fault approached 9,7%. With regard to the algorithm’s time of convergence, in small lines of production the time is satisfactory while in intermediate it is excessive.