':'11111111111111111111111'11111111111'111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

ig

論文誌掲載論文概要

2

JORSJ

Vol.33, No.2

一般化されたシステムに対するリライアピリティの上・下界のスケジューリング問題を取り上げる.

1 台の機械では同時には 1 種類の製品しか生産できないので，各製品の需要を品切れなく満たすためには，適切なロットサイズ

大阪大学新森修一

で各製品を切替生産することが必要になる.

愛知工業大学大鋳史男

本研究では，各製品の需要速度，生産速度，非稼働時

大阪国際大学西国俊夫

間，生産ロット+イズ，生産順序といった要因の関係にシステムの厳密なリライアピリティを求めることは，着目し，無限大の計画期間の上で品切れや不要な在庫な信頼性理論において最も基本的な事項の 1 つであり，実く需要を満たす生産スケジュールは，切替えなどに使わ際のシステムの設計などには必要不可欠であろう

とこ

れる非稼働時聞を考慮した生産能力と各製品の需要速度ろが，一般に，厳密なシステム・リライアピリティを算の合計値(総需要)がパランスしている場合にのみ存在出するのに要する演算回数は，システムを構成する部品することを証明している.製品聞に非稼働時閣が必要なの数やそれらの取り得る状態空間の大きさにより指数的場合には，に増大する.そのため，システムが大規模で複雑なもの十イズの下で実行可能なスケジュールが一意的に決まる“均衡ロットサイズ"と名づけた生産ロットになればなるほど，システム・リライアピリティを求めことを示し，その均衡ロットサイズを導いている.非稼ることは困難となる.このような理由で，システム・リ働時聞が 0 で連続生産が行なわれる場合には，サイクルライアピリティの上・下界 (stochastic bounds) を比較

タイムの定め方により無数の実行可能なスケジュールが的容易に計算可能な方法が重要となり，これに関する研得られる.いずれの場合も，各製品の生産ロットサイズ究がいくつかすでになされている.これら従来の研究に(均衡ロットサイズ)は，各製品の需要速度と+イクルタ

おいては，システム，部品の状態空聞を 2 要素全順序集イムに比例して決まるという特徴がある.

合あるいは有限全順序集合に制限した上で論じている.

本研究で明らかとなった種々の要因間の定量的な関係

本論文では，システムおよび部品の状態空間が半順序は，小ロット生産システムを設計するさいや，十分長い集合で定義されたより一般的なシステムを新たに導入

有限な計画期間の上での生産スケジュールを求めるさいし，などに実用的な指針として役立つ.

システムの状態を規定する極大，極小元から sto­

chasticbounds が導出可能であることを示す.また後半においては，システムが L 、くつかのモジュール(サブシステム)に分害Ijされる場合について述べる.各モジュー

区分的に線形なリスク関数を用いたポートフォリオ最適化宅デル

んが MC と呼ばれる構造上のある性質を満たしていれば，前半で述べた上・下界より常に良いものとなっていることを示す.最後に，提案した式の簡単なシステムへの適用例と演算回数に関する簡単な評価を行なう.

1 機械多製品ロットスケジューリング問

東京工業大学今野浩

本論文では，表題どおり，区分的に線形なリスグ関数を用いた新しいポートフォリオ最適化モデルについて論じたものである.

このモデルは，古典的なマーコピッ

ツ・モテツレとよく似た発想にもとづくものであるが，マーコピッツ・モデルにない，いくつかの長所をもってい題での均衡ロットサイズ

る.まず第 l は2 次計画問題のかわりに線形計画問題

慶応義塾大学河野宏和

を解けばよいため，計算の手間が大幅に軽減されること

慶応義塾大学中村善太郎

である.第 2 は，実際の取引に付随する最小売買単位の一定の需要速度で継続的に使用される複数の製品を，取扱いがマーコピッツ・モデルに比べて容易なこと，そ1 台の機械でサイクリックな順序でロット生産するときして第 3 は，平均と分散は同じであるが 3 次のモーメン

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

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

トが異なる 2 つのポートフォリオを区別できることであ点を中心としていくつかの海域を考え，探索を海域単位で行なうと L 、う方法が考えられる.もし連絡がとだえたる.

