論文

査読有り
2007年12月

Bi-criteria food packing by dynamic programming

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN
  • Yoshiyuki Karuno
  • ,
  • Hiroshi Nagamochi
  • ,
  • Xiaoming Wang

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.

リンク情報
DOI
https://doi.org/10.15807/jorsj.50.376
CiNii Articles
http://ci.nii.ac.jp/naid/110006532059
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000253322900008&DestApp=WOS_CPL
ID情報
  • DOI : 10.15807/jorsj.50.376
  • ISSN : 0453-4514
  • CiNii Articles ID : 110006532059
  • Web of Science ID : WOS:000253322900008

エクスポート
BibTeX RIS