2007年12月
Bi-criteria food packing by dynamic programming
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN
- ,
- ,
- 巻
- 50
- 号
- 4
- 開始ページ
- 376
- 終了ページ
- 389
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.15807/jorsj.50.376
- 出版者・発行元
- ELSEVIER SCI LTD
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' (subset of 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 -gamma(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 Sigma(i is an element of I') w(i) such that Sigma(i is an element of I') w(i) >= B must be satisfied, and the other is to maximize Sigma(i is an element of I') gamma(i). In this paper, we propose an O(n(2)w(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.
- リンク情報
- ID情報
-
- DOI : 10.15807/jorsj.50.376
- ISSN : 0453-4514
- CiNii Articles ID : 110006532059
- Web of Science ID : WOS:000253322900008