隣接2ジョブ交換法による平均滞留時間スケジューリング問題の解

概要

論文の詳細を見る
鍋島は、1973年にジョブ数・機械台数が任意のフロー・ショップ・スケジューリング問題で、最大滞留時間を最小にする十分条件式を導出した。また、得られた十分条件式に基づいて近似アルゴリズムを提案し、ある種の近似率を用いてそのアルゴリズムの有効性を検証した。しかし、鍋島と同様の問題で、平均滞留時間を最小にする解析は行われていない。平均滞留時間は、各ジョブの加工完了時刻の平均値であり、仕掛在庫量と密接に関係する評価尺度である。平均滞留時間に罵する研究には、Panwalkarらや、Guptaなどの研究がある。前者は、最適解を求めることのできる特殊な条件をもつ問題を取り扱っているだけで、一般の問題に適用できるアルゴリズムは提出していない。後者は、いわゆる発見的解法であり、解析的な取り扱いによる解を与えてい広い。そこで本研究では、ジョブ数・機械台数が任意の追抜禁止フロー・ショップ・スケジューリング問題を取りあげ、平均滞留時間を最小にする十分条件式を導出する。得られた十分条件式に基づいて、最適解または準最適解を得るためのアルゴリズムを提案する。用いる手法は、Johnson、鍋島なども使用している隣接2ジョブ交換法である。この手法は、隣接する2ジョブの先行関係を決定する推移性をもつ条件式を導き、それに基づくアルゴリズムを得ようとするものである。さらに、求めた解の質を評価するために、新しい近似率の定義式を導入する。従来使用されていた近似率は、単に最適解と近似解の値の比率で求めていた。したがって。近似解が最悪解と一致した場合でも、ある程度高い近似率が得られるなどの不合理な点もあった。そこで、可能解の範囲(最適解と最悪解の巾)を考慮した近似率を新しく定義して使用する。この近似率は、求めた解が最適解と一致すれば100%、最悪解と一致すれば0%の値になる。得られた十分条件式は、加工時間の値だけからなる不等式群で構成され、その総数は機械台数の2剰にほぽ等しい。すべての不等式は、ジョブに関する推移性を満足するので、数ステップからなる比較的簡単次近似アルゴリズムが提案できる。提案したアルゴリズムを用いて約100種の例題を解いた結果、平均90%の近似率をもつ解が得られた。ジョブ数、機械台数、加工時間のばらつきなどは、調査した範囲では近似率に影響を与えなかった。このアルゴリズムは、簡単恋記入用紙による手計算でも遂行できる。解を得るまでに必要な時間は、ジョブ数×(機械台数)^2にほぼ比例する。たとえば、ジョブ数5、機械台数5の問題では、手計算で12〜13分、コンピュータで0、16秒の所要時間である。フロー・ショップ問題は、機械台数がジョブの工程数に等しいため、機械台数の増加には生産技術的に一定の限界が存在する。また本アルゴリズムの計算時間は、かなり多くなる可能性のあるジョブ数には、単なる一次の比例関係にとどまっている。以上の結果より、提案したアルゴリズムは、実用上効果を発揮すると思われる。
社団法人日本オペレーションズ・リサーチ学会の論文

隣接2ジョブ交換法による平均滞留時間スケジューリング問題の解

スポンサーリンク

概要

著者

関連論文

スポンサーリンク