BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we deal with a certain type of automated food packing system with n hoppers. The system repeats throwing some amount of foods into empty hoppers to make all hoppers full of foods, and collecting the foods from several hoppers to pack them into a single package. We treat foods thrown into each hopper as an item i with an integer weight w_i. Given a set I of n items in the hoppers, the packing system chooses a subset I' (⊆ I) of items, and puts them into a package so that the total weight of items is at least a specified target weight B. The packing system then throws new items into the empty hoppers, and the set I is updated to be the union of the remaining items in I-I' and the new items. Repeating such packing operations, it produces a large number of packages one by one. In the packing system, an item may stay for a long time in some hopper until it is chosen for packing. To avoid such a situation, we introduce a priority r_i for each item i, and formulate the problem of choosing a subset I' as a bi-criteria discrete optimization problem in which one objective is to minimize Σ_<i∈I'> w_i such that Σ_<i∈I'> w_i ≥ B must be satisfied, and the other is to maximize Σ_<i∈I'> γ_i. In this paper, we propose an O(n^2w_<max>) time algorithm based on dynamic programming to obtain a nondominated solution, where w_<max> is an upper bound on the weight of an item. We also report the results on computational experiments conducted to examine the performance of the proposed approach.
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
-
NAGAMOCHI Hiroshi
Department of Applied Mathematics and Physics, Kyoto University
-
Nagamochi Hiroshi
Kyoto Univ. Kyoto‐shi Jpn
-
Karuno Yoshiyuki
Kyoto Institute of Technology
-
Wang Xiaoming
Kyoto Institute Of Technology
-
Nagamochi Hiroshi
Kyoto Univ.
関連論文
- 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
- Constant Time Generation of Trees with Degree Bounds
- 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 Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication
- A Simple Proof of a Minimum Cut Algorithm and Its Applications
- k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
- Augmenting Edge-Connectivity and Vertex-Connectivity Simultaneously
- Enumerating Colored and Rooted Outerplanar Graphs
- 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
- An Efficient Vector Transfer for Sparse Matrix-Vector Multiplication on Distributed Memory Systems
- 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)
- Orthogonal Drawings for Plane Graphs with Specified Face Areas
- Approximation Algorithms for Multicast Routings in a Network with Multi-Sources(Discrete Mathematics and Its Applications)
- Efficient Representation of Constraints and Propagation of Variable-Value Symmetries in Distributed Constraint Reasoning
- B34 Hardness of Approximating Transshipment Problems with Permutable Transit Vectors(Advanced machining technology)
- ANALYSIS AND OPTIMIZATION FOR AUTOMATED VEHICLE ROUTING ON A SINGLE LOOP(Advanced Planning and Scheduling for Supply Chain Management)
- Symmetry Breaking by Dominance Detection in Distributed Environments
- 2-B-5 A HEURISTIC ALGORITHM FOR OPERATING A PERMUTATIONAL CIRCULATION-TYPE VEHICLE ROUTING SYSTEM
- A SHIFTING BOTTLENECK APPROACH FOR A PARALLEL-MACHINE FLOWSHOP SCHEDULING PROBLEM
- Around the Constructive Orbit Problem in Distributed Constraint Programming
- 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)
- The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights
- FOREWORD (Special Section on Discrete Mathematics and Its Applications)
- OPTIMAL SCHEDULING FOR AN AUTOMATED m-MACHINE FLOWSHOP
- GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(Network Design, Control and Optimization)
- An Approximation of the Minimum Vertex Cover in a Graph
- Accelerating A* algorithms by sweeping out small-degree nodes
- Approximating the Minmax Rooted-Subtree Cover Problem(Graphs and Networks)
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- A Simulation-Based Analysis for Worst Case Delay of Single and Multiple Interruptions
- Multilingualization Based on RPC for Job-level Parallel Script Language, Xcrypt
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- 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)