平成15年度第3回KSMAP


日時:10月29日(水) 15:00〜17:00

場所:京都大学 工学部8号館共同6講義室(3階)
      http://www.kuamp.kyoto-u.ac.jp/map/index-map.html
      http://www.i.kyoto-u.ac.jp/top/address.html
      
講演題目と講演者:

・ 山下信雄
  (京都大学大学院情報学研究科)
  「DSLシステムの電力配分問題に対するゲーム理論アプローチ+α」講演要旨

・ 野々部宏司
  (京都大学大学院情報学研究科)
  「資源制約スケジューリング問題:メタヒューリスティクスによるアプローチ」講演要旨
  

講演要旨:

DSLシステムの電力配分問題に対するゲーム理論アプローチ+α
山下信雄(京都大学大学院情報学研究科)

電話回線を用いたDSLは高速インターネットの代表的技術の1つ である.多くの電話回線は1つのケーブルにまとめられて配線され ており,同一ケーブル内に含まれる電話回線間では電磁波による干 渉がおきる.そのため,すべてのユーザが高速な通信を実現するた めには,通信に用いる電力の配分が重要となる.すべてのユーザの 伝送情報量の和を最大にする問題は凸計画問題にはならない.しか しながら各ユーザが自分の伝送情報量を最大化する問題は凸計画問 題となる.そこで,各ユーザが自分の伝送情報量を最大化する非協 力ゲームのNash均衡を求め,その均衡解を電力配分に用いることが 提案されている.本発表ではこの均衡を求める問題を非線形相補性 問題として定式化し,その非線形相補性問題の性質を明らかにする. 具体的には扱う関数がP0関数となる条件や解がb-正則となる条件を 与える.さらに効率のよい解法を提案する.また,より高速な通信 を可能にする拡張モデルを提案を行う. 時間が許せば,「非等間隔分布したアレイアンテナの高指向性を 与えるパラメータの設定法」についてや,カナダでの1年間の滞在 経験についての話をするつもりである.

資源制約スケジューリング問題:メタヒューリスティクスによるアプローチ
野々部宏司(京都大学大学院情報学研究科)

資源制約スケジューリング問題は、限られた資源の下、複数の作業 をどのように処理するか決定する問題であり、幅広い分野において 現れるスケジューリング問題を定式化することができる。そのため、 高性能な RCPSPアルゴリズムは、様々なスケジューリング問題を扱 うことのできる汎用スケジューラとして用いることができる。この 考えに基づき、我々はこれまでに RCPSP に対する近似解法の開発、 および現実のスケジューリング問題への適用を行ってきた。近似解 法の枠組みとしては、メタヒューリスティクスを用いている。最近 ではさらに、アルゴリズムの適用範囲を拡げるため、凸型コスト関 数の導入や作業中断の許可など、RCPSPの定式化の拡張を行ってい る。本発表では、これらの拡張、アルゴリズム、計算結果について 述べる。


22名の方々に御参加いただきました.御礼申し上げます.
巳波弘佳(Hiroyoshi Miwa)
最終更新作成日時:2003年10月30日