Optimization Problems and Algorithms in Double-layered Food Packing Systems
スポンサーリンク
概要
- 論文の詳細を見る
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.
著者
-
KARUNO Yoshiyuki
Department of Mechanical and System Engineering, Kyoto Institute of Technology
-
NAGAMOCHI Hiroshi
Department of Applied Mathematics and Physics, Kyoto University
-
WANG Xiaoming
Department of Mechanical and System Engineering, Kyoto Institute of Technology
関連論文
- Optimization Problems and Algorithms in Double-layered Food Packing Systems
- CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK
- 1A1 COMBINATORIAL OPTIMIZATION PROBLEMS AND ALGORITHMS IN DOUBLE-LAYERED FOOD PACKING EQUIPMENTS
- 6B2 AN ITERATED LOCAL SEARCH ALGORITHM FOR THE MULTI-RESOURCE GENERALIZED ASSIGNMENT PROBLEM WITH FLEXIBLE ASSIGNMENT COST(Technical session 6B: General model for scheduling and assignment problem)
- Constructing a Cactus for Minimum Cuts of a Graph in ★(mn+n^2logn) Time and ★(m) Space (Special Issue on Selected Papers from LA Symposium)
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex(Graph Algorithms,Foundations of Computer Science)
- A Simple Proof of a Minimum Cut Algorithm and Its Applications
- Approximating a Generalization of Metric TSP(Graph Algorithms,Foundations of Computer Science)
- Approximation to the Minimum Cost Edge Installation Problem
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(the 50th Anniversary of the Operations Research Society of Japan)
- Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning
- 4C1 SCHEDULING MULTIPROCESSOR TASKS WITH PROMPT SERVICE CONSTRAINTS ON ALIGNED IDENTICAL PROCESSORS
- Worst Case Analysis for Pickup and Delivery Problems with Transfer
- Orthogonal Drawings for Plane Graphs with Specified Face Areas(Theory of Computer Science and Its Applications)
- 1A2 AN IMPROVED APPROXIMATION ALGORITHM FOR CAPACITATED MULTICAST ROUTINGS IN NETWORKS(Technical session 1A: Combinatorial optimization)
- 5B2 AN ITERATED LOCAL SEARCH ALGORITHM BASED ON NONLINEAR PROGRAMMING FOR THE IRREGULAR STRIP PACKING PROBLEM(Technical session 5B: Packing problem)
- 2B1 A DP-BASED HEURISTIC ALGORITHM FOR THE DISCRETE SPLIT DELIVERY VEHICLE ROUTING PROBLEM(Technical session 2B: Vehicle scheduling and communication)
- A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs(Discrete Mathematics and Its Applications)
- A Note on Approximating the Survivable Network Design Problem in Hypergraphs(Special Issue on Selected Papers from LA Symposium)
- Approximation Algorithms for Multicast Routings in a Network with Multi-Sources(Discrete Mathematics and Its Applications)
- B34 Hardness of Approximating Transshipment Problems with Permutable Transit Vectors(Advanced machining technology)
- 3C3 A TRANSSHIPMENT PROBLEM WITH A PREMUTABLE TRANSIT VECTOR
- 2-B-5 A HEURISTIC ALGORITHM FOR OPERATING A PERMUTATIONAL CIRCULATION-TYPE VEHICLE ROUTING SYSTEM
- 1B2 AN APPLICATION OF THE GENETIC ALGORITHM TO A TWO-MACHINE ROBOTIC FLOW-SHOP SCHEDULING PROBLEM(Technical session 1B : Meta Heuristics)
- A Fast Algorithm for Cactus Representations of Minimum Cuts
- Solving the Single-Vehicle Scheduling Problems for All Home Locations under Depth-First Routing on a Tree (Special Section on Discrete Mathematics and Its Applications)
- An Approximation of the Minimum Vertex Cover in a Graph
- A Dynamic Programming Based Improvement Heuristic for a Repetitive Routing Problem of Grasp-and-Delivery Robots
- Dynamic Programming Algorithms with Data Rounding for Combinatorial Food Packing Problems
- 5B1 IMPROVED IMPLEMENTATION OF AN APPROXIMATION ALGORITHM WITH FACTOR TWO FOR A CYCLIC ROUTING PROBLEM OF GRASP-AND-DELIVERY ROBOTS(Technical session 5B: Routing problems)