CHaMP: Creating Heuristics via Many Parameters

The online bin packing problem is a well-known bin packing variant which requires immediate decisions to be made for the placement of a sequence of arriving items of various sizes one at a time into fixed capacity bins without any overflow. The overall goal is maximising the average bin fullness. We investigate a ‘policy matrix ’ representation which assigns a score for each decision option independently and the option with the highest value is cho-sen for one dimensional online bin packing. A policy matrix might also be considered as a heuristic with many parameters, where each parameter value is a score. We hence investigate a framework which can be used for creating heuristics via many parameters. The proposed framework combines a Ge-netic Algorithm optimiser, which searches the space of heuristics in policy matrix form, and an online bin packing simulator, which acts as the eval-uation function. The empirical results indicate the success of the proposed approach, providing the best solutions for all item sequence generators used during the experiments