On-line bin covering algorithms

On-line Bin Covering Algorithms In food processing items of irregular sizes are frequently collected and packed into bins with portions of a specified minimal size, i.e. a target weight. The purpose of this study is to develop algorithms to assign the items, usually arriving fast on a conveyor belt, to bins, in order to minimize the overweight. Bin packing and dual bin packing, also called bin covering, are known in the literature as NP-hard problems. Our problem is on-line as the items must be processed in the order they arrive, and very fast. We discuss several different approaches, among which are knapsack optimization and heuristic methods, and present a new algorithm that has now been patented and proved itself in food processing equipment sold worldwide. Numerical results will be given.