平成１２年度第５回KSMAP

平成１２年度第５回のKSMAPでは，京都工芸繊維大学の木瀬先生と中央大学の平田さんに講演をお願いしました．

日時：１１月２１日（火）　１５：００ 〜 １７：３０ 

場所：京都大学 工学部８号館 共同２講義室

      京都大学へのアクセス

講演題目と講演者

  極値理論を用いたメタヒューリスティックスの性能評価
    平田 敦 (中央大学大学院理工学研究科情報工学専攻)

  スケジューリング研究の過去・現在・未来
    木瀬 洋 (京都工芸繊維大学)

講演要旨：

極値理論を用いたメタヒューリスティックスの性能評価

平田敦 (中央大学大学院理工学研究科情報工学専攻)

メタヒューリスティックスとは, 近傍探索を基礎とする組合せ最適化手法の総称である. 代表的なものに, 模擬アニーリング法, タブー探索法, 遺伝的アルゴリズムなどがあり, 高精度近似解を構成する枠組みとして実用性が高く, 様々な組合せ最適化問題への応用がみられる. しかし, これらの手法に対する確固とした評価方法はなく, また, 一般に最適性の保証もないことから, 得られた解がどれだけ良い解か, もしくは悪い解かを見積ることが重要であると考えられる.
　R. A. Fisher and L. H. C. Tippett (1928) は, 標本の大きさ n が無限に大きくなるとき, 位置母数と尺度母数を適当に調節することで, 標本最大値, 最小値の分布が限られた3種類の極限分布に収束することを示した. この理論は, 極値理論と呼ばれ, 材料強度, 洪水の研究などに広く応用されている.
　本研究では, メタヒューリスティックスの各手法で得られる解を標本最大値 (最大化問題), もしくは標本最小値(最小化問題) と考え, これらの分布に対して極値理論を適用し, メタヒューリスティックスの各手法で得られる解の精度に対する見積りを行う. 具体的な問題例として, 0-1ナップサック問題, 巡回セールスマン問題を用いる.

スケジューリング研究の過去・現在・未来

木瀬洋 (京都工芸繊維大学)

ガントチャートから始まるこの１００年間のスケジューリング研究・技術の歴史を主なシステム技術と対比させながら、振返る。また、今後のスケジューリング研究のあり方についても言及したい。

４２名の参加がありました．参加していただいた方々，どうもありがとうございました．

柳浦睦憲(yagiura@amp.i.kyoto-u.ac.jp)

<最終更新作成日時 2000年11月22日 >