A Modification of Hungarian Method to solve One Dimensional Bin Packing Problems

Abstract

In bin packing problems, items of various sizes must be packed into a limited number of bins or containers, each with a fixed capacity. There are several kinds of BPP such as one-dimensional (1D), Two-dimensional (2D), three-dimensional (3D). While First Fit and Best Fit method is faster and simpler it does not ensure that optimal solution and can result in smaller spaces in the bins that could have been occupied by larger objects. This research introduces a new method for solving the 1D BPP inspired by the row reduction method from Hungarian method. To minimize the bin usage, carefully analyzes item placement by applying the concept of row reduction. Existing methods often produce suboptimal solutions, resulting in wasted space within bins. This method aims to achieve optimal packing, minimizing waste. First, arrange items in ascending order of size as Row 1 and descending order of size as Row 2. Subtract the smallest value in Row 2 from all values, recording results in Row 3. Identify items in Row 1 corresponding to zeroes in Row 3 and allocate them to the first bin. Select the smallest non-zero value in Row 3, subtract it from all values, and update as Row 4. Repeat the allocation process for remaining zeroes in Row 4, ensuring bin capacity is not exceeded. This new approach to 1D BPP has been thoroughly tested using examples taken from research papers Continue above steps until all items are assigned to bins. This suggested method presents a new approach to the 1D BPP that consistently produces optimal solutions that perform better than existing methods such as the First Fit and Best Fit approaches. This study provides a foundation for researching more developments for bin packing problems such as 2D and 3D.