………lllll………ll……ll……lll…l…………l川…………l………l……llll……lll………刷Illl…lll…‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖‖‖‖＝‖‖‖‖‖州l

論文誌掲載論文概要

JORSJVol．48，No．3，TORSJVol．48
1……＝＝＝‖‖‖＝‖‖＝‖‖＝‖‖…‖llll…llltl…潮岬111…ll川…ll…1‖‖‖＝＝‖仙Il】………tt…l…………l…冊…川‖‖‖‖＝‖附……1……………‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖‖＝＝＝川棚Il‖‖‖‖州…ll…llllll……lll‖‖＝‖＝‖‖‖‖‖‖‖胴証を与える．最後に，最小費用流問題における実行可●JORSJVol．48，No．3

能基底の個数について，主問題では高々カタラン数で供給業者が部分的買掛を許した場合の小売業あり，双対問題では少なくとも指数オーダになることを示す．

者の在庫政策Yung−Fu Huang

木構造動的ネットワークにおける避難問題と（ChaoyangUniversityofTechnology，Taiwan）木分割問題
間々田聡子（大阪大学）

本論文では，部分的買掛が行われる場合の経済発注

宇野 毅明（国立情報学研究所）量（EOQ）を議論する．本論文の主目的は，1985年

牧野 和久（大阪大学）のGoyalのモデルの仮定を緩和し，単位販売原佃と藤重 悟（京都大学）

単位購入価格が必ずしも一致しないこと，および完全な買掛ではなく部分的な買掛を行うことを仮定したモ

本論文では，点の部分集合がコストを持つ木構造ネデルを扱うことである．後者の仮定は，小売業者は注

ットワークに対する分割問題を考察する．単調なコス文時に供給業者に購入価格の一部分を支払い，一定期トを持つmin−maXタイプの分割問題に対して多項式間後に残額を支払わなければならないことを意味する．

時間アルゴリズムを提案する．また，単調でないコス

この条件の下で，小売業者の在庫費用を最小にする最トを持つmin−maXタイプの分割問題はNP困難であ

適発注周期と最適発注量を求める在庫モデルをモデルることを証明し，さらに，コストが単調であっても，化し，小売業者の最適な在庫政策を効率的に求めるた

minqsumタイプの分割問題は，NP困難であることめの定理を展開する．この結果は，従来の研究結果をも証明する．

特別な場合として含む．最後に，この定理を説明するために数値例を示す．

（山下英明 訳）

ネットワーク流問題や単模な整数計画問題における主基底および双対基底の個数について
石関 隆幸，中山 裕貴，今井 浩（東京大学）

この木分割問題は，木構造動的ネットワークにおける避難問題の自然な一般化である．ここで，動的ネッ
トワークは，各枝が容量と移動時間を持つ有向グラフによって定義され，木分割問題は，木構造動的ネットワークにおいて，与えられた供給量を与えられた出口集合へ最速に送り出すフローを求める問題として定式

近年，整数計画問題に対して，グレブナ基底や標準化される．ただし，各点においてその点を経由するフ対を用いた計算代数的手法が研究されており，これにローは，その点に接続する同一の枝を通ると仮定し，より計算代数的手法と組合せ的手法を関連づける試み送出される出口に対応して木の分割が定まる．

がなされている．本研究では，主問題と双対問題を同条件下で扱うために，係数行列が単模である場合を考え，そのもとで以下の結果を得た．

セルラ移動体通信網におけるハンドオーバ数の分布：遅延再生過程による方法
Ram6n M．Rodr盲guez−DagnlnO

まず，整数計画問題の双対実行可能基底の最大数は，係数行列により生成される凸多面体の正規化体積を計（MonterreyInstituteofTechnology，Mexico）

高木 英明（筑波大学）算することで得られることを示す．次に，この結果を無閉路トーナメントグラフ上の輸送問題に適用し，主セルラ移動体通信網において，呼の継続時間内に起バ数の分布を知ることは，無線セルに問題および双対問題の実行可能基底の最大数に関するこるハンドオー既存の結果について，計算代数的アプローチによる別許容される回線数を決めるために重要である．本論文

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

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

では，種々の呼継続時間分布とセル滞在時間分布に対待完【r時刻を最小にすることである．この間題を動的し，ハンドオーバ数の確率分布とモーメントを計算す

計画法により定式化し，再帰方程式の性質と最適政策

