Τεχνικές παράλληλης επεξεργασίας στο Bin Packing Problem

Abstract

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

The aim of the diploma thesis is to develop and study parallel algorithms to solve a famous optimization problem of linear programming, known as Bin Packing Problem. The problem lies in managing and allocating a finite number of packages so that they are properly and optimally positioned in bins in such a way that the smallest possible number of bins in use can be achieved. To solve this problem, the Best Fit Decreasing algorithm (BFD) was used in the Matlab programming tool and adapted with some methods for parallelization needs. The resulting results are analyzed and presented in terms of waste (extra space), the bins used, as well as the time of execution of the algorithm in each case of parallelism.