Dynamic Programming Algorithms with Data Rounding for Combinatorial Food Packing Problems
スポンサーリンク
概要
- 論文の詳細を見る
The lexicographic bi-criteria combinatorial food packing problem to be discussed in this paper is described as follows. Given a set <I>I</I> = {<I>i</I> | <I>i</I> = 1, 2, . . . , <I>n</I>} of current <I>n</I> items (for example, <I>n</I> green peppers) with their weights <I>w<SUB>i</SUB></I> and priorities <I>γ<SUB>i</SUB></I>, the problem asks to find a subset <I>I'</I> (⊆ <I>I</I>) so that the total weight Σ<SUB><I>i</I>∈<I>I'</I></SUB> <I>w<SUB>i</SUB></I> is no less than a specified target weight <I>T</I> for each package, and it is minimized as the primary objective, and further the total priority Σ<SUB><I>i</I>∈<I>I'</I></SUB> <I>γ<SUB>i</SUB></I> is maximized as the second objective. The problem has been known to be NP-hard, while it can be solved exactly in <I>O</I>(<I>nT</I>) time if all the input data are assumed to be integral. In this paper, we design a heuristic algorithm for the problem by applying a data rounding technique to an <I>O</I>(<I>nT</I>) time dynamic programming procedure. We also conduct numerical experiments to examine the empirical performance such as execution time and solution quality.
著者
-
KARUNO Yoshiyuki
Department of Mechanical and System Engineering, Kyoto Institute of Technology
-
Takahashi Kazushi
Department Of Cardiology Teikyo University School Of Medicine
-
Karuno Yoshiyuki
Department Of Mechanical And System Engineering Faculty Of Engineering And Design Kyoto Institute Of
-
YAMADA ATSUSHI
DEPARTMENT OF ADMINISTRATION ENGINEERING CHUO UNIVERSITY
関連論文
- Optimization Problems and Algorithms in Double-layered Food Packing Systems
- DPE-063 Prognostic Value of Urinary Liver-type Fatty Acid-Binding Protein (L-FABP) in Patients with Acute Coronary Syndrome(DPE11,Kidney/Renal Circulation/CKD (H),Digital Poster Session (English),The 73rd Annual Scientific Meeting of The Japanese Circulat
- Novel IRF6 mutations in Japanese patients with Van der Woude Syndrome : two missense mutations (R45Q and P396S) and a 17-kb deletion
- Lack of evidence for a significant association between nonsyndromic cleft lip with or without cleft palate and the retinoic acid receptor alpha gene in the Japanese population
- 1A1 COMBINATORIAL OPTIMIZATION PROBLEMS AND ALGORITHMS IN DOUBLE-LAYERED FOOD PACKING EQUIPMENTS
- Potentiating and blocking actions of neonicotinoids on the response to acetylcholine of the neuronal α4β2 nicotinic acetylcholine receptor
- A low-protein diet concomitant with high calorie intake preserves renal function and structure in diabetic OLETF rats
- OE-158 Significance of Pre-test Likelihood of Coronary Artery Disease in Patients with Coronary Artery Calcium Score Zero(OE27,CT/MRI (Coronary/Vascular) 1 (I),Oral Presentation (English),The 73rd Annual Scientific Meeting of The Japanese Circulation Soci
- PE-462 Comparison of Clinical Outcomes of Percutaneous Transluminal Angioplasty to Superficial Femoral Artery with and without Stenting in Hemodialysis Patients(Peripheral circulation/Vascular disease-3, The 71st Annual Scientific Meeting of the Japanese
- Immunosuppressive Effects of Gallic Acid and Chebulagic Acid on CTL-Mediated Cytotoxicity
- Identification of Low Molecular Weight Probes on Perforin- and Fas-based Killing Mediated by Cytotoxic T Lymphocytes
- Impact of unilateral interposition sural nerve graft on the recovery of sexual function after radical prostatectomy in Japanese men : A preliminary study
- 4C1 SCHEDULING MULTIPROCESSOR TASKS WITH PROMPT SERVICE CONSTRAINTS ON ALIGNED IDENTICAL PROCESSORS
- Estimated glomerular filtration rate is an independent predictor for mortality of patients with acute heart failure
- PE-083 The Predictors of Incomplete Stent Expansion with Percutaneous Coronary Intervention in Hemodialysis Patients(Coronary revascularization, PCI-8 (IHD) PE14,Poster Session (English),The 70th Anniversary Annual Scientific Meeting of the Japanese Circu
- B34 Hardness of Approximating Transshipment Problems with Permutable Transit Vectors(Advanced machining technology)
- 3C3 A TRANSSHIPMENT PROBLEM WITH A PREMUTABLE TRANSIT VECTOR
- Influence of Mechanical Loading on Resonance Frequency Analysis and Trabecular Structure of Peri-implant Bone
- 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)
- Pramipexole Reduces the Prevalence of Fatigue in Patients with Parkinsons Disease
- VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
- Acupuncture modulates mechanical responses of smooth muscle produced by transmural nerve stimulation in gastric antrum of genetically hyperglycemic rats
- 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
- Gene Targeting Mice for Genome Research : An in vivo Study of Mouse Gene Functions
- Dynamic Programming Algorithms with Data Rounding for Combinatorial Food Packing Problems
- Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems
- Expression of myelin and lymphocyte protein (MAL) in oral carcinogenesis
- 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)
- New building blocks for heterocyclic syntheses. Silylated methyl isothiocyanates.
- Scheduling Capacitated One-Way Vehicles on Paths with Deadlines
- MATHEMATICAL FOUNDATION OF GENERAL COOPERATIVE FUZZY GAMES
- Disaster Medicine Education and Training for Medical Student at Juntendo University