社団法人 日本オペレーションズ・リサーチ学会
ENGLISH
入会申込み お問合わせ
HOME オペレーションズ・リサーチ学会とは 研究活動案内 OR事典Wiki 機関誌 論文誌 会員の方へ
活動概要
会長挨拶
支部紹介
 

HOME > 論文誌  > JORSJ論文概要 


JORSJ 59-1 JORSJ 59-2 JORSJ 59-3 JORSJ 59-4 

JORSJ 59-1

1.
探索ゲーム: その文献とサーベイ
宝崎 隆祐 (防衛大学校)
 
この論文は探索ゲームに関する過去の文献を調査し,それらのモデルや手法を分類・解説したものである.探索ゲームは,いわゆる探索理論と呼ばれる研究分野の問題に対しゲーム理論を適用したモデル群であり,汎用的解法の提案よりは個別の問題解決を指向するものが多いため,この論文では,解法の詳述ではなく,その多岐にわたる問題発掘とモデリングを主として解説した.論文では,過去の文献を次の15のモデルに分類して述べた.密輸ゲーム(SG), 検閲ゲーム(IG), 2分探索ゲーム(BSG), 直線探索ゲーム(LSG), 潜伏・捜索ゲーム(HSG), 潜伏・配分ゲーム(HAG), 逃避・捜索ゲーム(ESG), プリンセス・モンスターゲーム(PMG), 待伏せゲーム(AG), 捜索配分ゲーム(SAG), 経路制約付き探索ゲーム(PCSG), 捜索・捜索ゲーム(SSG), ブロットゲーム(BG), 攻撃・防御ゲーム(ADG), ネットワーク阻止ゲーム(NIG).ただし,それらの歴史的背景から,SG,IG,BG,ADGとNIGについては簡単な解説とした.
2.
外部性のあるマッチング問題の研究に関するサーベイ
坂東 桂介,河﨑 亮,武藤 滋夫 (東京工業大学)
 

本論文では,外部性のあるマッチング問題についての研究のサーベイを行う.マッチング問題は,男性と女性,学生と学校,企業と労働者といった二つの異なる集団に属する人々の間の望ましいマッチングを取り扱う.通常のマッチング問題では,各主体は自分が組みうるパートナーのみに対して選好をもつ.他方,外部性のある場合には,各主体は自分以外の人々がどのようにマッチするかにも依存する選好をもつ.例えば,ある企業の利潤は,自社が雇っている労働者だけでなくライバル企業が雇っている労働者にも依存する.また,通学する学校に対する学生の評価は,学校の設備,運営だけでなくその学校に誰が通っているかにも依存する.これらは全て,外部性のあるマッチング問題として定式化できる.本論文では,外部性がある場合の安定マッチングの性質に焦点を当て,最近の研究成果を紹介する.

3.
位相型分布推定と信頼性工学への応用
岡村 寛之,土肥 正(広島大学)
 
PH分布は吸収状態を持つ連続時間マルコフ連鎖で定義され,一般の確率分布をPH分布で置き換えることにより,もとのモデルを連続時間マルコフ連鎖で近似できることから,信頼性工学や待ち行列理論における性能評価でよく利用されている.本稿では,確率密度関数やグループデータの情報からPH分布のパラメータを決定する統計的な手法の原理やアルゴリズムを概説し,その信頼性工学への応用事例を紹介する.
4.
レクトリニア図形配置問題に対する分割に基づく構築型解法
胡 艶楠 (名古屋大学)
橋本 英樹 (東京海洋大学)
今堀 慎治 (中央大学)
宇野 毅明 (国立情報学研究所)
柳浦 睦憲 (名古屋大学)
 
