問題タブ [assignment-problem]

問題設定

現在、フードテック スタートアップ (電子食料品店) の派遣問題に取り組んでいます。私たちには仕事（配達される注文）と労働者（宅配業者/梱包業者/ユニバーサル）があります。問題は、注文を労働者に効率的に割り当てることです。最初のステップでは、CTE (クリックして食べる - 注文してから配達までの時間) を最適化することにしました。

問題そのもの

問題は、単一のエグゼキューターではなく、1 つのジョブにつき 2 人のワーカーを持つことが効率的であるという事実から生じます。なぜなら、パッカーは店舗の「マップ」を知っている可能性があり、宅配業者は自転車を持っている可能性があるため、それぞれを個別に比較した場合でもジョブをより速く実行できるからです。注文転送費用の会計。

アルゴリズムを調査したところ、私たちの問題は割り当て問題のように見え、アルゴリズムによる解決策 (ハンガリーのアルゴリズム) があることがわかりましたが、問題は、古典的な問題では、「各ジョブが 1 つのワーカーに割り当てられ、各ワーカーに 1 つのジョブが割り当てられる」必要があることです。私たちの場合、1 つのジョブに 2 人のワーカーを配置すると効率的な場合があります。

これまでに試したこと

1. (パッカー A +ユニバーサル B ) の組み合わせをコストのマトリックスに挿入しますが、この場合、ユニバーサル B をマトリックスに追加することは できません。パッカーAとの組み合わせの一部として）

2. その結果、2 つのハンガリー語アルゴリズムを実装します。最初にパッケージを割り当て、次に配送を割り当てます。これはほとんどの場合に機能しますが、非効率的なソリューションにつながることもあります。必要に応じて、例を追加します。

質問自体

私はたくさんグーグルで検索しましたが、問題の解決策を教えてくれるものは何も見つかりませんでした。解決の手がかりとして使用できるリンクやアイデアがあれば、喜んでチェックさせていただきます。

編集:私の質問のブルート フォース ソリューションを追加しました。問題をよりよく理解するのに役立つことを願っています

私は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 です。

これは、すべてのフライト (ジョブ) を作成するための乗組員の最小数を見つける問題と見なすことができます。