下限がゼロでない、または容量が0のフローグラフ
質問のタイトルが十分に正確ではないのではないかと思いますが、もっと正確なものを思い付くことができませんでした
ここに問題があります
与えられた「n」マシン
- 各マシンには一連の機能があります
- 各マシンには最大の可用性があります（A（m））
与えられた「m」タスク
- 各タスクには一連の機能が必要です
- 各タスクには一定の時間がかかります（D（t））
- タスクは1台のマシンでのみ実行する必要があります
問題は、すべてのタスクを完了できるかどうかを判断することです。
「1台のマシンのみ」の要件で行き詰まります。私が思いつくことができる唯一のフローグラフは、タスクが複数のマシンにリンクされていないことを保証するものではありません。
これは一種の2部マッチングの問題ですが、容量が1を超えています
また、フローネットワークでXORのような動作に遭遇しました。これは似ていますが、ターゲット側で必要になる「ソース」側に「xor」要件があります。
誰かが何かヒントがありますか？これをフローグラフとしてモデル化することは可能ですか？
Tx！
ピーター
PSより具体的な例で要件を明確にしようとしています
デジタル印刷システムと印刷ジョブを想定する
- 各デジタル印刷機は数時間稼働できます
- 各プレスにはいくつかの仕上げの可能性があります：例えば、「シートカッター」、「ラミネート」、「レーザーカッター」、「ページ折り畳み」、...。
- 各印刷ジョブには数時間かかります
- 各印刷ジョブには、1つ以上の仕上げの可能性が必要です
一連のマシンが与えられた場合、それぞれの可用性と仕上げの可能性、および一連の印刷ジョブ（期間、必要な仕上げオプション）によって、すべての印刷ジョブを終了できるかどうかが決まります。
だから例えば
- プリンタp1は10時間使用可能で、機能f1とf2があります。
- プリンタp2は10時間使用可能で、機能f2およびf3があります。
- 機能f1とf2を必要とするJob1の実行には8時間かかります
- Job2、機能f2とf3を必要とする実行には8時間かかります
- Job3、機能f2が必要な場合、実行には4時間かかります
たとえば10時間使用可能なプリンターは、10 x1時間のジョブまたは5x 2時間のジョブ、または1 x8時間のジョブと1x2時間のジョブを実行できます...ジョブは常に単一のプリンターで実行する必要があります
私が思いつくことができたフロー図は、常に次のような場合になります。
8時間のp1がjob1に割り当てられます（プリンターp1に2時間を残します）8時間のp2がjob2に割り当てられます（プリンターp2に2時間を残します）
（ここまでは順調ですね）
しかしその後
残りの2時間のp1とp2はjob3へのフローに使用され、最大フローは3つのジョブを実行できることを示しているようです（これは問題ありません）。
回答
あなたの問題はNP困難です。ジョブが特定の機能を必要とせず、すべてのプリンターの可用性が同じである特殊なケースでは、これはビンパッキング問題になり、（強力に）NP完全です。
あなたはあなたの状況にビンパッキングのための標準的なアルゴリズムを適応させることを試みることができます。たとえば、1つのアプローチは、整数線形計画法を使用し、ILPソルバーが結果の問題インスタンスを処理できることを期待することです。