論文

査読有り
2010年

Optimization Problems and Algorithms in Double-layered Food Packing Systems

JOURNAL OF ADVANCED MECHANICAL DESIGN SYSTEMS AND MANUFACTURING
  • Yoshiyuki Karuno
  • ,
  • Hiroshi Nagamochi
  • ,
  • Xiaoming Wang

4
3
開始ページ
605
終了ページ
615
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1299/jamdsm.4.605
出版者・発行元
JAPAN SOC MECHANICAL ENGINEERS

In this paper, we discuss lexicographic bi-criteria combinatorial optimization problems arising in two types of double-layered food packing systems, which we call upright and diagonal types. Such food packing systems are known as so-called automatic combination weighers. The first and second layers in a double-layered food packing system consist of n weighing hoppers and n booster hoppers, respectively. Some amount of food such as a green pepper and a handful of potato chips is thrown into each hopper, and it is called an item. The food packing system performs an operation of choosing a subset I' from the set I of the current 2n items to produce a package of the food. Then, the resulting empty hoppers are supplied with next items, and the set I is updated. By repeating the packing operation, a large number of packages are produced one by one. The boosters are just hoppers without weighing function, but the weights of items in the boosters can be known since each type of double-layered food packing systems has its own constructional feature such that they receive next items from the weighing hoppers. The primary objective of lexicographic bi-criteria food packing problems is to minimize the the total weight of chosen items for each package, making the total weight no less than a specified target weight T. The second objective is to maximize the total priority of chosen items for each package so that items with longer durations in hoppers are preferably chosen. The priority of an item is given as its duration in hopper. In this paper, we prove that the lexicographic bi-criteria food packing problems can be solved in O(nT) time by dynamic programming if all input data are integral. We also show the executive efficiency of the pseudo-polynomial dynamic programming algorithms by conducting numerical experiments.

リンク情報
DOI
https://doi.org/10.1299/jamdsm.4.605
CiNii Articles
http://ci.nii.ac.jp/naid/130000300099
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000280848400007&DestApp=WOS_CPL
ID情報
  • DOI : 10.1299/jamdsm.4.605
  • ISSN : 1881-3054
  • CiNii Articles ID : 130000300099
  • Web of Science ID : WOS:000280848400007

エクスポート
BibTeX RIS