\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Pseudo-polynomial time algorithms for combinatorial food mixture packing problems

Abstract Related Papers Cited by
  • A union $\mathcal{I}=\mathcal{I}_{1}\cup \mathcal{I}_{2}\cup \cdots \cup \mathcal{I}_{m}$ of $m$ sets of items is given, where for each $i=1,2,\ldots,m$, $\mathcal{I}_{i}=\{I_{ik} \mid k=1,2,\ldots,n\}$ 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 $p_{ik}$. The food mixture packing problem to be discussed in this paper asks to find a union $\mathcal{I}'=\mathcal{I}'_{1}\cup \mathcal{I}'_{2}\cup \cdots \cup \mathcal{I}'_{m}$ of $m$ subsets of items so that for each $i=1,2,\ldots,m$, the sum weight of chosen items of the $i$-th type for $\mathcal{I}'_{i} \subseteq \mathcal{I}_{i}$ is no less than an integral indispensable bound $b_{i}$, and the total weight of chosen items for $\mathcal{I}'$ is no less than an integral target weight $t$. The total weight of chosen items for $\mathcal{I'}$ is minimized as the primary objective, and further the total priority of chosen items for $\mathcal{I'}$ is maximized as the second objective. In this paper, the known time complexity $O(mnt+mt^{m})$ is improved to $O(mnt+mt^{2})$ for an arbitrary $m\geq 3$ by a two-stage constitution algorithm with dynamic programming procedures. The improved time complexity figures out the weak NP-hardness of the food mixture packing problem.
    Mathematics Subject Classification: Primary: 90C27, 90C39; Secondary: 68Q25.

    Citation:

    \begin{equation} \\ \end{equation}
  • [1]

    M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979.

    [2]

    S. Imahori and Y. Karuno, Pseudo-polynomial time algorithms for food mixture packing by automatic combination weighers, in Proceedings of International Symposium on Scheduling 2013 (ISS 2013), 2013, 59-64.

    [3]

    S. Imahori, Y. Karuno, H. Nagamochi and X. Wang, Kansei engineering, humans and computers: Efficient dynamic programming algorithms for combinatorial food packing problems, International Journal of Biometrics, 3 (2011), 228-245.doi: 10.1504/IJBM.2011.040817.

    [4]

    S. Imahori, Y. Karuno, R. Nishizaki and Y. Yoshimoto, Duplex and quasi-duplex operations in automated food packing systems, in IEEE Xplore of the Fifth IEEE/SICE International Symposium on System Integration (SII 2012), 2012, 810-815.doi: 10.1109/SII.2012.6427267.

    [5]

    S. Imahori, Y. Karuno and K. Tateishi, Dynamic programming algorithms for producing food mixture packages by automatic combination weighers, Journal of Advanced Mechanical Design, Systems, and Manufacturing, 8 (2014), 1-11.doi: 10.1299/jamdsm.2014jamdsm0065.

    [6]

    Ishida Co., Ltd.Products (Total System Solutions), Weighing and Packaging, 2015. Available from: http://www.ishida.com/products/.

    [7]

    K. Kameoka and M. Nakatani, Feed control criterion for a combination weigher and its effects (in Japanese), Transactions of the Society of Instrument and Control Engineers, 37 (2001), 911-915.

    [8]

    K. Kameoka, M. Nakatani and N. Inui, Phenomena in probability and statistics found in a combinatorial weigher (in Japanese), Transactions of the Society of Instrument and Control Engineers, 36 (2000), 388-394.

    [9]

    Y. Karuno, H. Nagamochi and X. Wang, Bi-criteria food packing by dynamic programming, Journal of the Operations Research Society of Japan, 50 (2007), 376-389.

    [10]

    Y. Karuno, H. Nagamochi and X. Wang, Optimization problems and algorithms in double-layered food packing systems, Journal of Advanced Mechanical Design, Systems, and Manufacturing, 4 (2010), 605-615.doi: 10.1299/jamdsm.4.605.

    [11]

    Y. Karuno, K. Takahashi and A. Yamada, Dynamic programming algorithms with data rounding for combinatorial food packing problems, Journal of Advanced Mechanical Design, Systems, and Manufacturing, 7 (2013), 233-243.doi: 10.1299/jamdsm.7.233.

    [12]

    H. Morinaka, Automatic combination weigher for product foods (in Japanese), Journal of the Japan Society of Mechanical Engineers, 103 (2000), 130-131.

    [13]

    H. A. Wurdemann, V. Aminzadeh, J. S. Dai, J. Reed and G. Purnell, Category-based food ordering processes, Trends in Food Science & Technology, 22 (2011), 14-20.doi: 10.1016/j.tifs.2010.10.003.

    [14]

    Yamato Scale Co., Ltd.Category Search, Filling and Packaging, 2015. Available from: http://www.yamato-scale.co.jp/en/products/index.

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(182) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return