The standard bin packing problem is about distributing a set of items with positive sizes over bins of certain capacity in such a way that the number of bins used is minimized. In this thesis a relatively undocumented version of bin packing with negative items is discussed. Negative items added to the standard problem can reduce the load in a bin. In context, this means energy is regenerated or recharged. This forces us to take a look at the problem in a different way. The goal of this thesis is to find methods that give solutions with a guaranteed desired quality. For the standard problem, we already have well-working heuristic algorithms such as the First Fit (FF), Best Fit (BF), and their decreasing-order variants (FFD and BFD). These algorithms have nice bounded approximation ratios. However, introducing negative items sabotages these nice approximation ratios. We know negative items can reduce the total number of bins, so naively applying classical algorithms does not perform well, as these methods do not take the potential of negative items to offset large positives and reduce bin usage into account. To try and solve these problems, we introduce the adjusted heuristic algorithms Negative First Fit (NFF), Negative Best Fit (NBF), and their decreasing-order variants, which work by placing all negative items into the first bin before applying the standard algorithm. By placing all negative items in the first bin, we can get a packing that uses 1 bin or more. If the packing uses only 1 bin, the problem is trivial. If it uses more than 1 bin, we know that all negative items in the first bin have been canceled out, so we can retain the logic of the standard problem and thus the approximation ratio. Although the negative adjusted algorithm has a nice approximation ratio, putting all negative items in the first bin does not make sense in a real-life context. That is why we also explore the heuristic method of dividing negative items over large positive ones before applying standard packing algorithms. Here we focus on the notion that fewer big items, where we define big items as items larger than half the capacity, lead to a smaller number of bins for the solution because all big items need to be in a separate bin. First we have Decreasing Division (DD), which pairs the largest big item with the smallest negative items. Unfortunately, this does not guarantees a reduction of big items. To try and improve on this, we also introduce Increasing Division (ID). ID pairs the smallest big item to the smallest negative item. This way, ID can give a bigger guarantee to reduce the number of big items. DD and ID both have the same approximation ratio and both give more logical packing results. However, we proved that for DD there is no better approximation ratio. For ID however, we saw that a better approximation ratio may still be found. This thesis is mostly based on literature research, mathematical analysis and explanatory examples. We show the potential performance and limitations of different heuristic algorithms for bin packing
with negative items. The results achieved give a different perspective on the bin packing problem and leave open future research in optimizing bin packing with negative items. But most importantly, the goal of finding methods that work on the bin packing problem with negative items was achieved.