平衡組合せ最適化問題に対する新解法の提案とその生産スケジューリングへの適用

平衡组合优化问题新求解方法的提出及其在生产调度中的应用

• 批准号: 11780333
• 负责人: 根本 俊男
• 金额: $ 1.22万
• 依托单位: Bunkyo University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1999
• 资助国家: 日本
• 起止时间: 1999 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-11780333/
• 关键词: 組合せ最適化問題; 安定結婚問題; メジアン安定マッチング; ローテーション半順序集合; アルゴリズム; 平衡組合せ最適化問題; 組合せ最適化; 半順序集合; イデアル; 平衡

研究費補助期間2年目の今年度も研究計画どおり組合せ最適化問題において基本的な制約の一つである半順序制約下での最適化問題に対する効率の良い解法の開発に取り組んできた.一般的な枠組みでの研究の一方で,半順序制約を持つ最適化問題に帰納でき,経済学や計算科学の分野で活発に研究されている安定結婚問題への研究成果の集中が特徴である.研究概要実績の詳細は以下のとおりである.1.安定結婚問題において,公平性を重視した平衡安定解を求める解法に関する研究に取り組んだ.その中で,メジアン安定マッチングと名付けられる,従来とは異なる公平性基準を持つ解の性質の導出に成功した.その成果は,国際数理計画学会(ISMP2000,2000年8月,アトランタ)にて公表され,論文は準備中である.2.安定結婚問題の解集合を効率よく見出す別解法を提案した.その成果は応用数理学会(2000年10月,東京工業大学)などで発表された.また,安定結婚問題の最新の研究動向などに関しサーベイも行った.これらの内容は「応用数理計画ハンドブック(仮)」(共同執筆,朝倉書店)の一部まとめられ近日発行予定である.3.組合せ最適化問題に関する基本的な性質に関する情報提供の作業を「OR用語辞典」(2000年4月,日科技連),「OR辞典2000」(2000年5月,日本OR学会編)の共同執筆を通して行った.また,学術雑誌「応用数理」(2000年12月,岩波書店)においては組合せ最適化に関する書籍の書評を行った.4.本研究の生産スケジューリングへの適用は現在も検討中である.

Research grant period 2 years This year's research plan is to combine optimization problems with basic constraints and semi-sequential constraints to develop efficient solutions. On the one hand, research on general groups is focused on semi-sequential constraints and optimization problems, and on the other hand, the division between economics and computing science is active in research on marriage stability issues. The concentration of research results is characterized by this. Summary of the research results are detailed below. 1. Stability of marriage problems, fairness, balance, stability, solutions, related research, group. In addition, the fairness benchmark is successfully derived from the nature of the solution. The results of this paper are published in the International Society for Mathematical Planning (ISMP2000, August 2000). The paper is under preparation. 2. The solution set of stable marriage problem is proposed. Institute of Applied Mathematics (Tokyo Institute of Technology, October 2000) The latest research trends in stable marriage. The contents of this paper include: "Application of Mathematical Planning"(co-authored by Asakura Bookstore), a part of "Application of Mathematical Planning"(co-authored by Asakura Bookstore). 3. Basic properties related to combinatorial optimization problems, information provision,"OR Dictionary"(April 2000, Japan Science and Technology Corporation), and "OR Dictionary 2000"(May 2000, edited by Japan OR Society). The academic journal "Applied Mathematics"(December, 2000, Iwawa Bookstore) provides a review of books related to combinatorial optimization. 4. The production of this study is currently under discussion.

项目成果

日本OR学会 編: "OR事典2000"日本OR学会. 6272 (2000)

日本OR学会编：《OR百科全书2000》日本OR学会6272（2000）。

日本OR学会 編: "OR用語辞典"日科技連出版社. 257 (2000)

日本OR研究学会编：《OR术语词典》日本科学技术学会出版257（2000）。

Toshio Nemoto: "An efficient algorithm for the minimum-range ideal problem"Journal of the Operations Research Society of Japan. 42. 88-97 (1999)

Toshio Nemoto：“最小范围理想问题的有效算法”日本运筹学会杂志。