る．呼がセルの内点から発生する場合のように，最初を与える境界値の性質を導いた．のセル滞在時間分布がそれ以後のセル滞在時間分布と異なってもよいとして，遅延再生過程の理論を適用す
る．特に，円形のセルの場合を詳しく解析する．数値●TORS」Vot．48（和文論文誌TORSJは年1回，12月に刊行されますが，電子ジャーナルとしては学会ホームページに随計算結果を含む．

時掲載されます．）

マルコフ型フィードバックを持つマルチクラ
スポーリングシステムー局内に優先度順と独立分散最適化によるネットワークにおけるFCFS順のサービス順序を持つゲート方式と性能劣化パラドックスとその大きさ

亀田 幸夫（筑波大学大学院）

全処理方式のシステムにおける平均滞在時間
平山 哲治（筑波大学）
本論文では次のようなポーリングシステムにおけるInternetやGRIDなど，多数の独立した個人や企業体が共用するネットワークや分散システムが社会の客の平均滞在時間を求める．一人のサーバーがシステ根幹をなしてきている．各個人や組織体は独立していム内の局を巡回しながら，各局の客をゲート方式あるるので，（経路選択や負荷割り当て等に関する）分散

いは全処理方式でサービスする．各局には複数クラスした意志決定により，独自の工夫で使用効率やコストの客が到着し，その局内では優先度順あるいは先着削減を追求すると，いわゆる神の見えざる手によるが（FCFS）順でサービスされる．各客はサービス終了ごとく，全体として良い方向へ導かれるとの期待が持後，マルコフ型フィードバック機構によって，ある局たれる．また，全体的な意志決定による上意下達的なに進むかあるいはシステムを離脱する．次のような解割り当てによるよりも，互いの切磋琢磨により，諸側析方法を用いる．まず各客の到着時点のシステムの状面のより多くの進歩が期待される．しかし，独立意志態での条件付期待滞在時間を定義し，それが状態の線決定分散には，ゲームの理論における囚人のデイレン形関数になることを示す．定常状態での平均滞在時間

マのように，全ての個体が努力した結果かえって全てはそれの極限操作によって求められ，実際の値は一次の個体に対してコストや応答性能の劣化がおこるとい方程式を解いて求める．複雑なスケジューリング方式う可能性が危惧される．特に，ネットワークにおけるを考えることができ，各客のサービス経路ごとの平均Braessのパラドックスのように，ネットワークや分滞在時間（meanpathtime）を求めることができる．

散システムに新たに設備を増設したり，結合度を増し一機械における絵期待完了時刻を最小にする
ベイズ的逐次バッチサイズ決定問題たりして，各個体の意志決定の自由度が増すと，かえって，全ての個体に対する効用が低下してしまう場合がいくつか報告されている．

濱田 年男（兵庫県立大学）

時刻0で処理開始可能な同一種類のn個のジョブ

本稿は，独立分散意志決定をするネットワークや分散システムにおいて，そのような劣化が起こる場合，を1台の機械で処理する．複数のジョブを1つのバッその大きさが，どの程度になりうるかについて，これチとして処理する場合に，バッチ内の最初のジョブのまでのいくつかの研究成果を概観する．

処理前に1回の準備時間を必要とし，後はジョブ数に比例した処理時間を必要とする．ジョブの処理時間はすべて同じで既知であるが，準備時間はパラメータが未知のガンマ分布に従い，その未知パラメータはガンマ分布を事前分布として持つ．同一バッチ内のジョブ

ネットワーク外部性の働く製品市場のモデル化とプレゼント戦略の評価
川村 秀憲，大内 東（北海道大学）
本論文では，ネットワーク外部性の働く製品市場のの完了時刻はすべて同じである．まず最初のバッチサ

モテリレ化とプレゼント戦略の評価を行う．エージェンイズを決定して，そのジョブを処理し，準備時間を観トベースモデルを用いることにより，消費者間の相互iRljした後，次のバッチサイズを決定する．すべてのジ作用ネットワークを明示的にモデルに取り込むことがョフやを処理し終えるまでこれを繰り返す．目的は総期可能である．本モデルは，消費者間のネットワークの© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

2005年91】号（65）66丁構造とネットワーク外部性の効果の関係について明ら数であるプレゼント戦略を導入し，その有効性の検証かにすることが出来る点に特徴がある．シミュレーシを行う．実験結果より，ネットワークの構造と有効な

ョンでは，企業の視点に立つことにより，競争が重要プレゼント戦略には密接な関係があり，同じ数のプレな意味を持つネットワーク外部性を有する製品の市場

ゼントを行っても構造に応じて効果的な戦略が存在すにおいて，企業が独立に操作可能なマーケテイング変ることを示す．

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

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