The lexicographic bi-criteria combinatorial food packing problem to be discussed in this paper is described as follows. Given a set I = {i | i = 1, 2, . . . , n } of current n items (for example, n green peppers) with their weights w_(i) and priorities γ_(i) , the problem asks to find a subset I' (? I ) so that the total weight Σ_(i ∈I' ) w_(i) is no less than a specified target weight T for each package, and it is minimized as the primary objective, and further the total priority Σ_(i ∈I' ) γ_(i) 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 assumed to be integral. In this paper, we design a heuristic algorithm for the problem by applying a data rounding technique to an O (nT ) time dynamic programming procedure. We also conduct numerical experiments to examine the empirical performance such as execution time and solution quality.
展开▼
机译：本文将要讨论的词典序双准则组合食品包装问题描述如下。给定集合 I = { i | i = 1、2，... 。 。 ，当前 n个项目（例如， n个青椒）的权重 w_（i）和优先级γ_（i），则问题要求找到一个子集 I'（？ I），以便总权重Σ_（ i∈ I'） w_（i）不小于指定目标权重 T对于每个包，将其最小化作为主要目标，然后将总优先级Σ_（ i∈ I'）γ_（i）最大化作为第二个目标。已知该问题是NP难题，如果假定所有输入数据都是完整的，则可以在 O（ nT）次之内准确解决。在本文中，我们通过将数据舍入技术应用于 O（ nT）时间动态规划程序，设计了一种启发式算法。我们还进行了数值实验，以检验经验性能，例如执行时间和解决方案质量。
展开▼
