GT型フロー・ショップにおける直・並列先行関係制約下の最適スケジュール

概要

論文の詳細を見る
二機械フロー・ショップにおける次のような問題を解く。仕事はいくつかのグループに分類されており、各グループの仕事は連続して処理される必要がある。各グループの最初の仕事に着手する前に、第一、第二の機械にグループ特有の準備が必要である。各仕事には第一と第二の機械の間の加工遅れが指定されても良い。また、各グループの問には、直・並列ネットワークにより表現される先行関係が指定されている。この時、総所要時間を最小にする集合問、並びに、集合内のスケジュール(順列)を求めよ。最初に、従来とは多少異なる方法で合成仕事を定義すれば、上の問題で先行関係制約を無視した場合には、集合間、集合内の両スケジュールは一般化したJohnson規則により最適に定められることを示す。ここで "一般化" とは負の処理時間を形式的に許容することである。次に、負の処理時間を許容した、一般化した仕事に対する合成仕事を定義し、これが通常の非負の処理時間を有する仕事の合成仕事と全く同じ特性を持つことを示す。このことを利用して、Sidneyの古典的な二機械フロー・ショップ問題に関する理論をほぼそっくり、上述の問題にも適用できることを明らかにし、直・並列アルゴリズムによってO(n 1og n)、n:仕事の個数、で最適スケジュールを定めうることを指摘する。本稿で扱った問題は、二機械フロー・ショップで総所要時間を最小化する問題の、多くの研究者によって調べられた様々な変種をその特殊化として含むが、さらに、各仕事も処理時間とは独立の段取持問を有し、グループ内の仕事間にも直・並列先行関係が指定される場合をも、内包していることが指摘される。
社団法人日本オペレーションズ・リサーチ学会の論文
1983-09-00

著者

関口恭毅
北海道大学

GT型フロー・ショップにおける直・並列先行関係制約下の最適スケジュール

スポンサーリンク

概要

著者

関連論文

スポンサーリンク