レクトリニア図形を長方形の容器に重なりなく配置する問題を考える.レクトリニア図形は垂直線分と水平線分のみで描ける多角形である.この問題は古典的な組合せ最適化問題の一つであり,これまで多くの研究がなされてきた.我々は先行研究において,長方形配置問題に対する二つの代表的な構築型解法であるbottom-left法とbest-fit法を一般化してレクトリニア図形配置問題への適用を可能にした.本論文では,これら二つの解法の配置結果を分析し,その分析結果に基づいて二つの解法両方の利点を活かす新たな解法を提案する.提案手法は与えられた図形集合をいくつかのグループに分割してグループごとにbest-fit法を適用するというものであり,二つの解法の自然な拡張になっている.提案手法で用いる分割方法とグループの順序についても,図形や配置結果の特徴を利用した様々な方法を提案する.計算実験の結果,図形数が多い問題例に対して,提案手法の性能が既存の構築型解法より高いことを確認した.
5.
既存製品との競合および開発・生産費用を考慮した新製品の属性の決定問題
Bibo Yang and Xiaoling Hu (The Hong Kong Polytechnic University)
 
This paper explores a situation in which a firm wants to add a new product to its existing product line in order to maximize its profit. A new product contains a group of attributes, and thus its development can be viewed as a configuration of attribute levels. Different attribute levels contribute to product variety and reduce cannibalization by product similarities. On the other hand, large variations in attribute levels often increase development cost and process variation cost. Thus, the impact of product cannibalization, development cost and production cost on new products should be evaluated. We formulate this selection of attribute levels as a nonlinear optimization problem. A heuristic is proposed to solve the problem efficiently, and managerial implications are provided.
ページトップへ戻る

JORSJ 59-2

1.
客がカウンター上のサービス位置を指定する待ち行列モデル
加藤 憲一 (神奈川大学)
高橋 幸雄 (東京工業大学)
 
客はカウンター上でサービスを必要とする位置を指定し,サーバーは指定された位置に移動して客に対する処理を行う待ち行列モデルを提案する.複数サー バーの場合,その並ぶ順序は固定され,互いに位置を入れ替えることができない.この制約のため提案する待ち行列は通常の待ち行列モデルとは異なる振る舞いをする.本モデルは大学図書館の移動集密書庫の性能評価の際に考案された.まず2サーバーの場合における呼損系モデルと飽和系モデルに対して解析を行い,呼損率とサーバー稼働率の性質を明らかにする.次により現実に想定しうる移動集密書庫のサービス規律を導入し,シミュレーションによってその性質を考察する.さらに移動集密書庫の設計に際し,サービス通路の個数などの検討を行った結果を紹介する.
2.
大規模分散並列処理におけるタスク複製の性能解析:極値理論によるアプローチ
平井 嗣人,増山 博之 (京都大学)
笠原 正治 (奈良先端科学技術大学院大学)
高橋 豊 (京都大学)
 

クラウド・コンピューティングで提供される大規模分散並列処理サービスは,巨大なタスクを多数のサブタスクに分割し,ワーカと呼ばれるマシン群で独立に実行する.このため,処理の遅いワーカがタスク処理全体に遅延を招く落伍者の問題が存在する.この対処法として,遅いワーカの担うサブタスクを別のワーカでも実行するタスク複製がある.本研究では,タスク複製の効率を理論的観点から評価する.そのために,ワーカの処理時間が超指数,ワイブル,パレートの各分布に従う場合において,タスクの処理時間の平均と標準偏差は極値理論を用いて近似値を,総処理時間の平均は厳密値を,それぞれ導出する.数値例から,タスク複製の効率はワーカの処理時間分布の裾に大きく依存する一方で,複製数が3あれば,裾に依らずタスクの処理時間の分散を低く抑えられることが判明した.

3.
非対称情報をもつネットワーク上での損耗ゲームモデル
宝崎 隆祐 (防衛大学校)
須永 桂一 (防衛省)
 
この論文は,ネットワーク上での損耗現象を伴う攻防ゲームを論じている.この問題は,インフラネットの防護や情報通信ネットワークにおける不法な侵入の阻止等様々な適用例をもつが,ここでは攻撃側と阻止側の間の2人ゼロ和ゲームとして一般化してモデル化される.攻撃側は出発ノードから目的ノードまで移動し,阻止側はアークに資源を配備して攻撃側を阻止しようとする.支払は攻撃側の残存量であり,攻撃側はそれを大きくするように,阻止側は小さくするように行動する.攻撃側がアーク上での配備阻止資源と出会うと衝突が起こり,攻撃側には資源量に比例した損耗が生じる.ここでは,攻撃側または阻止側の片方が相手に関する情報を非対称的にもつ4つのモデルを考え,それぞれの均衡解の導出法を提案した後,評価した情報の価値について比較・分析する.
4.
歪優モジュラ関数に対する交差解消ゲームについて
平井 広志 (東京大学大学院情報理工学系研究科)
 

