On optimal packing of randomly arriving objects

Objects of finitely many types arrive at a facility according to independent stationary Poisson processes. The objects are to be placed in boxes as they arrive. There are finitely many types of boxes and each box type has its own packing configuration. There is an unlimited supply of boxes of each type and once an object is placed in a box it cannot be moved to another box in the future. When a box is completely filled it produces a reward which depends on its configuration. The objective is to select a rule for placing the arriving objects in boxes so as to maximize expected reward. The authors show how to construct optimal and ∈-optimal policies under which the expected number of partially packed boxes does not explode.