An improved performance of greedy heuristic solutions for a bi-criteria mixture packaging problem of two types of items with bounded weights

Abstract

In this paper, we treat a lexicographic bi-criteria combinatorial optimization model of mixture packaging of two types of items, which arises in actual food packing systems, so-called multi-head weighers. The primary objective is to minimize the total weight of chosen items for a package, and the second objective is to maximize the total priority of them. The constraints are that the total weight must be no less than a given target weight, and that the weight sum of chosen items of each type must also be no less than a given necessity minimum. The weight of an item of each type is bounded by the necessity minimum from the above. We show that a greedy heuristic solution with the total weight at most twice the minimum attains the total priority at least the conditionally maximum, which is an improved performance guarantee of greedy heuristic solutions for the lexicographic bi-criteria mixture packaging problem of two types of items.

Keywords

• combinatorial optimization
• mixture packaging
• subset sum
• greedy heuristic algorithms
• performance guarantee