Περίληψη:
Στην παρούσα μελέτη, με αφορμή το πρόβλημα βελτιστοποίησης του γραμμικού προγραμματισμού “Bin Packing Problem” θα παρουσιαστεί η υλοποίηση ενός παράλληλου αλγόριθμου με σκοπό την επίλυση του προβλήματος.
Ο αλγόριθμος που χρησιμοποιήθηκε είναι ο Best Fit Decreasing (BFD) ο οποίος υλοποιήθηκε με τη γλώσσα προγραμματισμού JAVA στο προγραμματιστικό περιβάλλον Eclipse.
Θα παρουσιαστούν δύο μέθοδοι υλοποίησης του αλγορίθμου. Στην πρώτη περίπτωση, τα δεδομένα (βάρη) χωρίζονται σε ομάδες και εκτελείται ο αλγόριθμος στην καθεμία ανεξάρτητα ενώ, στην δεύτερη, ορισμένα από τα δεδομένα είναι κοινά και έτσι η εκτέλεση του αλγορίθμου είναι ενιαία.
Στα πλαίσια του διαμοιρασμού των βαρών θα χρησιμοποιηθούν τρεις τρόποι διανομής, ο εναλλάξ, ο block ανά 5 και η reverse.
Τα αποτελέσματα που προκύπτουν αναλύονται και παρουσιάζονται ως προς τη φύρα και το χρόνο εκτέλεσης του αλγορίθμου στις εκάστοτε περιπτώσεις παραλληλοποίησής του.
Τέλος, παρουσιάζονται τα βήματα της υλοποίησης του παράλληλου αλγόριθμου με τη γλώσσα Java.