Dynamic programming algorithms for producing food mixture packages by automatic combination weighers
Dynamic programming algorithms for producing food mixture packages by automatic combination weighers
复制标题
通过自动组合秤生产食品混合物包装的动态规划算法
DOI：
10.1299/jamdsm.2014jamdsm0065
复制
发表时间：
2014
影响因子：
0.9
通讯作者：
Kenju Tateishi
中科院分区：
文献类型：
--
作者：
S. Imahori;Y. Karuno;Kenju Tateishi
本文讨论的字典序双准则组合优化问题是由所谓的自动组合秤执行的食品混合物包装的数学模型，并且描述如下。给出m个项目集合的并集I = I 1 [ I 2 [（cid：1）（cid：1）[ I m，其中对于每个i = 1 ; 2 ;：：; m，I i = f I ik j k = 1 ; 2 ;：：; n g表示第i类型的n个项目的集合，并且I ik表示第i类型的第k个项目.每个项目Iik具有积分权重wik和积分优先级（cid：13）ik。该问题要求找到m个项目子集的并集I ′ = I ′ 1 [ I ′ 2 [（cid：1）（cid：1）[ I ′ m，其中I ′ i（cid：18）I i，使得I ′的所选项目的总权重不小于整数目标权重T，并且I ′ i的第i类型的所选项目的总权重不小于整数必不可少权重B i。首先以I ′的总权重最小化为主要目标，其次以I ′的总优先级最大化为次要目标。对于存在两种类型的项目的情况（即，m = 2），我们提出了一个O（nT）时间的动态规划算法，应用线性搜索技术.我们还进行了数值实验，以证明经验的性能。
The lexicographic bi-criteria combinatorial optimization problem to be discussed in this paper is a mathematical model of the food mixture packing performed by so-called automatic combination weighers, and it is described as follows. We are given a union I = I 1 [ I 2 [ (cid:1) (cid:1) (cid:1) [ I m of m sets of items, where for each i = 1 ; 2 ; : : : ; m , I i = f I ik j k = 1 ; 2 ; : : : ; n g denotes a set of n items of the i -th type and I ik denotes the k -th item of the i -th type. Each item I ik has an integral weight w ik and an integral priority (cid:13) ik . The problem asks to find a union I ′ = I ′ 1 [ I ′ 2 [ (cid:1) (cid:1) (cid:1) [ I ′ m of m subsets of items where I ′ i (cid:18) I i so that the total weight of chosen items for I ′ is no less than an integral target weight T , and the sum weight of chosen items of the i -th type for I ′ i is no less than an integral indispensable weight b i . The total weight of chosen items for I ′ is minimized as the primary objective, and further the total priority of chosen items for I ′ is maximized as the second objective. For the case in which there are two types of items (i.e., m = 2), we propose an O ( nT ) time dynamic programming algorithm, applying a linear search technique. We also conduct numerical experiments to demonstrate the empirical performance.