~1111111 1I 1111111111111111111111111111111111111111111111111111111111111111111111 “ 1111 “ 111111 ・ 1111111111111111111111111111111111111 “ 11111111111111""1111 “"“ 1111111111111111111111 “ 1111111111“ 1111“"“・ UUUIUIIIL

ii

論文誌掲載論文概要

;

JORSJ

Vo
l.34, No.l';1111111'111111111111111111111111111111111111111111111111111111“ 1111111U- lllll lI IIIIIIIIIIIIIIIIIIUJIIIIIIII'U “ 1111 “ IUIIIIIIIIIIII'"lllllllflllllllllllllllllllllllllllllllllllllllllllll11111111111111111111111111111;

在庫保管能力制約付確定的多品種在庫シス(a):aE ‑(v)} のある比率で抑えられるような最大整テムのヒューリスティック解法

数フロー f' を求める問題を考える.ただし ，点集合 ，NationolTsingHuaUniversity

Maw‑ShengChem
Kao‑Ch麩gLin
Chin‑ChernChen
本論文では，各品種に独自の発注間隔を設定することが可能であり，また，全品種を合計した在庫水準の最大値を低減させるために品種ごとに発注をずらすことが可能な，在庫保管能力に制限がある m 品種 (m~3) 在庫シ

VはN のò-(v) は v に入ってくる Nの校の集合とする.

この論文では，問題( IVBP) が NP-完全であることを証明することによってこの問題が難しい問題であることを示し，問題 (1 VBP) に対する多項式近似アルゴリズムを提案する.

総滞留時間最小化のフローショップ・スケ
ジューリング解法

ステムを考える.このようなシステムに対して，発注をIndianInstituteofTechnology

ChandrasekharanRa
iendranDi
pakChaudhuri

ずらす時間や発注間隔を考慮して，単位時間当たりの総コストを最小化する各品種の最適発注量を求めるのが研究の目的である.本論文では，この問題を非線形整数計

本論文では，各ジョブの完了時刻の合計，すなわち，画問題として定式化し，本問題の最適解を導出することジョブの総滞留時間の最小化を目的とするフローショッがきわめて難しいことを示した後，ヒューリスティッグ

プ・スケジューリング問題に対するヒューリスティッグ解法を提案し，さまざまな計算例をもとに，この解法が解法を提案する.提案するアルゴリズムでは，ショップラグランジュ乗数法や固定ザイクル法に較べて優れた方のさまざまなステージにおけるジョブの完了時刻の下界法であることを示した.

値が重要な役割を果たす.この下界値は，ショップの一最大点整数平衡フロー問題に対する NP-完全性と近似アルゴリズム部あるいはすべてのステージでジョプの待ちが許きれない場合にも成立する下界値であるので，提案するヒューリスティック解法は，このように，ジョブ待ちが許され福島大学中山

明ないフローショップにおいても適用可能である.各種フMinoux は 2 端子ネットワーク上の最大平衡フロー問

ローショップを想定した計算実験をもとに，このヒュー題を考察した.この問題は，ネットワークの各校の流量リスティック解法の性能を評価し，その結果，本研究でf(a)(aEA) が全流量のある比率で抑えられるような最提案する解法が安定して良好な結果を生み，既存のフロ大フロー f を見つける問題である.ただし ，ーショップ・スケジューリング解法に較べて良い結果を

A はネットワークの校集合，全流量とはネットワータのソースからシンクまでの流量の合計とする.

彼は，さらに最大整数平衡フロー問題も考察し，アルゴリズムの提案をした.なお，最大整数平衡フローとは2 端子ネットワー生むことを示した.

固定在庫費用がある場合の (8， S) 政策についてクの各校の流量が整数となる最大平衡フローのことであ名古屋工業大学石垣智徳

る. Minou互による整数平衡フローという概念は，ネッ

南山大学滞木勝茂

トワークのフローを平衡にするという 1 つの手法とみなすことができる.この論文では

本論文では有限期間の下で単一製品の需要が確率的で2 端子ネットワーク Nある動的在庫モデルにおいてい ， S) 政策が最適となる条上の最大整数“点平衡"フロー問題 (1 V BP) ，すなわ

件を厳密に展開する.われわれのモデルの特徴は，従来

ち ， N の各点 VEV に対して ， V に入ってくる任意の技の発注費用，品切れ費用，在庫費用という 3 種類の線形

流量 f' (a) (aEò-(v)) が u に入ってくる全流量I: {f'

費用にすべて固定費用を加えた費用構造を有しているこ

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

オベレーショシズ・リ+ーチ

とである.

このモデルはAneja ，Y. and Noori ,ようなシステムに対して，地点毎の分散管理と中央管理H.A. の拡張された形になっており，このような費用構の 2 種類の管理方式を考える.分散管理方式では，各地造の下では一般に (s ， S) 政策は最適とならない.われわ

点がそれぞれの在庫を持ち，地点聞の融通，すなわち，れはいかなる場合に (s， S) 政策が最適となるかを単一期在庫に余裕がある地点から品切れを起こしている地点へ

間モデル，多期間モデルの I1慎で一般的に考察し，さらにの供給を許さない.したがって，分散管理方式における例として需要密度関数を特定化したとき ，期待総費用は，各地点の期待費用の合計である.

(s ， S) 政策が最適になる条件のより詳細な分析を行なう.

一方，中央管理方式は，在庫に余裕のある地点から不ここで得られた結論は，従来のモデルの拡張になっているばかりでなく，Aneja , Y. and Noori , H.A. とは異なる方法で (s ， S) 政策の最適性に関する証明を与えている.

Aneja , Y. and Noori , H.A. で、は，多期間モデルの (s ， S) 政策が最適となる条件は，単一期間モデノL足している地点へのものの転送を許すシステムである.

この場合，在庫保管費および品切れ費は，転送後の最終在庫量，または，最終不足量をもとに評価するものとし，総期待費用は，期待在庫保管費，期待品切れ費，および，在庫の転送に伴う期待輸送費の合計とする.のそれよりもきつい条件が必要であった.われわれの証

本論文では，各地点の需要確率分布の形にかかわら

明法によれば K-convex 関数の一般的性質を使用するず，これらのシステムが満足する 2 つの性質を示し，こことによって，単一期間モデルと多期間モデルの (s ， S)れをもとに中央管理方式の効果を明らかにする.

政策の最適性に関する証明が同ーの条件の下で可能であることを示す.

制限式サービス規律をもっ集団到着巡回多重待ち行列の解析

区間係数を有する多目的線形計画問題に対

横浜国立大学馬場裕

する非支配解の概念
大阪府立大学乾ロ雅弘

久米靖文
本研究では，区関係数を有する多目的線形計画問題に対する解の概念として

4 つの非支配解を提案する.まず，目的空間上の支配関係を定義し，これを用いて決定空間上の支配関係を構成する.このさい，目的関数が点対集合写像であることから，可能，必然などの様相概念を導入する.得られた決定空間上の支配関係の性質を調べ

4 つの非支配解を定義する.次に4 つの非支配解の性質を調べ，各非支配解が各非支配端点の凸結合で表わされることを示す.

また，

Bitran により提案されている 2 つの有効解が4 つの非支配解に含まれていることを示す.

本論文では制限式サービス規律をもっ集団到着巡回多重待ち行列について解析する.巡回多重待ち行列は計算機システムや通信システムの性能評価における基本モテ'ノレであり，客がし、なくなるまでサーピスを行なう全処理式，サーバが到着した時点ですでに待ち行列に到着した客だけサーピスするゲート式，などの処理方式がある.
全処理制限式 (E-limited) は待ち行列 i を訪れるとき，h 人の客をサービスするかまたは客が L 、なくなるまでサーピスを行なう.ゲート制限式 (G-limited) はサーパが待ち行列 i を訪れたとき ， li 人の客が L 、れば min (lj ， kil
人のサービスを行なう.

本論文では，到着分布が集団ポアソンの場合には，E-limited と G-limited の 2 つの制限式サーピス規律について，各待ち行列における平均待ち時間の重み付き多地点新聞売り子問題の期待費用に対する和に関する等式を導く.対称形の場合には，これらの等中央管理方式の効果

式から得られるタイトな不等式を用いることによって，NationalChiao‑TungUniversity
Pao‑LongChang
Chin‑TsaiLin
本論文では，複雑の独立な需要源を有する単一期間，各待ち行列における平均待ち時間の上限が得られる.さらに集団の到着分布が一般分布の場合には，各待ち行列における平均待ち時間の重み付き和に関する近似式を導く.対称形の場合には，この近似式は全処理式，ゲート単一品目在庫問題を考え，複数の地点から成る問題に対式，して中央集中管理を行なうことのメリットを分析する.

似式となる.数値例において，対称形待ち行列について

E-limited ,G-limited における平均待ち時間の近各地点における在庫保管費および品切れ費は，線形関数シミュレーションや拡散近似の結果と比較し，平均待ちを構成し，地点によらずに共通であるものとする.この時間の上限や近似式の有効性を確かめる.

1991 年 7 月号

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

(89)377