処理順序に制約のある1台の機械の順序づけ問題
スポンサーリンク
概要
- 論文の詳細を見る
一台の機械とこの機械で処理されるn個の仕事1、2、…、nからなる順序づけ問題を考える。各仕事iには処理時間P_i(>0)と重みw_i(>0)が対応しているものとする。又、n個の仕事はいくつかのグル一プに分けられており、各グル一プの内部では処理順序は予め定まっており、一旦一つのグル一プに含まれる最初の仕事の処理を開始するとそのグル一プに含まれるすべての仕事の処理をこの定まった順序にしたがって完了するまで、他のグル一プに含まれる仕事の処理は開始できないものとする。さらに、あるグル一プの仕事は他のグループの仕事より先に処理しなければならないという形でグループ間の半順序が与えられており、グループの処理順序はこの半順序を溝足しなければならないものとする。このような関係は各グル一プをnodeとし先行関係をarrowとする1つのグラフで表わすことができる。叉、1つの処理順序による全費用をその処理順序による各仕事の完了時間にその仕事の重みをかけたものの和と定義する。我々の問題は、処理順序が満たすべきグラフが与えられた時、これを満足する範囲で全費用を最小にする処理順序を求めることである。この問題に対しては既に多くの研究者による研究があり、先行関係が特別な構造を持つ場合の考察がいろいろなされている。特にSidneyは各グル一プが1つの仕事からなっている時を考察し、あるアルゴリズムを提案し、このアルゴリズムによって最適な処理順序が得られることを示している。本論文ではSidneyの与えたアルゴリズムは効率がよくなく、又、解を与えない場合があることを例をもって示し、更に新しいアルゴリズムを与え、これによって最適な処理順序が一般の先行関係に対して求まることを示した。このアルゴリズムの特色はw_iとp_iとの関係により次々に新しいグループを作っていき、それに伴なって先行関係を表わすグラフを次々に作り変えていくことである。最後に、このアルゴリズムによって最適解を求める例を示してある。
- 社団法人日本オペレーションズ・リサーチ学会の論文