7

私にはそれぞれ試験を受けNなければならない人がいます。T各試験には「ある程度の」時間がかかります (例: 30 分) (早期に終了することはありません)。試験は、試験官の前で実施する必要があります。

私は各人が全体の時間内に試験官の前で各試験を受けるようにスケジュールする必要がありますが、昼休みを避け、最小数の試験官を最小限の時間使用します (つまり、アイドル状態の試験官がいない/最小)。

次の制限があります。

  • 人は一度に 2 つの場所にいることはできません
  • 1 人 1 人が各試験を 1 回受ける必要があります
  • 誰も同じ検査官によって二度検査されるべきではない

最適なソリューションはおそらく NP-Complete であり、遺伝的アルゴリズムを使用して最良の推定値を取得するのがおそらく最善であることを認識しています (これに似ていますか?座席計画ソフトウェアの推奨事項 (そのような獣は存在しますか?) )。

私は遺伝的アルゴリズムの仕組みに満足しています.私が苦労しているのは、パラメーターを遺伝的に操作できるようにプログラムで問題をモデル化する方法です..

各試験に同じ時間がかかった場合、時間をこれらの長さに分割し、時間枠と試験官のマトリックスを作成して、受験者をドロップします。ただし、各試験の時間は必ずしも同じ、私はこれにアプローチする方法について少し迷っています。

現在これをやっています：

  • すべての受験者と試験の間で、実施する必要があるすべての「テスト」のリストを作成します
  • テストがあるのと同じ数の試験官から始める
  • すべての試験官を繰り返しループします。それぞれの試験官について: (制限に基づいて) 試験官に適格な予定外の試験を見つけます。
  • スケジュール可能なすべてのテストが終了するまで続行します。
  • 予定外のテストがある場合は、試験官の数を増やして、もう一度開始します。

現在はかなり粗雑に感じられるため、これにアプローチする方法についてより良い提案を探しています。

4

5 に答える 5

1

julienaubertが提案したように、解決策 (これをscheduleと呼びます) は、関連するすべての学生とテストの組み合わせをカバーする一連のタプル (日付、学生、試験官、テスト) です (N 人の学生全員が T テストをすべて受けますか?)。私は、1 人の試験官が一度に複数の学生を試験する場合があることを理解しています。そうしないと、膨大な数の試験官が必要になります (学生ごとに少なくとも 1 人)。

次の場合、2 つのタプル A と B が競合します。

  • 生徒は同じ、テストは違う、期間が重なる
  • 試験官が同じ、試験が違う、期間が重複している
  • 学生はすでに別のテストで試験官と協力しています

タプルの競合は、スケジュールの競合とは異なることに注意してください (繰り返し検査者の問題を追加でチェックする必要があります)。

下限:

  • 試験官の数 E は >= 最も働き過ぎの学生のテストの総数でなければなりません
  • 合計時間は、最も過労状態の生徒のテストの合計時間より長くなければなりません。

シンプルで貪欲なスケジュールは、次の方法で作成できます。

  1. 最も働き過ぎの生徒を取り上げ、ランダムな順序でテストを割り当てます。それぞれ別の試験官が担当します。一部のビンパッキングを使用して、テストの順序を変更し、昼食時間を空けることができます。これは幸せな学生です。彼は可能な限り短い時間で終了します。
  2. 他の各生徒について、生徒がすでに予定されているテストを受ける必要がある場合は、時間、場所、および試験官を事前に予定されたテストと共有します。
  3. 最も過重労働の学生 (例: 予定外のテストの最大数) を取り、制約に違反しないようにタプルを割り当て、必要に応じて時間と試験官を追加します。
  4. 予定外のテストがある生徒がいる場合は、2 に進みます。

上記のステップ 2 で行った選択を改善することは、改善に不可欠です。この選択は、ヒューリスティック検索の基礎を形成できます。上記のアルゴリズムは、必要な試験官の数を最小限に抑えようとしますが、学生の時間を犠牲にします (学生は、早い段階で 1 つの試験を受け、その日の最後に別の試験を受けることになり、その間には何もない可能性があります)。ただし、法的な解決策が得られることは保証されています。さまざまな学生と一緒に実行すると、法的な答えに固執する GA の「開始」ソリューションを生成するために使用できます。

