====== ジョブショップスケジューリング ======
==== job-shop scheduling ====

{{tag>..c19}}

　各ジョブが固有の機械処理順序を持つシステム，すなわち[[|ジョブショップ]]において，ジョブの各機械における処理順序と，開始時刻，終了時刻を決定すること．//N//個のジョブを//M//台の機械で処理する場合のジョブショップスケジューリングにおいて，前提条件として，時刻0で//N//個のジョブがそろっているものとし，ジョブを処理するために必要な機械順序，処理時間，および納期は既知とする．このとき，各//M//台の機械でのジョブの処理順序は//N//!通りあり，したがって最大(//N//!)<sup>//M//</sup>通りの可能な処理順序が考えられる．例えば10ジョブ，5機械の場合，6.3×10<sup>3</sup><sup>2</sup>通りの処理順序がある．これらをスケジューリング評価基準であるメイクスパン最小化，納期遅れジョブ数や平均納期遅れ時間最小化，あるいは平均滞留時間最小化などから最適解を選択することは，該当するジョブの処理順序数がばく大になるため非常に困難とされている．したがって，これまで数多くの研究があるにもかかわらず，この問題に対する有効な解法は提案されていない．むしろ，実際には，ディスパッチング規則や人間の経験的知識などの簡単なヒューリスティックスが用いられている．近年，[[19:1005980|ジョブショップ形生産]]における多数の処理順序の存在と複雑性にこたえる解法として，AI（人工知能）を用いたスケジューリング方法が開発されている．


~~NOCACHE~~