フラット予約最適化システム

Question

私は予約システムを持っており、予約を最適化するスクリプトを書く必要があります。

すると、顧客のブックフラット、システムは、利用可能な最初のフラットを割り当てます。問題は、いくつかの予約の後、私の "グリッド"が断片化するということです。

グリッド例：実際に

Grid example

私は予約の最大数を受け入れることができるように、ホワイトスペースを最小化する必要があります。 私の質問には次のようなものがあります。私はいくつかのナップザックの問題のバリエーションを考えていました。 必要に応じてさらに情報を提供できます。

ありがとうございました。

Answer 1

これはスケジューリングの問題です。 1つの非常に重要な質問は、予約が行われた後、別の番号にフラットを再割り当てすることができますか？

• 答えがイエスであれば、あなたがあれば解決策を見つけるだろうし、あなたがフラットを持っているよりも多くの予約で何日を持っていない場合のみ：単に非常に最初の日d1の最初の空きスロットを取り、もしそこに将来の予約と競合しています。最初の未使用スロットを最初のd2（d2> d1に注意してください）とし、将来の予約を再割り当てしてください。アルゴリズムは収束します。再配分。

• 答えがノーであるならば、我々はあなたのアルゴリズムは将来の予約がどうなるかを推測することがあるトリッキーな世界に入って来ます。良いheurisicは、私が考えると、プレースメントに得点することです。たとえば、予約の前後に残っているイドルスロットの数を確認し、できるだけ空のスロットを残すオプションを選択することができます。