In the Probabilistic Bin Packing Problem (PBPP), some items are randomly deleted after having been placed into bins. The problem is to rearrange the remaining items, using the a priori solution. The initial arrangement being done with the Next Fit Decreasing heuristic, we consider two procedures. In the first one, the NF algorithm is applied to the new list. In the second one, successive groups of bins are optimally rearranged. In both cases, we prove a law of large numbers and a central limit theorem for the number of occupied bins as the initial number of items tends to infinity.