ジョブ ショップ スケジューリングのジョンソン アルゴリズムは、2 台のマシンと N 個のジョブのケースを解決します。
ジョブ Pi には、期間 Pi1、Pi2 の 2 つの操作があり、マシン M1、M2 でこの順序で実行されます。
Step 1. List A = { 1, 2, …, N }, List L1 = {}, List L2 = {}.
Step 2. From all available operation durations, pick the minimum.
If the minimum belongs to Pk1,
Remove K from list A; Add K to end of List L1.
If minimum belongs to Pk2,
Remove K from list A; Add K to beginning of List L2.
Step 3. Repeat Step 2 until List A is empty.
Step 4. Join List L1, List L2. This is the optimum sequence.
これが「最適な」答えを与える理由がわかりません。ここにウィキペディアのリンクがあります
これは反例だと思います：
ジョブ セット:
(2,3);(4,5);(6,7)
アルゴリズムが与える最終的な答えは、マシン 1 では J1,J2,J3(2,4,6) ですが、マシン 2 は常にアイドル状態のままです。代わりに、マシン 1 で J1、J2 をスケジュールし、マシン 2 で J3 をスケジュールした場合は、もっと早く実行できたはずです。
誰が私が間違っているのか説明できますか?