メタヒューリステイクスによる汎用組合せ最適化アルゴリズムに関する研究

基于元启发式的通用组合优化算法研究

• 批准号: 15700012
• 负责人: 野々部 宏司
• 金额: $ 2.24万
• 依托单位: Hosei University (2005)Kyoto University (2003-2004)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15700012/
• 关键词: メタヒューリスティクス; 資源制約スケジューリング; 組合せ最適化; タブー探索; 汎用アルゴリズム

資源制約スケジューリング問題(RCPSP)の一般化として、凸型コスト関数の最小化問題を考え、メタヒューリスティクスにもとづくアルゴリズムの開発を行った。RCPSPの枠組みでは、多くの場合、種々の制約の下で作業をできるだけ早く完了することを目的とする。これに対し本研究では、2つの作業の開始時刻(もしくは完了時刻)の差に応じて定まる「時間ずれコスト」を導入し、その総和を最小化する問題を考えた。(ただし、時間ずれコストは凸関数に限定している。)これにより、納期ずれの最小化に対応することができ、さらにプロジェクトスケジューリングにおいて期間短縮の方法として用いられるクラッシングやファストトラッキングを扱うことも可能になった。アルゴリズムは局所探索法を基本としているが、最小費用フローアルゴリズムによる解の評価や、最小カットアルゴリズムを用いて解を改善する仕組みを組み込むなどの工夫を加えている。一方、昨年度より行っている重工業における鋳造ラインのスケジューリングについても本研究で開発したアルゴリズムの検証を継続して行った。その結果、より大規模なデータに対する計算実験において、問題の定式化の違いが計算時間に大きく影響することが確認され、適切な定式化を行うための指針について考察を行った。しかしながら、実用性を考えると、性能が定式化に大きく依存しないアルゴリズムを開発することが望ましく、今後の課題である。

The resource constraint problem (RCPSP) is generalized and the convex problem is minimized. RCPSP's work is done in a variety of situations. In this study, the problem of minimizing the difference between the start time and the end time of the operation was examined. () The method of shortening the time period of the production line is to minimize the production line and reduce the production line and reduce the production line. The minimum cost of the solution is evaluated, and the minimum cost of the solution is used to improve the solution. In the past year, the heavy industry has developed a series of research and development projects. The results, the large-scale calculation, the problem formulation, the calculation time, the confirmation, the appropriate formulation, the pointer investigation The development of the system depends on the performance of the system, and the future problems are expected.

项目成果

Heuristic approaches to the capacitated square covering problem

容量平方覆盖问题的启发式方法

• 发表时间: 2005
• 期刊: Pacific Journal of Optimization 1・3
• 作者: E.Boros;T.Ibaraki;H.Ichikawa;K.Nonobe;T.Uno;M.Yagiura
• 通讯作者: M.Yagiura

Efficient branch-and-bound algorithms for weighted MAX-2-SAT

• DOI: 10.1007/s10107-009-0285-6
• 发表时间: 2011-04
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: T. Ibaraki;T. Imamichi;Yuichi Koga;H. Nagamochi;K. Nonobe;M. Yagiura

A metaheuristic approach to the resource constrained project scheduling with variable activity durations and convex cost functions

具有可变活动持续时间和凸成本函数的资源受限项目调度的元启发式方法

• 发表时间: 2006
• 期刊: Topics in modern project scheduling(J.Weglarz, J.Jozefowska(eds.)) (出版予定)
• 作者: K.Nonobe;T.Ibaraki
• 通讯作者: T.Ibaraki

K.Nonobe, T.Ibaraki: "A tabu search algorithm for a generalized resource constrained project scheduling problem"The Fifth Metaheuristics International Conference. 55-1-55-6 (2003)

K.Nonobe、T.Ibaraki：“针对广义资源受限项目调度问题的禁忌搜索算法”第五届元启发式国际会议。

Metaheuristics : progress as real problem solvers

• DOI: 10.1007/b107306
• 发表时间: 2005
• 作者: T. Ibaraki;K. Nonobe;M. Yagiura