BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)

Abstract

In this paper, we deal with a certain type of automated food packing system with n hoppers. The system repeats throwing some amount of foods into empty hoppers to make all hoppers full of foods, and collecting the foods from several hoppers to pack them into a single package. We treat foods thrown into each hopper as an item i with an integer weight w_i. Given a set I of n items in the hoppers, the packing system chooses a subset I' (⊆ I) of items, and puts them into a package so that the total weight of items is at least a specified target weight B. The packing system then throws new items into the empty hoppers, and the set I is updated to be the union of the remaining items in I-I' and the new items. Repeating such packing operations, it produces a large number of packages one by one. In the packing system, an item may stay for a long time in some hopper until it is chosen for packing. To avoid such a situation, we introduce a priority r_i for each item i, and formulate the problem of choosing a subset I' as a bi-criteria discrete optimization problem in which one objective is to minimize Σ_<i∈I'> w_i such that Σ_<i∈I'> w_i &ge; B must be satisfied, and the other is to maximize Σ_<i∈I'> γ_i. In this paper, we propose an O(n^2w_<max>) time algorithm based on dynamic programming to obtain a nondominated solution, where w_<max> is an upper bound on the weight of an item. We also report the results on computational experiments conducted to examine the performance of the proposed approach.