View article

Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into a minimum number of bins such that the sum of item sizes in a bin does not exceed the capacity. We define a new variant called -times bin packing (BP), where the goal is to pack the items such that each item appears exactly times, in different bins. We generalize some existing approximation algorithms for bin-packing to solve BP, and analyze their performance ratio. The study of BP is motivated by the problem of fair electricity distribution. In many developing countries, the total electricity demand is higher than the supply capacity. We show that -times bin packing can be used to distribute the electricity in a fair and efficient way. Particularly, we implement generalizations of the First-Fit and First-Fit-Decreasing bin-packing algorithms to solve BP, and apply the generalizations to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem.