私には次のシナリオがあります（長さについての予備的な謝罪ですが、できるだけ説明的にしたかったです）：
特定のタスクを完了するために、提示された順序で実行する必要のある「レシピ」（Ri）のリストが表示されます。各レシピは、それを完了するために必要なパーツ（Pj）のリストで構成されています。レシピには通常、最大3つまたは4つのパーツが必要ですが、最大16のパーツが必要になる場合があります。レシピリストの例は次のようになります。
- R1 = {P1}
- R2 = {P4}
- R3 = {P2、P3、P4}
- R4 = {P1、P4}
- R5 = {P1、P2、P2}//特定のパーツが複数必要になる場合があることに注意してください。（ここ、P2）
- R6 = {P2、P3}
- R7 = {P3、P3}
- R8 ={P1}//レシピがリスト内で繰り返される場合があることに注意してください。（R1と同じ）
最長のリストは数百のレシピで構成されている場合がありますが、通常、一部のレシピの繰り返しが多数含まれているため、同一のレシピを削除すると、通常、リストは50未満の一意のレシピになります。
私はマシンのバンク（Mk）を持っており、それぞれが利用可能なタイプのパーツの一部（またはすべて）を生成するように事前にプログラムされています（これはリスト処理が開始される前に1回行われます）。
フルフィルメントプロセスの反復は、次のように発生します。
- リスト内の次のレシピは、マシンのバンクに提示されます。
- 各マシンで、このレシピに必要なパーツの1つを作成するために、使用可能なプログラムの1つが選択されます。このレシピに必要ない場合は、「オフライン」に設定されます。
- 「クランク」が回され、各マシン（「オフライン」になっていない）が1つのパーツを吐き出します。
- クランクを1回転させることでできた部品を組み合わせることで、レシピが完成します。順序は関係ありません。たとえば、レシピ{P1、P2、P3}を実行することは、レシピ{P1、P3、P2}を実行することと同じです。
機械は瞬時に並行して稼働し、原材料は無制限であるため、リソースや時間/スケジュールの制約はありません。マシンバンクのサイズkは、少なくとも最長のレシピの要素数と等しくなければならず、したがって、上記のレシピの長さとほぼ同じ範囲（通常は3〜4、場合によっては最大16）になります。したがって、上記の例では、k = 3（R3とR5のサイズによって決定される）が妥当な選択のようです。
当面の問題は、銀行が特定のリストのすべてのレシピを実行できるように、マシンを事前にプログラムする方法です。マシンバンクはメモリの共通プールを共有するため、合計メモリ負荷の量を最小限に抑えるために、マシン間の冗長性を（完全に、または可能な限り）排除するプログラミング構成を生成するアルゴリズムを探しています。マシンバンクのサイズkは柔軟性があります。つまり、特定のリスト内の最長レシピの長さを超えてマシンの数を増やすと、リストのより最適なソリューションが生成される場合（ただし、16のハード制限を維持する場合）は問題ありません。
今のところ、これは単一コストの問題であると考えています。つまり、各プログラムは同じ量のメモリを必要としますが、将来的にはプログラムごとの均等化を柔軟に追加したいと考えています。上記の例では、すべてのレシピを考慮すると、P1は最大1回、P2は最大2回（R5）、P3は最大2回（R7）、P4は最大1回発生するため、理想的にはこれに一致する構成-P1を生成するように構成された1台のマシン、P2を生成するように構成された2台のマシン、P3を生成するように構成された2台のマシン、およびP4を生成するように構成された1台のマシンのみ。マシンバンクサイズk=3を使用した、上記の例で考えられる最小構成の1つは、次のとおりです。
- M1は、P1またはP3のいずれかを生成するようにプログラムされています
- M2は、P2またはP3のいずれかを生成するようにプログラムされています
- M3は、P2またはP4のいずれかを生成するようにプログラムされています
ここにはジョブショップタイプの制約がないので、私の直感では、これは集合被覆問題に還元されるはずだと教えてくれます。これは、デジタルシステムの設計で見られる最小限の集合被覆問題のようなものです。しかし、これらのアルゴリズムに関する私の（確かに限られた）知識をこのシナリオに適応させることはできないようです。誰かがこのアプローチの実現可能性を確認または否定できますか？どちらの場合でも、いくつかの有用なアルゴリズムに私を向けることができますか？BerkeleyのEspressoのように事前にパッケージ化されたものではなく、既存のコードのチャンクに統合できるものを探しています。
ありがとう！