平成１１年度第６回KSMAP

第６回の研究会では, 神戸大学の玉置先生と 大阪大学の牧野先生にご講演をお願いしました. 
日時：１２月１日（水）　１５：００ 〜 １７：３０ 

場所：大阪大学 大学院 基礎工学研究科
      本館大会議室(2階)

       大阪大学へのアクセス

講演題目と講演者

  A Linear Time Algorithm for Recognizing Regular Boolean Functions
    牧野 和久 (大阪大学基礎工学研究科)

  メタ戦略によるスケジューリング問題へのアプローチ
    玉置 久 (神戸大学工学部電気電子工学科)
講演要旨：

A Linear Time Algorithm for Recognizing Regular Boolean Functions

牧野 和久 (大阪大学基礎工学研究科)

A positive (or monotone) Boolean function is regular if its variables are naturally ordered, left to right, by decreasing strength, so that shifting the non-zero component of any true vector to the left always yields another true vector. Recognition problem for regular functions is important in practical applications, since a number of intractable problems become tractable, if we restrict our attention to regular functions. Such examples include set covering problem, reliability computation, dualization problem and exact learning problem. In this paper, we propose a simple linear time algorithm to recognize whether a positive function is regular.

メタ戦略によるスケジューリング問題へのアプローチ

玉置 久 (神戸大学工学部電気電子工学科)

計算機環境の飛躍的な充実に伴って，試行錯誤をシステマティック かつ効率的に行うとでも言うべきメタ戦略 (Meta-Heuristics: MH) が注目されており，特に組合せ最適化問題への適用が盛んである． 生産スケジューリング問題についても，MH を応用することによって 効率的な求解が期待されている． MH としては，局所探索法，遺伝アルゴリズム，シミュレーテッド・ アニーリング，タブー・サーチなどが代表的であるが，スケジュー リングの問題をはじめとして最適化問題に MH を適用するための標 準的とも言える方法論は，未だ確立されていないというのが現状で ある．さらに，実際の生産システムでのスケジューリングに際して は，複雑な制約条件や多様な評価基準(目的関数)などにより，単に MH を適用するだけで望ましい解を得られるとは限らない． このような状況に留意して，MH による探索の枠組みの中に，問題固 有の知識・経験に基づくヒューリスティクスあるいは数理的なアル ゴリズムを組み込む形でのハイブリッド解法について研究を進めつ つある．本講演では，まず我々のグループとしての基本スタンス/ア プローチを明確にした上で．ハイブリッド解法の構成例をいくつか 紹介する．さらに，これらの例題を通してメタ戦略によるアプロー チの有効性・可能性について議論したい．
３０名の参加がありました．参加していただいた方々， どうもありがとうございました．
柳浦 睦憲(yagiura@kuamp.kyoto-u.ac.jp)
<最終更新作成日時 1999年12月2日 >