生産システムのスループットを改善しようとしています。システムの正確なタイプは関係ありません (私は思います)。
説明
- このシステムは、ステーションのLINE (番号 1、2、3...) とARMで構成されています。
- システムは、ランダムな時間にITEMを受け取ります。
- 各ITEMには、それに関連付けられたPLANがあります (たとえば、ITEM1には、ステーション 3、次に 1、次に 5 を通過する必要があるというPLANがある場合があります)。PLANには、 ITEMが各ステーションに留まる時間に関するタイミング情報(ハード最大/最小値の範囲) が含まれています。
- 各STATIONは、一度に 1 つのITEMを保持できます。
- ARMは、各ITEMを 1 つのSTATIONから次の STATION に移動するために使用されます。各PLANには、固定値であるARMのタイミング情報も含まれています。
現在の習慣
2 つの現在の (作業中の) 計画ソリューションがあります。
1 つ目は、各STATIONの使用状況のマスター リストを維持します。これを「予約」アプローチと考えてください。新しいITEM-Nが入力されるたびに、システムはPLAN-Nが適合する最も早いスロットを見つけるために前方を検索します 。したがって、たとえば、t = 0 で適合させようとし、適合が見つかるまで遅延を徐々に増やしていきます (実際には、処理時間を短縮するためのヒューリスティックがいくつかありますが、アプローチは有効です)。
2 つ目は、いつ開始するかを指定する各ITEMのリストを維持します。新しいITEM-Nが入ると、システムはそのPLAN-Nを既存のすべてのリスト と比較して、開始するのに適した時期を見つけます。繰り返しますが、t=0 で開始し、徐々に遅延を増やしていきます。
2 つのソリューションのどちらも、ITEMが各ステーションで許可される時間の範囲を利用していません。一定の時間が想定されます (中間点または最小値)。
理想的なソリューション
現在のITEMの一部が特定のSTATIONで費やす期間を変更した場合、その期間を短縮するかどうかに関係なく (新しいITEMが入ることができるように代わりにステーション）またはその期間を長くする（したがって、ARMはITEMを移動する時間があり ます）。
問題に遺伝的アルゴリズムのソリューションを実装しようとしています。現在の遺伝子には N 個の数字 (0 から 1 の間) が含まれています。ここで、N は現在システム内にあるすべてのアイテムと追加される新しいアイテムの合計ステーション数です。この遺伝子を実際の期間に変換するのは簡単です。 (0 は最小持続時間、1 は最大持続時間、その間を直線的にスケーリングします)。
ただし、この遺伝子表現は、互いに重複する使用できない計画を一貫して生成します。この理由は、複数の項目がすでに理想的に配置されている場合 (時間的に連続し、計画的に)、期間の変更は不可能だからです。アイテムがすでに処理されていると、遅延または前倒しできないため、これは避けられません。
上記の状況の例として、ITEMAがt1 から t2 および t3 から t4 の間STATION3にあるとします。その後、ITEMBが出現し、t2 から t3 の間、STATION3 を占有します (したがって、STATION3は t1 と t4 の間で完全に使用されます)。私の現在の遺伝子表現では、重複を生成しないように、遺伝子の特定の要素が正確に正しい値を持つ必要があるため、有効な解決策を見つけることは事実上保証されていません。
質問
- 上記よりも優れた遺伝子表現はありますか?
- 変更可能なタイミングを見つけるために、簡単な山登りをした方がよいでしょうか? それとも、GAは実際にこの問題に適していますか?