可変な機械スピードをもつ二機械オープン・ショップスケジューリング問題

概要

論文の詳細を見る
従来のスケジューリング問題においては、機械スピードは一定であるとしていた。ここでは、機械スピードが可変であるとする一般化問題を考える。通常の二機械オープン・ショップ問題は以下の如くである。2台の機械A、Bとこれらの機械で処理されるべきn個の仕事がある。各仕事は、一方がAで、他方がBで処理されねばならない2つの操作から成る。すべての仕事はオープン・ショップ型、すなわち2つの操作の処理順序は自由でどちらの機械2操作から処理してもよいが、同時には同じ仕事の2つの操作を処理できない。又、各機械は高々1つの仕事しか同時には処理できない。分割処理は許されない。以上の通常の二機械オープン・ショップ問題に対する設定に加えて、機械A、Bのスピードが可変であるとする。目的は、最大完了時間及び機械スピードで表わされるコストを最小にする最適機械スピード及び最適スケジュールを求める事である。上記の一般化された二機械オープン・ショップ問題に対して、O(nlogn)のアルゴリズムを与える。
社団法人日本オペレーションズ・リサーチ学会の論文