日時：2005年 12月6日（火） 15:00〜18:00 場所：京都大学 本部構内 工学部総合校舎 総合213講義室 講演題目と講演者： ・ 松本 一輝（関西学院大学 理工学部 情報科学科） 「段ボールの製造スケジューリング」講演要旨 ・ 大黒 健太朗（京都大学大学院 情報学研究科） 「BMAP/D/ｃ待ち行列における系内客数分布」講演要旨
段ボールの製造スケジューリング
松本 一輝（関西学院大学 理工学部 情報科学科）
段ボールの紙は，表中裏3種類の紙を貼り合わすことにより構成される．各注文では，3種類の紙の種類，長さ，幅が指定され，各々３本のロールを持つ機械か ら引き出され，貼り合わされ，切り取られる．機械は複数あり，スケジューリングの前半は，各注文をどの機械で処理するかということを一般化割り当て問題と して定式化した．このとき，ロールの全長と幅の不整合により生じる紙のロスを最小化する．後半は，各機械に割付けられた注文の処理順序を求める問題に対 し，問題の性質を利用した効率的な近似アルゴリズムを与えた．
BMAP/D/ｃ待ち行列における系内客数分布
大黒 健太朗（京都大学大学院 情報学研究科）
本研究では，固定長サービスと集団マルコフ型到着過程(BMAP：Batch Markovian Arrival Process)を入力とする複数サーバ待ち行列(BMAP/D/c待ち行列)の系内客 数分布を解析する．BMAPは解析的に扱いやすく，また，到着時点列が順序性を持 つような集団到着過程の族に対して稠密に存在することが知られているため，こ れまで多くの研究者がこのBMAPを入力とする待ち行列モデルの研究を行ってき た．しかし，複数サーバモデルではFIFO(First-In-First-Out)が成り立たず，一 般に解析が難しいとされており，特に過渡解析に至ってはほとんど研究がなされ ていない．本研究ではBMAPを入力とした複数サーバ待ち行列に対して，固定長 サービスを仮定することで，1サービス長を単位時間とした系内客数分布の時間 発展方程式を導出し，過渡状態での系内客数分布を再帰的に計算するアルゴリズ ムを構築した．さらに，その時間発展方程式を基に定常状態での系内客数分布と そのモーメントを計算する手法も確立した．