Heuristic algorithms with rounded weights for a combinatorial food packing problem

Abstract

In this paper, a lexicographic bi-criteria food packing problem arising in actual packaging equipments is considered. Given a set I = {i | i = 1,2,...,n} of current n items (for example, n green peppers) with their weights wi and priorities pi, the problem asks to find a subset I′ (⊆ I) so that the total weight ∑i∈I′ wi is no less than a given positive t which denotes a target weight for each package, and it is minimized as the primary objective, and further the total priority ∑i∈I′ pi is maximized as the second objective. The problem has been known to be NP-hard, while it can be solved exactly in O(nt) time if all the input data are integral. In this paper, for a given real ε > 0, an O(n2/ε) time heuristic algorithm with rounded weights is proposed such that the heuristic total weight is at most (1 + ε) times the optimal total weight. Numerical experiments are also conducted to compare the proposed and known heuristic algorithms with rounded weights, and the results are reported.

Keywords

• engineering optimization
• food packaging operation
• dynamic programming
• heuristic algorithms
• rounding