私はNさまざまな仕事をしています。一部のジョブは連続して実行できます。
ジョブシーケンスの数が最小になるように、連続したジョブを並べてジョブシーケンスを形成する必要がMあります。
問題は、最大カーディナリティ マッチングの形式です。
しかし、Maximum cardinality マッチングの場合、ジョブ シーケンスの数が最小になることは確かですか?
それを解くアルゴリズムを探しています。
例
N=6
次のジョブをフォローできます。
その後、ジョブ 1 はジョブ 2、5 に進むことができます。
その後、ジョブ 2 はジョブ 3 に進むことができます。
その後、ジョブ 4 はジョブ 2、5 に進むことができます。
その後、ジョブ 5 はジョブ 6 に進むことができます。
ジョブの割り当てを実行すると、次の 2 つのジョブ シーケンスが得られます。
1-2-3
4-5-6
その場合、M=2 です。
これは、すべてのフライト (ジョブ) を作成するための乗組員の最小数を見つける問題と見なすことができます。