Modeling and Solving the Open-End Bin Packing Problem

In the Open-End Bin Packing Problem a set of items with varying weights must be packed into bins of uniform weight limit such that the capacity of the bin can be exceeded only by the last packed item, known as the overflow item. The objective is to minimize the number of used bins. In this paper, we present our Integer Linear Program model based on a modification of Cesili and Righini model [1]. Also, we propose two greedy heuristics to solve a problem. The first one is an adaptation of the Minimum Bin Slack heuristic where we have reduced to one unit capacity, the weight of the largest item in the current bin. While, the second heuristic is based on the well-known First Fit Decreasing heuristic. Computational results based on benchmark instances taken from the literature as well as generated instances show the effectiveness of the proposed heuristics in both solution quality and time requirement.

@article{Mohamed2016,
  title     = {Modeling and Solving the Open-End Bin Packing Problem},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {7},
  number    = {12},
  year      = {2016},
  publisher = {The Science and Information Organization},
  author    = {Maiza Mohamed and Tebbal Mohamed and Rabia Billal},
  doi       = {10.14569/IJACSA.2016.071252},
  url       = {https://doi.org/10.14569/IJACSA.2016.071252}
}