Kansei engineering, humans and computers: efficient dynamic programming algorithms for combinatorial food packing problems

被引：20

作者：

Imahori, Shinji ^{[1
]}

Karuno, Yoshiyuki ^{[2
]}

Nagamochi, Hiroshi ^{[3
]}

Wang, Xiaoming ^{[4
]}

机构：

[1] Nagoya Univ, Dept Computat Sci & Engn, Chikusa Ku, Nagoya, Aichi 4648603, Japan

[2] Kyoto Inst Technol, Dept Mech & Syst Engn, Sakyo Ku, Kyoto, Kyoto 6068585, Japan

[3] Kyoto Univ, Dept Appl Math & Phys, Sakyo Ku, Kyoto, Kyoto 6068501, Japan

[4] Kyoto Inst Technol, Dept Mech & Syst Engn, Sakyo Ku, Kyoto, Kyoto 6068585, Japan

来源：

INTERNATIONAL JOURNAL OF BIOMETRICS | 2011年 / 3卷 / 03期

基金：

日本学术振兴会;

关键词：

automatic combination weighers; food packing problems; target weight constraints; combinatorial optimisation; lexicographic bi-criteria optimisation; computer algorithms; dynamic programming; pseudo-polynomial time algorithms; optimal solutions; minimal solutions;

D O I：

10.1504/IJBM.2011.040817

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The packing system performs an operation of choosing a subset I ' from the set of I of the current n items to produce a package of foods. By repeating the packing operation, it produces a large number of packages one by one. The primary objective is to choose a subset I so that the total weight of chosen items is as close to a specified target weight T as possible. We additionally try to maximise the total priority of chosen items as the second objective so that items with longer durations in hoppers are preferably chosen. We show that the combinatorial food packing problem can be solved in O(nT) time if all input data are integral.

引用

页码：228 / 245

页数：18

共 11 条

[1]

Garey M. R, 1979, COMPUTERS INTRACTABI, P223

[2]

Ibaraki T., 1999, ALGORITHMS DATA STRU, P89

[3]

ISHIDA CO. LTD, 2009, PROD TOT SYST WEIGH

[4]

Kameoka K., 2001, Transactions of the Society of Instrument and Control Engineers, V37, P911

[5]

Kameoka K., 2000, Transactions of the Society of Instrument and Control Engineers, V36, P388

[6] Bi-criteria food packing by dynamic programming [J].

Karuno, Yoshiyuki ;

Nagamochi, Hiroshi ;

Wang, Xiaoming .

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 2007, 50 (04) :376-389

[7]

Morinaka H., 2000, J JAPAN SOC MECH ENG, V103, P130

[8]

Murakami Y., 2002, Transactions of the Society of Instrument and Control Engineers, V38, P784

[9]

Murakami Y., 2003, T JAPAN SOC MECH E C, V69, P3431

[10]

Murakami Y., 2008, T JAPAN SOC MECH E C, V74, P1920

← 1 2 →