本論文では,歪優モジュラ関数に対する交差解消ゲームを考える.それはRedとBlueの2人のプレイヤーからなるゲームで,カット被覆線形計画問題の双対解をラミナー解にする交差解消プロセスを抽象化したものである.我々は,Karzanovによる0-1値歪優モジュラ関数に対する既存結果を拡張・改良した多項式時間Red必勝戦法を与え,その帰結として,広いクラスのカット被覆線形計画の双対解に対する強多項式時間交差解消アルゴリズムを与える.また,ラミナー双対解の最適性条件に対する興味深い帰結も述べる.

ページトップへ戻る

JORSJ 59-3

1.
木における同順位を許す多対多安定マッチング問題
中村 圭太 (九州大学)
神山 直之 (九州大学/JST さきがけ)
 
ゲールとシャプレーによって提案された安定マッチング問題において,選好が同順位を含む場合は,安定マッチングは常に存在するがそのサイズは異なる可能性があることが知られている.本論文では,同順位を許す多対多安定マッチング問題における最大サイズの安定マッチングを求める問題を考える. この問題は各点の容量が1の場合でもNP困難となることが知られている.本論文では,入力されるグラフが木の場合を考え,一対一の場合に対する田湯と上野のアルゴリズムを拡張することにより,この問題が多項式時間で解けることを示す.
2.
弱実行不能半正定値計画問題の幾何学的解析
Bruno F. Lourenço (成蹊大学)
村松 正和 (電気通信大学)
土谷 隆 (政策研究大学院大学)
 

半正定値行列錐とアフィン空間の交わる点を求める問題である半正定値実行可能性問題の弱実行不能性について解析した.半正定値実行可能性問題については (i) 強実行可能,(ii) 弱実行可能, (iii) 弱実行不能, (iv) 強実行不能 の4つの状態があるが,弱実行不能問題は,半正定値行列錐とアフィン空間が交わりは持たないが両者の間の距離は0であるような問題である.本論文では特に,弱実行不能な問題に対し,行列のサイズをn×nとすると,元のアフィン空間上の一点に,それに付随する線形空間上の高々n-1本のベクトルの一次結合を適切に取って変位ベクトルとして加えることにより,半正定値錐との距離が漸近的に0となる点列を生成できることを,構成的に示した.興味深いことに,この高々n-1本のベクトルとしては,半正定値実行可能性問題の双対問題に対して面的縮小法を適用して生成される一連の方向ベクトルを用いることができる.基本的なアイデアは,元の実行可能性問題を,実行可能性の状態をほぼ保ったより小さな次元の実行可能性問題に変換することを繰り返すことである.この結果に関連して,上記4つの実行可能性の状態についての証拠とそのサイズについても議論した.

3.
システム故障頻度の新近似計算法
林 正博,山本 尚生 (東京都市大学)
 
故障頻度とは,システム信頼性の評価尺度の一つであり,単位時間当たりの平均故障発生件数と定義される.最近の研究によれば,故障頻度の増大がユーザの解約行動に大きく影響することが分かっている.しかし,故障頻度のこのような重要性にも関わらず,これまで実際問題への利用は限定的であった.それは,システムのサイズが大きくなると,その計算に要する時間が指数関数的に増大するからである.そこで,本論文では新しく近似計算法を提案する.本提案法を用いれば,システムが正常である確率の下限値と上限値が多重線形多項式として計算できるのであれば,その計算手順を,システムの故障頻度の下限値と上限値の計算手順に変換することができる.しかも,この変換に伴う計算時間の増加は定数倍に過ぎない.さらに,数値実験を行い,提案法の有効性を確認した.
ページトップへ戻る

