l＝ll＝l＝ll＝l＝ll川‖川‖‖＝l一日‖ll‖ll川‖l＝lll川川Ill＝ll＝‖l‖＝川＝l‖ll川l川Il川l＝l＝ll川棚川II‖‖‖‖‖＝l川Ill川l＝ll‖＝＝川l‖lltl‖川‖‖＝‖lll川l＝‖ill＝‖川Il

論文誌掲載論文概要
JO R SJ

Vol．39，No．1
日＝‖‖＝‖‖川川川＝‖＝‖＝日日‖川‖＝lI＝‖＝lll＝l川l＝川‖‖川‖‖川Il‖lll川l川‖ll川‖‖＝l‖l＝l‖l川‖＝ll＝ll川Il川l‖lll＝‖‖川l川l川‖‖川‖‖＝l川Il＝‖川‖l

ゲートを持つ離散時間待ち行列システ皐の解析−ゲート開閉間隔が幾何分布に従う場合一石崎 文雄（徳島大学）滝根哲哉（大阪大学）
長谷川利治（京都大学）●ービス終了直後に乃人の客がいるとき，min（〝，〝）の客を同時にサービスしはじめる．またそのサービス率はサービスされる数に依存した指数分布に従うものとする．客の到着時点における待ち行列長とサービス中の客数の同時分布が隠れマルコフ連鎖をなし，その本論文はゲートを持つ離散時間待ち行列システムを推移確率行列が行列幾何的構造をもつことを示す．ま解析する．このシステムは2つの待ち行列と1つのゲた行列幾何的解における率行列斤が計算しやすい形ートから構成される．客は集団／ヾルヌーイ過程に従っで求められることを示し，その斤を用いて，客の到着て到着し，そのサービス時間は独立同一の一般分布に時点における定常待ち行列長が計算できることを示す．

従う．客は到着すると，まずゲートの前にある第1番さらに客の到着時点における任意の客の定常待ち時間目の待ち行列に並ぶ．ゲートが開くと第1番目の待ち分布のラプラス・ステイルチェス変換とモーメントの行列で待っていたすべての客はサーバの前にある第2求め方を導出する．

番目の待ち行列へ直ちに移動する．第1番目の待ち行列から第2番目の待ち行列にすべての客が移動すると直ちにゲートは閉まる．サーバは第2番目の待ち行列

補助倉庫容量とパレット数に制約のあるフレキシブル製造システムの設備容量決定法

長沢 啓行（大阪府立大学）にいる客に対してのみサービスを行なう．本論文においてはゲートの開く間隔は独立同一の幾何分布に従うム（FMS）において，システム内のジョブ数があるしものとする．

●

ジョブがポアソン到着するフレキシブル製造システ

この待ち行列システムの興味のある特徴は，システ

きい値に達している間に到着したジョブは，代替シス

ムに内在する種々の相関である．たとえば，第2番目テムへ回され，そこで加工されるようなシステムを近の待ち行列に一度に移動する集団を1人の客と見ると，似閉鎖型待ち行列ネットワークを用いてモデル化した．

その客の到着間隔とサービス時間の間には正の相関がこのしきい値は，到着ジョブを一時保管する補助倉庫ある．本論文では，この待ち行列システムに関して待の容量と利用可能なシステム内パレット数の和で表わ

ち行列長，仕事量，待ち時間の第1番目の待ち行列とされる・また，シヲツプ内ジョブ数が利用可能なシス第2番目の待ち行列に関する結合確率母関数が導かれテム内パレット数に達すると補助倉庫からショップ内る．さらに数値例を用いて，稜々の相関の影響が論じへの搬入がブロックされる．このFMSの生産率を近られる．

似閉鎖型待ち行列ネットワーク・モデルで求め，サービスされる数に依存したサービス率をもつ集団サービスGl／M／1待ち行列
馬場 裕（横浜国立大学）

サービスされる数に依存したサービス分布をもつ集SIMANシミュレーション結果との比較により，負荷均等配分等のFMSでは生産率が非′削こ精度よく得られることを例示した．さらに，近似生産率関数の補助倉庫容量や利用可能パレット数に関する極限，単調性および凹性を証明した．補助倉庫容量と利用可能パレ団サービス待ち行列についていくつかの研究が行なわ

ット数の和または加重和に制約がある場合に，FMSれているが，それらはすべてポアソン到着を仮定しての生産率を最大にするための補助倉庫容量と利用可能いる．本論文では，到着時間間隔が独立で一般分布にパレット数の決定問題を定式化した．この問題に対し従い，サービスされる数に依存したサービス率を持つて，生産率関数の上記諸性質を駆使した効率的な解法集団サービスGI／M／1待ち行列の解析を行なう．サを提案した．

1996年3 月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（51）18丁凸多面体上におけるランク2鞍型関数の効率的な最小化算法

究では，アークの長さを必ずしも非負としないネットワークにおいて，台車運行型SPPTWの構造解明も試みている．まず，原問題をいくつかの部分問題に分割

久野 誉人（筑波大学）

あるクラスの連続な非凸関数′：尺乃→斤1を凸多面し，次にこの部分問題に動的計画法を適用する．この考え方はタイムウィンドウがない場合の古典的な最短体β⊂斤乃上で最小化する効率のよい算法を提案する．

経路問題とも類似することから古典的なBellman−

