2021-12-04T21:15:16Zhttps://nagoya.repo.nii.ac.jp/oaioai:nagoya.repo.nii.ac.jp:000125752021-03-01T18:50:24ZDynamic Programming Algorithms for Duplex Food Packing ProblemsImahori, Shinji39553Karuno, Yoshiyuki39554Yoshimoto, Yui39555In this paper, we discuss a lexicographic bi-criteria combinatorial optimization problem arising in automated food packing systems known as so-called automatic combination weighers. A typical food packing system possesses n weighing hoppers. Some amount of foods is thrown into each hopper, and it is called an item. We deal with a duplex packing operation such that the food packing system chooses two disjoint subsets I' and I" from the set I of the current n items to produce two packages of foods. After choosing two subsets I' and I", the resulting empty hoppers are supplied with next new items, and the set I is updated. By repeating the duplex packing operation, a large number of packages are produced two by two. The primary objective of lexicographic bi-criteria duplex food packing problem is to minimize the total weight of chosen items for two packages, making the total weight of each package no less than a specified target weight T. The second objective is to maximize the total priority of chosen items for two packages 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 duplex food packing problem can be solved in O(nT2) time by dynamic programming if all input data are integral.journal articleIEEE2010application/pdf8th IEEE International Conference on Industrial Informatics (INDIN)857862http://hdl.handle.net/2237/14459http://dx.doi.org/10.1109/INDIN.2010.5549629https://nagoya.repo.nii.ac.jp/record/12575/files/1004.pdfeng978-1-4244-7298-7© 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.