Περίληψη:
Σκοπός της εργασίας είναι η ανάπτυξη παράλληλων αλγορίθμων για την επίλυση ενός διάσημου προβλήματος βελτιστοποίησης του γραμμικού προγραμματισμού, γνωστό ως Bin Packing Problem. Το πρόβλημα έγκειται στη διαχείριση και τον καταμερισμό πεπερασμένου αριθμού «πακέτων» (packages), έτσι ώστε να τοποθετηθούν κατάλληλα και όσο το δυνατόν βέλτιστα σε «κάδους» (bins), με τέτοιο τρόπο, έτσι ώστε να επιτευχθεί ο μικρότερος δυνατός αριθμός κάδων σε χρήση.
Για την επίλυση αυτού του προβλήματος χρησιμοποιήθηκε ο αλγόριθμος Best Fit Decreasing (BFD) στο προγραμματιστικό εργαλείο Matlab και προσαρμόστηκε με κάποιες μεθόδους για τις ανάγκες της παραλληλοποίησης.
Τα αποτελέσματα που προκύπτουν αναλύονται και παρουσιάζονται ως προς τη φύρα (περισσευούμενος χώρος), τους κάδους που χρησιμοποιήθηκαν, καθώς επίσης και το χρόνο εκτέλεσης του αλγορίθμου στις εκάστοτε περιπτώσεις παραλληλοποίησής του.