日時: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の定式化の拡張を行ってい る。本発表では、これらの拡張、アルゴリズム、計算結果について 述べる。