Bin Packing Problem: a parallel implementation

Abstract

The thesis is concerned with the parallelization of algorithms and specifically with the bin packing problem in parallel implementation. Due to the complexity and the existence of numerous variables and parameters, this problem refers to NP-hard problem, which makes the convergence to optimal solution hard to be achieved. Initially, the benefits, as well as, the advantages that can be gained by the parallel computing are described. Then, concepts such as data partition, speedup, efficiency, Flynn’s taxonomy and Amdahl’s law are analysed. The dissertation here is related to the “bin packing", a well-studied problem in theoretical computer science. Briefly, we describe the Bin Packing problem and the goal we want to achieve. Then, we will consider that as the number of data increased, we observe that the running time increases exponentially. In order to reduce the execution time for large datasets we perform data partition, which is a technique of parallelization of algorithms. So, we describe and compare the serial and parallel implementation and how they work. In particular, we focused on MATLAB and specifically on toolbox Distributed Computing Toolbox™, which has functions for the creation and implementation of distributed and parallel operations. More specifically, we answer the following question: will the serial execution of algorithm or the parallelization of algorithm be beneficial to us?