私は大学の学生寮で RA として働いており、毎晩 2 人の RA がオンコールで待機する必要があります (事件や緊急事態に対応できる)。毎月、RA は (何らかの理由で) オンコールできない夜を提出します。男性と女性の両方のRAがいます。私は、次の要件を満たす特定の月のオンコールの夜の最適な配置を見つけるための効果的なアルゴリズムを考え出そうとしています:
- 彼または彼女が利用不可と記載した夜には RA が予定されていません。
- RA は、1 か月に指定された夜数を超えてオンコールすることはありません。
- 任意の 3 泊期間内に 2 回オンコールする RA はありません。
- 毎晩、正確に 2 名の RA が待機しています。
- 毎晩、可能であれば、男性 1 名と女性 1 名の RA が待機しています。
いくつかの調査を行った結果、これはリソースに制約のあるスケジューリングの問題であり、NP 完全と見なされることがわかりました。したがって、最適なソリューションを見つける必要はなく、機能するソリューションを見つける必要があります。
これまでのところ、次のアプローチを検討してきました。
- RA x nights の単純な 2 次元配列。各セルには、その RA がその夜に待機中かどうかを示すブール値が保持されます。RA を 2 つの優先キュー (男性 1 人、女性 1 人) に保持し、これまでの夜の泊数、最後のオンコールの夜からの経過時間でソートし、1 つの RA を選択して夜を繰り返すだけです。各キューから、特定の夜に誰も働けない行き止まりにぶつかった場合はバックトラックします。
- 一方が男性のRA、もう一方が女性のRA、最後が夜の三者グラフ。ソリューションでは、毎晩 1 人の男性と 1 人の女性の RA に優位性があります。すべてのエッジを接続して開始し、解決策が見つかるまでエッジを削除します。
- 上記の構造を使用したある種の遺伝的アプローチ。
どのようなアプローチを使用することをお勧めしますか? もっとうまくいくかもしれないと思っていなかったものはありますか？これは宿題ではありません。私は、自分のスタッフやキャンパス内の他のスタッフが簡単に日付の希望を送信し、誰にとっても有効なスケジュールを生成できるようにする Web サイトを開発しようとしています.