一般に、このような問題に対する「完璧な答え」はないと思います。考慮しなければならない要因が非常に多いためです。試験官の数を最小限に抑えたいと考えていますが、1 人の試験官がいる部屋に収容できる学生の数にも実際的な制限があります。また、スケジュールを「公平」にしたいと考えています。したがって、あなたが望むことができる最善の方法は、これらのノブをいじることができるようにし、結果 (合計時間、生徒ごとの幸福度、試験官ごとの幸福度、試験のサイズ、知覚される公平性) を把握し、ユーザーが調査できるようにすることです。パラメーター空間と情報に基づいた選択を行います。

于 2010-06-03T18:01:06.777 に答える
1

これには SAT ソルバーを使用することをお勧めします。問題はおそらく NP 困難ですが、優れた SAT ソルバーは多くの場合、数十万の変数を処理できます。2 つの例については、Chaff または MiniSat を確認してください。

于 2010-06-03T23:08:56.513 に答える
0

制約プログラミングを検討することもできます。Prolog を確認するか、論理プログラミングのより現代的な表現についてはPyKEを確認してください。

于 2010-06-03T22:41:46.023 に答える
0

ここでは、GA でモデル化する方法について説明します。

あなたの表記を使用して：

  • N (受験者数)
  • T (nr 試験)

個人の遺伝子が予約の完全なスケジュールを表現するようにしましょう。つまり、個人は特定の予約のリストです: (i,j,t,d)

  • i は i 番目の受験者です [1,N]
  • j は j 番目の審査官 [1,?]
  • t は、受験者が受けなければならない t 番目のテストです [1,T]
  • d は試験の開始日 (日付 + 時刻)

次のプロパティを持つフィットネス関数を使用して評価します。

  • すべてのダブルブッキングされた審査官に（厳しく）罰する
  • 審査官の空き時間にペナルティを課す
  • 期間内に割り当てられなかった受験者にペナルティを課す
  • 期間内に予約した各受験者のテストの報酬

この関数には、二重予約などを決定するためのすべてのロジックがあります。個人に完全な提案されたスケジュールがあり、フィットネスを決定するために各予約で各テストの時間を知っているロジックを実行し、スコアを増減します。それに応じて予約。

これをうまく機能させるには、次のことを考慮してください。

  • 開始 - 計算上安価な場合は、「正気の」予約を行うために必要な情報をできるだけ多く使用します。
  • 適切な GA 演算子を定義する

正気の方法で開始する：

  • 期間内でランダムに選択します
  • (1,2,..,N) をランダムに並べ替えてから、これから i を選択します (重複を回避します)。j と t についても同様です。

適切な GA 演算子:

aとbを予約しているとします: (a_i,a_j,a_t,a_d) (b_i,b_j,b_t,b_d)

a_i と b_i を交換したり、a_j と b_j と a_d と b_d を交換したりできますが、a_t と b_t を交換する意味はありません。

また、例で最もよく説明されているサイクリングを行うこともできます。N*T = 4 の場合、完全な予約は 4 つのタプルであり、i または j または d に沿って循環します。たとえば、i に沿って循環します。

a_i = b_i
b_i = c_i
c_i = d_i
d_i = a_i
于 2010-06-03T16:46:30.327 に答える
0

時期尚早に遺伝的アルゴリズムに限定しないでください。他にも多くのアプローチがあります。

より具体的に言うと、遺伝的アルゴリズムは、2 つのソリューションの一部を組み合わせて新しいソリューションを作成できる場合にのみ、本当に役立ちます。これは、少なくとも同じような数の人と試験があり、ほとんどの人が直接対話する場合、この問題にはかなり難しいように見えます。

于 2010-06-01T19:36:01.843 に答える