A Mixed-integer Programming Model for the Bin Packing Problem with Piecewise Linear Loading Cost and Time Windows

In this paper, we address the bin packing problem while minimizing the total loading cost of used bins. We focus on two different quantity discount schemes: the all unit discount and the incremental discount. For both schemes, we take into consideration the time compatibility between items so that items sharing the same time window are assigned to the same bin while satisfying the bin capacity constraint. We propose then a mixed-integer programming (MIP) formulation. We prove that the problem is NP-hard for both discount schemes. To assess the model’s performance, we conduct numerical experiments. The results show that the proposed approach proves its effectiveness by providing optimal solutions whose computation time increases with the number of items.