古いシステムを使用して行われる仕事が n 件あります。それらを新しいシステムに変更すると、その仕事に対して双方向の利益が得られます。一部のジョブ ペア (i,j) には依存関係があります。ジョブを変更するが、その従属ペアを変更しない場合、xij のコストがかかります。ジョブ 1 は、新しいシステムでは実行できません。メリットを最大化するために、新しいシステムに変更するのに理想的な一連のジョブは何ですか (もちろんジョブ 1 を除く)。
これは私自身の言葉で言い換えたアルゴリズムの問題です。何らかの形の最大フローまたは循環に削減されるはずです。コストが新しいシステムに変更される他のジョブに依存しているという事実により、アプローチを思いつくのに非常に苦労しています（静的な値を最大フローグラフの設定に関連付けて、有効なソリューションを持っているようには見えません）。私はこれについてしばらく考えてきましたが、まだ適切なアプローチを見つけるのに苦労しています. この問題に対処する方法についての提案は大歓迎です!