特許

J-GLOBAL ID：200903071427947289

ジョブスケジューリング方法および装置

発明者： 柴崎 真人
出願人/特許権者： 株式会社日立製作所
代理人 (1件)： 有近 紳志郎
公報種別：公開公報
出願番号（国際出願番号）：特願平5-168844
公開番号（公開出願番号）：特開平7-028890
出願日： 1993年07月08日
公開日（公表日）： 1995年01月31日
要約：

【要約】【目的】 フローショップ型の生産ラインにおけるジョブスケジューリングで、スケジュール選択基準を満足するスケジュールが存在するなら、それを効率的に必ず見つけることができるスケジューリング方法および装置を提供する。【構成】 探索の途中で、ジョブを選択する際の評価値として、部分順列でのスケジュールの評価関数の値の代わりに下界値を用い、その下界値がスケジュール選択基準を満足しない部分順列を枝切りする(62,63)。また、下界値が暫定解の評価関数値よりも大きい部分順列を枝切する(66,71)。さらに、探索途中で、次に順序づけるジョブを決定するときには、下界値とスケジュール選択基準値との差の最も大きいものを選ぶ(63)。【効果】 探索の途中で、ジョブを選択する際の評価値として、下界値を用いることにより、探索空間を効率的に狭め、探索空間を調べつくすことが可能となり、スケジュール選択基準を満足するスケジュールが存在するなら、それを効率的に必ず見つけることが出来る。

請求項（抜粋）：

フローショップ型の生産ラインにおけるジョブデータとスケジュール選択基準とを与えられ、そのスケジュール選択基準を満足するジョブの完全順列を探索するジョブスケジューリング方法であって、部分順列格納エリアをもつセルを1個以上有する部分順列管理表を設け、前記スケジュール選択基準を基に先頭のジョブの候補を探索して得た各々を部分順列として前記セルの前記部分順列格納エリアに個別に格納し、次に、前記部分順列格納エリアに格納されたジョブの部分順列を保存した上で生産ラインの制約を緩和した緩和問題を最適に解いて得た所定の評価関数値を下界値としその下界値が前記スケジュール選択基準を満足する場合のみ前記スケジュール選択基準を基に当該部分順列に続くジョブを探索して当該部分順列に付加して新たな部分順列としそれを前記セルの前記部分順列格納エリアに格納し、これを繰り返して1個以上の完全順列を探索することを特徴とするジョブスケジューリング方法。