本論文ではまた，ここで提案したモデルにおける資本地点が探索者にとって全く不明であり，かつ彼が探索費市場線の存在を示し，ある非退化仮定の下で，個別j 銘用の支出について慎重であると仮定すれば，状況をゲー

柄の平均収益率と市場平均収益率との問に成り立つ関係ムとしてとらえることも考えられるを導いている.

デルを扱う.

最後に株式 50 に含まれる 50銘柄に関するデータを用い

セル 0， 1 ， "'， n がこの順で一列に並んでいる.プレーて数値実験を行ない，このモデルの有用性を実証してい

ヤー 1

る.

後動かない.プレーヤー 2

最小費用流問題に対する多項式時間の内点アルゴリズム

ここでは，次のモ(逃亡者)はセル 1 ， ".， n のいずれかに隠れ，以(探索者)はセノ L- 0 から出発して発見するまで各セルを探していく.各セノレを探すことに固定探索費用がかかり，セノレからセノレへ移動するのに，距離に比例した費用がかかる.もしもプレーヤー 1が隠れたセルをプレーヤー 2 が探したら確実に発見す東芝増沢香

る.プレーヤー 2 はできるだけ早くプレーヤー i を発見

東京工業大学水野健治

したい.プレーヤー 1 はそれをできるだけ遅くしたい.

東京工業大学森利得はプレーヤー 2 からプレーヤー 1 へ，期待探紫費用

雅夫

本論では，最小費用流問題を多項式時間で解く内点アであるとする.

ルゴリズムを提案する.内点アルゴリズムは，一般の線

このゼロ和ゲームの値，各プレーヤーの最適戦略が与形計画問題の多項式時閥解法として，最近急、速に発展しえられる.さらにプレーヤー l の最適戦略は 1 つしかなた.現在のところ，理論的に最も効率のよい内点、アルゴいことが示される.

リズムの計算時間は，変数の数を nf閤，入力データの総ピット数を L とするとき ，O(n 3 L) である.このアルゴ多面体の最小ノルム点を見出す双対算法

リズムをノード数 V 個アーク数 E 個の最小費用流問題に筑波大学藤重適用すると，その計算時聞は O(E3L) である筑波大学

これに対して，本論で提案するアルゴリズムは，入力

悟

ZhanPing

データの絶対値の最大値を M とするとき，全体で O(V3

ユークリッド空間における与えられた有限個の点の凸EO.51og (VM)) の計算時間を必要とする.この計算時間

包中の最小ノルム点を見出す問題に対して i つの双対算は反復あたり O(V3) の計算を高々 O(EO ・ 51o g (VM))

法を提案する.本算法では，分離支持越平面i を繰り返し

ここで V 謡 E 孟 V2 かっ回転させて，有限回のステップで最遠支持越平面を見出L=O(Elog(M)) であるので，提案するアルゴリズムのす.多面体中の求めるべき最小ノルム点はこの最遠支持計算時間は単純に線形計画問題の内点アルコリスムを最趨平面中の最小ノルム点である.算法実行中に支持超平小費用流問題に適用した場合と比較しでかなり小さい.

面の原点からの距離は単調に増加する.与えられた多面最小費用流問題を多項式時間で解く方法として，体の中でノルムが減少する点列を見出す P. Wolfe の主

Edmonds と Karp の方法がよく知られている.その解算法と本双対算法は密接に関係している.本算法の振舞

法の計算時間は ， O(Elog(M) (E+Vlog (V)))であを調べるために計算機実験の結果も示す.

回繰り返すことから求められるる.したがって ，E=O(V2) のときは，内点法による解法の計算時間とほぼ等しい.このことから，内点法による計算時間は， Edmonds と Karp の方法と比べて遜色ないといえる.

物国際数学者会議への外国人参加者・旅貸滞在費援助募集のお知らせ
標記の件について関心のある方は，学会事務局ま移動費用を考慮した探索ゲーム
M 山大学菊岡健作

でお間合わせください.特に締切りはありませんが，先着順審査決定のため6 月までで予算割当は終 fする模様.

i些難漁船等の探索の場合，たとえば連絡がとだえた地
1990 年 6 月号

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

(55)375