ジョンソン法を用いたフローショップスケジューリング問題

一つの工程ライン上に複数の作業があり、各作業は一連の工程を経なければならないライン作業スケジューリング問題では、作業の完了時間を最短にする方法を見つけることが目的となる。

ジョンソン法とは、フローショップ・スケジューリング問題を解くために広く利用される手法で、フローショップ・スケジューリング問題を2マシンのスケジューリング問題に帰着させることができる。その具体的な手順は以下のとおりである。

1. 各工程の処理時間を小さい順に並べ替えると、並べ替え後の工程順序がわかります。
2. マシン1とマシン2のそれぞれを代表する空のジョブシーケンスを2つ作成する
3. ソートされたジョブの順番から処理時間が最小のジョブを選び、機械1に割り当てる。
4. 処理時間が最も短いジョブを並べ替えたジョブシーケンスから1つ選んで、それを機械2に割り当てます。
5. 3番目と4番目の手順がすべての作業が割り当てられるまで繰り返す。
6. 1号機の作业順序と2号機の作业順序を統合して、最終的な作业スケジュール順序を求める。

ジョンソン法のメリットは、単純で分かりやすく、場合によっては最適解が得られることです。ただし、適用できるのは2台の機械の場合のみという制約があり、複数の機械の場合は他のアルゴリズムを使用する必要があります。また、ジョンソン法ではすべてのケースで最適解が得られるとは限りません。