1A1 COMBINATORIAL OPTIMIZATION PROBLEMS AND ALGORITHMS IN DOUBLE-LAYERED FOOD PACKING EQUIPMENTS
スポンサーリンク
概要
- 論文の詳細を見る
We consider efficient algorithms for combinatorial optimization problems arising in automatic double-layered food packing equipments. The first and second layers consist of n weighing hoppers and n booster hoppers, respectively. Some amount of foods is thrown into each hopper, and is called an item. The equipment performs an operation of choosing a subset I' from the set I of the current 2n items to produce a package of foods. Then, the resulting empty hoppers are supplied with the next items, and the set I is updated. By repeating the packing operation, a large number of packages are produced 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. In order to avoid the occurrence of an item such that it is left in hopper for a long time before it is chosen, a priority is additionally introduced into each item, and the equipment tries to maximize the total priority of chosen items as the second objective. The boosters are just hoppers without weighing function, but the weights of items in the boosters can be known since the equipment has a structural feature such that they receive the next items from the weighing hoppers. Regarding the structural feature, we formulate the combinatorial food packing problems, and then prove that the problems can be solved in O (nT) time by dynamic programming approaches if all input data are assumed to be integral. We also show the executive efficiency of the pseudo-polynomial time algorithms by conducting numerical experiments.
- 2009-07-04
著者
-
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
-
Karuno Yoshiyuki
Kyoto Institute of Technology
-
Wang Xiaoming
Kyoto Institute Of Technology
-
Wang Xiaoming
Department Of Mechanical And System Engineering Kyoto Institute Of Technology:(present Office)feg Co
-
Karuno Yoshiyuki
Department Of Mechanical And System Engineering Faculty Of Engineering And Design Kyoto Institute Of
-
Nagamochi Hiroshi
Department Of Applied Mathematics And Physics Graduate School Of Engineering Kyoto University
関連論文
- Optimization Problems and Algorithms in Double-layered Food Packing Systems
- AN INAPPROXIMABILITY OF TRANSSHIPMENT PROBLEMS WITH PERMUTABLE TRANSIT VECTORS
- CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK
- Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs
- Generation of Symmetric and Asymmetric Biconnected Rooted Triangulated Planar Graphs
- 1A1 COMBINATORIAL OPTIMIZATION PROBLEMS AND ALGORITHMS IN DOUBLE-LAYERED FOOD PACKING EQUIPMENTS
- 3B4 ON OPTIMAL SCHEDULING PROBLEMS FOR PARALLLEL MACHINES WITH A SINGLE SERVER(Technical session 3B : Combinatorics 2)
- 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
- ANALYSIS AND OPTIMIZATION FOR AUTOMATED VEHICLE ROUTING ON A SINGLE LOOP(Advanced Planning and Scheduling for Supply Chain Management)
- 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 SHIFTING BOTTLENECK APPROACH FOR A PARALLEL-MACHINE FLOWSHOP SCHEDULING PROBLEM
- 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)
- VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
- OPTIMAL SCHEDULING FOR AN AUTOMATED m-MACHINE FLOWSHOP
- Approximability of the Minimum Maximal Matching Problem in Planar Graphs(Graphs and Networks)
- An Approximation of the Minimum Vertex Cover in a Graph
- Approximating the Minmax Rooted-Subtree Cover Problem(Graphs and Networks)
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- A Dynamic Programming Based Improvement Heuristic for a Repetitive Routing Problem of Grasp-and-Delivery Robots
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- Dynamic Programming Algorithms with Data Rounding for Combinatorial Food Packing Problems
- Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- 4A2 NETWORK TRANSFORMATION HEURISTICS FOR MULTI-STORY STORAGE RACK PROBLEMS(Technical session 4A: Material handling system)
- 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)
- 5B3 APPROXIMATING CYCLIC ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS(Technical session 5B: Routing problems)
- Scheduling Capacitated One-Way Vehicles on Paths with Deadlines
- A DP-based Heuristic Algorithm for the Discrete Split Delivery Vehicle Routing Problem