JORSJ 59-4

1.
若化を伴う動的ソフトウェアアベイラビリティモデル
土肥 正,岡村 寛之 (広島大学)
 

本稿では多段階劣化レベルを伴うソフトウェアシステムを考え,定常アベイラビリティを最大にする最適な動的ソフトウェア若化方策をセミマルコフ決定過程を用いて導出する.また,Q学習に基づいた強化学習アルゴリズムにより,劣化レベルの推移に関する情報を利用しない適応型ノンパラメトリック推定アルゴリズムを開発する.数値例では,最適若化方策の導出方法を紹介すると同時に,強化学習による最適若化方策推定の漸近的なふるまいを調べる.

2.
多状態信頼性システムの直列システムへの分解
大鑄 史男 (名古屋工業大学)
 

二状態システムでは,極小カット集合を用いて構造関数が直列構造に分解され,max演算子を用いて統合される.この分解統合は,二状態システムにおけるさまざまな確率的評価方法の基盤になるが,分解統合の観点だけでなく,構造関数が極小カットベクトルの特定の状態ベクトルによって一意的に定まることも意味する.本論では,前者の観点を多状態の場合に拡張することを目指し,システムおよびそれを構成する部品の状態空間が半順序である場合の多状態システムを直列システムに分解し,それを用いた確率的上下界を示した.またこの議論のために,順序集合上で一般化された下界,上界を定義し,一般化された直列システムにおいて部品レベルでの直列化とシステムレベルでの直列化が同値であることが示されている.双対的な議論によって,以上の結果は並列システムについても容易に言い換えることができる.

3.
異なる視点からのトレンド再生過程に対するノンパラメトリック推定
齋藤 靖洋 (海上保安大学校)
土肥 正 (広島大学)
 

トレンド再生過程は,トレンド関数と呼ばれる時間変調関数によって互いに変換可能な計数過程と再生過程によって特徴付けられ,ある種の一般修理モデルを表現するために重要な役割を担う.本稿では,トレンド関数の関数形が既知であり再生過程の故障率関数が未知であるという仮定の下,トレンド再生過程のノンパラメトリック推定手法についての考察を行う.これは,トレンド関数が未知であり故障率関数の関数形が既知であるという仮定の下で考察されたHeggland and Lindqvist (2007)によるノンパラメトリック最尤推定量の対面に位置するものであり,彼らの研究結果を補完するものである.本稿では,シミュレーション実験を通じて提案するノンパラメトリック推定手法の有効性を評価するとともに,本提案手法を修理系システムの実データ解析に適用する.

4.
線形連続 k-out-of-n:F システムに対する予防保全政策
Alfonsus Julanto Endharta, Won Young Yun (Pusan National University)
山本 久志 (首都大学東京)
 

線形連続 k-out-of-n:F システムはn列に並んだコンポーネントのうちk個連続して故障する(極小カット)とシステム故障となるシステムである.本論文では,本システムに対してコンポーネント故障が指数分布に従うことを仮定し,ある一定期間後に,ちょうど1個のコンポーネントが稼働している極小カットが少なくとも1つ以上発生するとすべての故障コンポーネントを新品に取り換え(予防保全),その期間前にシステムが故障するとすべての故障コンポーネントを新品に取り換える(事後保全)という保全政策を考える.そして,そのもとで,時間当たりの期待コストを最小にする最適保全政策を提案している.

ページトップへ戻る
HOMEに戻る
イベントカレンダー
2017年度第4回ORセミナー
日程:
2018年1月20日(土)
場所:
南山大学
シンポジウム
2018年春季シンポジウム
日程:
2018年3月14日(水)
場所:
東海大学

2018年秋季シンポジウム
日程:
2018年9月5日(水)
場所:
名古屋市立大学
研究発表会
2018年春季研究発表会
日程:
2018年3月15日(木)-16日(金)
場所:
東海大学

2018年秋季研究発表会
日程:
2018年9月6日(木)-7日(金)
場所:
名古屋市立大学