Kansei engineering, humans and computers: efficient dynamic programming algorithms for combinatorial food packing problems. (27th June 2011)

• Record Type: Journal Article
• Authors: Imahori, Shinji; Karuno, Yoshiyuki; Nagamochi, Hiroshi; Wang, Xiaoming
• Is Part Of: International journal of biometrics. Volume 3:Number 3(2011)
• Page Start: 228
• Page End: 245
• Publication Date: 2011-06-27
• Subjects: automatic combination weighers -- food packing problems -- target weight constraints -- combinatorial optimisation -- lexicographic bi-criteria optimisation -- computer algorithms -- dynamic programming -- pseudopolynomial time algorithms -- optimal solutions -- minimal solutions; Biometric identification -- Periodicals; Biometry -- Periodicals; 570.15195
• Languages: English
• ISSNs: 1755-8301

Abstract

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.