摂動レベルと後悔の度合いを考慮した組合せ最適化問題に対するロバスト最適化

考虑扰动水平和后悔程度的组合优化问题的鲁棒优化

• 批准号: 21K14367
• 负责人: 呉 偉
• 金额: $ 2.41万
• 依托单位: Shizuoka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K14367/
• 关键词: ロバスト最適化; 組合せ最適化; 反復双対置換法; 最大後悔最小化; 発見的解法; 後悔の度合い最小化; 摂動レベル

前年度は，0-1組合せ問題のロバスト最適化に対する汎用解法（iDS法）を提案し，代表的な問題に対して大規模実験を行いました．今年度は，ロバスト巡回セールスマン問題へのiDS法の適用を検討しました．巡回セールスマン問題は，重要な実用例が多い問題ですが，多項式サイズの0-1整数計画モデルの構築が困難な問題として知られているため，今まで提案したiDS法の適用ができません．iDS法を改良・拡張し，ロバスト巡回セールスマン問題に適用しました．また，ロバスト巡回セールスマン問題に対する新しい発見的手法として，コア選択法を提案し，優れた性能を示しました．さらに，単一機械スケジューリング問題の一般化であるバッチスケジューリング問題を対象として処理時間が不確定な場合のロバスト最適化問題に対して多項式時間厳密解法を提案しました．具体的には遅延ジョブの発生数の上限がΓのとき，最大滞留時間最小化バッチスケジューリング問題に対して，並列バッチの状況および直列バッチの状況をそれぞれ考慮し，どちらの場合でも多項式時間で解けることを示しました．

In the past year, the generic solution (iDS) for optimization of 0-1 combination problems was proposed for large-scale implementation. This year, the application of the iDS method is discussed. IDS method is an improvement of the IDS method, and it is suitable for the IDS problem. A new approach to the problem was proposed. In this paper, the generalization of mechanical optimization problem, the solution of polynomial optimization problem. The upper limit of the number of occurrences of the reverse delay is set to zero, and the maximum residence time is minimized.

项目成果

最大納期遅れ最小化基準におけるロバストバッチスケジューリング

具有最大交付延迟最小化标准的稳健批量调度

• 发表时间: 2022
• 作者: 呉偉;梅野慶人;渡邉夢大
• 通讯作者: 渡邉夢大

工事立会者手配問題に対する制約生成法および集合被覆アプローチ

施工见证排列问题的约束生成方法和集合覆盖方法

• 发表时间: 2022
• 期刊: 情報処理学会論文誌 数理モデル化と応用
• 作者: 高須賀将秀;呉偉;柳浦睦憲
• 通讯作者: 柳浦睦憲

多様な最適解の間の推移

各种最优解之间的过渡

• 发表时间: 2022
• 作者: Hirotoshi Honma;Yuya Sato;Yoko Nakajima;市来嵜治，菊地宥人，高木聡，池上 敦子，篠田 心治;加藤尚瑛，池上敦子;加藤尚瑛，呉偉，池上敦子
• 通讯作者: 加藤尚瑛，呉偉，池上敦子

An exact algorithm for the robust serial batching problem to minimize maximum lateness

用于最小化最大延迟的鲁棒串行批处理问题的精确算法

• 发表时间: 2022
• 作者: Keigo Miyagawa;Katsuki Hasegawa;Tang Liang and Wei Wu;Wei Wu and Liang Tang
• 通讯作者: Wei Wu and Liang Tang

Generating diverse solutions for nurse scheduling

为护士调度生成多样化的解决方案

• 发表时间: 2021
• 作者: N. Katoh;W. Wu;A. Ikegami
• 通讯作者: A. Ikegami