ここで扱う関数′は，2つの1次独立なべクトルCl，Ford法やYenの方法と同■じ構造をもつ解法が提案でら∈斤乃によって次のように特徴づけられる：ある連

きる．論文ではさらに分枝限定法的な解法についても続関数g：斤2→尺1が存在し，任意のズ∈斤乃で／（ズ）＝g

提案し，計算の複雑性に関する理論的および数値的な（（：1㌦，C2㌦）が満たされる（ランク2性）；ズ∈斤乃を任考察も行なっている．

意に固定すれば，g（・，Q㌦），g（cl㌦，・）はそれぞれ凸関数，（準）凹関数となる（凸凹性）．ただし，提案する算法で関数gを陽に知る必要はない．凸凹性により問題には複数の局所的最小解が存在するが，（準）凹

人的資源スケジューリングにおける困難問題に対する組合せ的アプローチ

Hoong Chuin Lau（東京工業大学）

関数の最小化と異なり，βの端点に大域的な最小解が資源管理問題の1つである人的資源のスケジューリ含まれると・は限らない．この2つの特徴をもつ関数にング問題について考察した．この間題は，一般には，は，線形乗法関数（2つのアフィン関数の積），d．c．関NP困難であることが知られているので，どの程度ま数（2つの凸関数の差）をはじめととして応用上重要で実際的に解けるかを見究めることが重要になってくなものが多い．

る．本論文では，次の3つの場合を考え，そのそれぞ本稿では，パラメトリック単体法によって問題が1次元の子問題たちに分解されることを示し，各子問題れに対して，組合せ論的アルゴリズムを提案した．
（1）各曜日の労働力（人手）の需給が一致しており，の∈最小解の計算に／の劣評価関数を用いた分枝限休みの日が固定されている場合．この場合には，グラ定法を適用する．∈＝10」5の精度での計算実験で，提案フの道被覆を解くアルゴリズムを用いて，0（〃2・5）の時する算法は変数の数300までの問題を数分で解いてい間で解くアルゴリズムを示した．（2）人手が余る曜日る．また，ある確率的な仮定の下では，．部分クラスのを許した場合．ただし，スケジューリング制約が単調乗法計画問題やある種のNP一完全な凹2次計画問題のとき，この場合には，分枝限定アルゴリズムで疑似は，平均的に問題規模の多項式時間で大域的な最小解多項式時間で解けることを示した．（3）一般の場合が求められることを示す．

（すなわち，NP困難な場合）．この場合にも，固定費台車運行型タイムウィンドウのあるネットワークでの最短経路問題
宮崎隆祐（防衛大学校） 藤井 進（神戸大学）

つきネットワークフロー問題に還元することができることを示し，解き方の手がかりを与えた．

取引コストを考慮したポートフォリオ最適化

三道弘明（流通科学大学）

吉本 敦（宮崎大学）

工場内搬送系における無人搬送台車（以下，AGVとポートフォリオの収益率を向上させるには，収益率いう）の経路決定問題は，タイムウィンドウと呼ばれの高い資産の組み入れ比率を上げるか，あるいはポーる時間制約がノードおよびアークにあるネットワークトフォリオ構築に関わるコストを下げる必要がある．

上での最短経路探索問題として定式化できる．これま一般的にハイリスク・ハイリターンの観点からいえば，でにもタイムウィンドウの研究はされているが，上述

前者の方法ではポートフォリオの安全性が損なわれるしたタイムウィンドウとはその性質が異なるが故に危険性があるが，後者の方法ではポートフォリオの安AGVの経路決定には使用できない．本論文は，前者の全性にはなんら支障をきたすことがなく，リスクを伴台車運行型と呼ぶタイムウィンドウを考慮した最短時わない戦略といえる．本研究では，資産の収益率・リ間経路問題（台車運行型SPPTW）に対する解法を提スクそしてリバランスに伴うコストを同時に考慮した案したものである．この問題は，交通路問題やスケジポートフォリオ最適化問題を定式化し，コストの最適ューリング問題等多くの応用分野が考えられる．本研

ポートフォリオに及ぼす影響について解析を行なった．

188（52）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

取引コストにはⅤ一型非線形関数（組み入れ比率の変を入力としてもつ割り込み優先権付き待ち行列モデル化量の絶対値の関数）を仮定した．ポートフォリオ最を解析する．割り込み規律は継続型，繰り返し型双方適化問題の定式化には平均・分散理論を用いた．解析を含む．非優先呼に着目することにより，モデルを非の結果，取引コストの有効フロンティア，ポートフォ優先呼入力，セミマルコフサービス，サーバ・バケーリオの実質収益率に及ぼす影響は無視することができションのあるモデルと見なす．この結果，サーバ・バず，最適なポートフォリオを構築する際には，資産のケーションはi．i．d．でもなくなるうえ，サービス過程に収益率のみならず，ポートフォリオのリバランスに関依存する．したがって，セミマルコフサービス，サーわるコストも考慮する必要があることがわかった．

ビス依存サービスバケーションをもつ非ノ削こ一般的なモデルの解析を行ない，非優先呼退去直後における定サーババケーションのあるモデルとしての常系内呼数分布と残ー）仕事量の分布を求める．さらに，割り込み優先型待ち行列
町原文明（NTT通信網研究所）

系内呼数分布と系内時間との関係式を明示する．結果はすべて既存結果を含んでいる．

2種のマルコフ到着過程（位相マルコフ再生過程）

1996年 3 月号

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（53）189