Arc Flow Models for the Min-Sum Bin Packing Problem

In this work, we study the Min-Sum Bin Packing Problem (MSBPP), in which items must be packed into bins without exceeding the size capacity of the bins, the cost of packing an item is equal to the index of the bin it is placed into, and we seek to minimize the total cost of packing the items. The problem models logistic issues with the goal of minimizing the average time of processing the items within the bins in order, and is a special case of a parallel batch-scheduling problem with a single machine. We propose two arcflow formulations for the MSBPP and compare their efficiency with respect to the time needed to solve bin packing instances in the literature. Our best proposed model is shown to solve in efficient time instances with up to 500 items and capacity up to 150.