平成１１年度第２回KSMAP

次回の研究会では, 3名の学生に研究発表をしてもらった後, 京都大学の福島雅夫教授に, ご自分の研究歴を振り返ってお話ししていただくきました. これから研究者を目指そうとする若手には, きっとよい刺激になったと思います.

日時：６月４日（金）　１５：００─１７：３０

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

       京都大学へのアクセス

講演題目と講演者

  最小費用３点連結部分グラフを求める問題に対する近似アルゴリズム
    関 勝宏 （京都大学情報学研究科数理工学専攻）

  同質C-CBR多重化における遅延解析
    井上 大 （京都大学情報学研究科数理工学専攻）

  半導体スケジューリングについて
    宮崎 泰輔  （大阪大学大学院基礎工学研究科システム人間系）

  私の履歴書・非公式版
    福島 雅夫 （京都大学情報学研究科数理工学専攻）

講演要旨：

最小費用３点連結部分グラフを求める問題に対する近似アルゴリズム

関勝宏（京都大学情報学研究科数理工学専攻）

与えられた重みつきグラフGの最小費用３点連結部分グラフを求める問題を考える. この問題は, NP-困難であることが知られており, Nutov, Pennによる O(n²m)時間の３-近似アルゴリズムや, Dinitz, NutovによるO(n⁸)時間の２-近似アルゴリズムがある. ここで, n, mはそれぞれGの点数, 枝数である. 本論文では, 計算時間がO(n² m)の 7/3-近似アルゴリズムを提示する.

同質C-CBR多重化における遅延解析

井上大（京都大学情報学研究科数理工学専攻）

2010年までに全世帯に整備される予定である B-ISDNは, データ, 音声, 静止画像とビデオなどの様々なクラスを転送する. 様々なクラスの1つに, CBR(constant bit-rate)トラヒックという, セルが一定の率で周期的に発生するクラスがある. 実際のネットワークの中を流れている情報のほとんどは、 CBRトラヒックであり、そうでない場合でも最悪時の評価を行なう場合には, CBRトラヒックとみなすことができる。したがって、CBRトラヒックに対する研究は非常に重要であり、現在までも盛んに行なわれている. しかし, 実際に動いているネットワークの中継点での観測データによると, 従来考えられてたCBRトラヒックとは少し違い, 少し長めの一定周期の間に複数個（例えば 8個）のセルが一度に到着していることが明らかになり, それに対する解析が必要となった. 以下では, この連続して発生する複数個のセルをまとめてメッセージと呼び, CBRと区別するために, 一定の率でメッセージが発生するトラヒックを, C-CBR(Clustered Constant Bit-Rate Batch) トラヒックと呼ぶことにし, このC-CBRトラヒックの多重化に対する遅延時間の考察を行う. 同質C-CBRトラヒックの多重化に対する遅延時間解析が以前にも行なわれているが, メッセージの先頭のセルについての周辺確率分布だけが得られている. 今回はメッセージの中の 2つの異なるセルの遅延時間の差に関する確率分布を求める。

半導体スケジューリングについて

宮崎泰輔（大阪大学大学院基礎工学研究科システム人間系）

近年の半導体産業における競争の激化により、これまでにも増して利益向上のために機械の稼働率の向上、滞留時間の減少、スループットの増加という効率的な生産ラインの運用が求められるようになった。また、消費者側からの多品種少量生産、納期に合わせた生産等のいろいろな要求に対応できるシステムの運用も求められるようになった。このような半導体生産において生じてきた問題の解決を目的としたスケジューリング法について考察する。このために、半導体生産ラインの特徴を考慮して半導体生産ラインのモデルを作成し、このモデルに対してスケジュールを求めた。

私の履歴書・非公式版

福島雅夫（京都大学情報学研究科数理工学専攻）

ＫＳＭＡＰの主査・幹事から、専門的ではなく、一般的な内容の話をしてほしいと依頼されました。私自身の研究の歴史のような話などが良いということでした。ついに自分の歴史の話をする羽目になったとは私も先が長くはないなと苦笑しつつ、引き受けてしまいました。ということで、面白いかどうか分かりませんが、学生時代から現在にいたる過程を、特に若かりし頃のことを中心に１時間程お話しさせていただきます。

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

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

<最終更新作成日時 1999年6月4日 >