学校の時間割作成アルゴリズム
https://stackoverflow.com/questions/2177836
-
24-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
学校の時間割を作成するアルゴリズムに関する既知の解決策があるかどうか疑問に思っています。基本的に、これは、特定のクラス、教科、教師の関連付けにおける「時間分散」（教師とクラスの両方の場合）を最適化することです。入力時にクラス、授業科目、教師のセットが相互に関連付けられており、時間割は午前 8 時から午後 4 時の間に収まるはずだと想定できます。
おそらくそのための正確なアルゴリズムはないと思いますが、誰かがそれを開発するための適切な近似またはヒントを知っているかもしれません。
解決
この問題はです NPコンプリート!
一言で言えば、許容可能なソリューションのリストを見つけるために、可能なすべての組み合わせを探求する必要があります。さまざまな学校で問題が現れる状況の変動のためです（たとえば、教室に関して制約はありますか？、クラスの一部はサブグループで分割されていますか？など）すべてのスケジューリングの問題に対応する有名な問題クラスはありません。多分、 ナップサックの問題 これらの問題全体と類似性の多くの要素があります。
これが難しい問題であり、人々が永遠に解決策を求めている問題の両方であることの確認は、これをチェックすることです（長い） （主に商用）ソフトウェアスケジューリングツールのリスト
関係する変数の数が多いため、最大のソースは、通常、教員の欲求です; - ）... すべての可能な組み合わせを列挙することを検討することは非現実的です. 。代わりに、問題/ソリューションスペースのサブセットにアクセスするアプローチを選択する必要があります。
- 遺伝的アルゴリズム, 、別の答えで引用されています（または、私見、 思われる）この種の半誘導検索を実行するのに適した装備（問題は、候補者が次世代に維持されるための適切な評価機能を見つけることです）
- グラフの書き換え このタイプの組み合わせ最適化の問題にもアプローチが使用されます。
自動スケジュールジェネレータープログラムの特定の実装に焦点を当てるのではなく、提案したい 適用できるいくつかの戦略、 問題の定義のレベルで.
一般的な理論的根拠は、ほとんどの現実世界のスケジューリングの問題では、表現され、暗示されたすべての制約ではなく、いくつかの妥協が必要になるということです。したがって、私たちは次のように自分自身を助けます。
- すべての既知の制約の定義とランキング
- 手動で問題空間を減らす、一連のセットを提供する 追加 制約。
これは直感に反しているように見えるかもしれませんが、たとえば、すべての制約を完全に満たす方法で、初期の部分的に満たされたスケジュール（たとえば、タイムスロットの約30％など）を提供することによって、この部分的なスケジュールを不変であることを考慮することにより、私たちは大幅に減少します。候補ソリューションを作成するために必要な時間/スペース。
追加の制約の別の方法は、たとえば「人為的に」制約を追加することで、週のある日に一部の被験者を教えるのを防ぐことです（これが毎週のスケジュールの場合...）。このタイプの制約により、通常、かなりの数の優れた候補者を除外することなく、問題/ソリューションスペースが削減されます。 - 問題の制約の一部を迅速に計算できるようにします。これは、多くの場合、問題を表すために使用されるデータモデルの選択に関連付けられています。アイデアは、いくつかのオプションを迅速に選択（またはプルーンアウト）できるようにすることです。
- 問題を再定義し、いくつかの制約を数回壊すようにします（通常、グラフのエンドノードに向かって）。ここでのアイデアは、削除することです いくつか スケジュールの最後のいくつかのスロットを埋めるための制約、または自動スケジュールジェネレータープログラムにスケジュール全体を完了するのを恥ずかしくさせるために、その代わりに、もっともっともらしい候補者のリストを提供します。人間はしばしば、示されているように、パズルを完成させるより良い立場にあり、おそらくいくつかのコントレントを破り、通常は自動化されたロジックと共有されない情報を使用しています（例：「午後の数学はありません」ルールを時々破ることができます。 「高度な数学と物理学」クラスの場合、または「スミスさんの1つよりもジョーンズ氏の要件の1つを破る方が良い... ;-)
この答えを校正する際に、私はそれが明確な反応を提供することに非常に恥ずかしがり屋であることを認識していますが、それはそれでも実際的な提案に満ちています。結局のところ、これが「難しい問題」であることを助けてくれることを願っています。
他のヒント
それはめちゃくちゃです。王室の混乱。すでに非常に完全な答えに追加するために、私は私の家族の経験を指摘したいと思います。私の母は教師であり、以前はその過程に関与していました。
コンピューターを持っていることは、SEをコーディングするのが難しいだけでなく、事前に焼かれたコンピュータープログラムに指定することが困難な条件があるため、難しいことでもあります。例：
- 教師はあなたの学校と別の研究所の両方で教えています。明らかに、彼が10.30でレッスンを終了すると、彼は10.30にあなたの施設から始めることができません。
- 2人の教師が結婚しています。一般的に、同じクラスに2人の結婚した教師がいないことは良い習慣と考えられています。したがって、これら2人の教師には2つの異なるクラスが必要です
- 2人の教師が結婚しており、子供は同じ学校に通っています。繰り返しますが、2人の教師が子供がいる特定のクラスで教えることを防ぐ必要があります。
- 学校には別の施設があります。ある日、クラスはある研究所にあり、別の日はクラスが別の施設にあります。
- 学校は研究所を共有していますが、これらの研究所は特定の平日にのみ利用可能です（たとえば、追加の人員が必要な場合など）。
- 一部の教師は無料の日を好みます。月曜日に好み、金曜日には水曜日には好みがあります。早朝に来ることを好む人もいれば、後で来ることを好む人もいます。
- 発言権のあるレッスン、最初の1時間の歴史、次に3時間の数学、さらに1時間の歴史がある状況があるべきではありません。それは生徒にとっても教師にとっても意味がありません。
- 引数を均等に広める必要があります。週の最初の日だけが数学のみ、そして週の残りの文学のみを持つことは意味がありません。
- 評価テストを行うために、一部の教師に2回連続で与える必要があります。
ご覧のとおり、問題はNP不完全ではなく、NPインナンです。
したがって、彼らがしていることは、小さなプラスチックの挿入図を備えた大きなテーブルがあり、満足のいく結果が得られるまで挿入図を動かしているということです。彼らは決してゼロから始めることはありません：彼らは通常、前年の時刻表から始まり、調整を行います。
2007年の国際時間計算コンペティション レッスンのスケジューリングトラックと試験のスケジューリングトラックがありました。多くの研究者がその競争に参加しました。多くのヒューリスティックとメタヒューリスティックが試みられましたが、最終的には、地域の検索メタヒューリスティック（タブー検索やシミュレーションアニーリングなど）が他のアルゴリズム（遺伝的アルゴリズムなど）を明らかに破りました。
ファイナリストの一部が使用する2つのオープンソースフレームワークをご覧ください。
- JBoss Optaplanner （Java、オープンソース）
- ユニットタイム （Java、オープンソース） - 大学の詳細
私の半期の課題の 1 つは、遺伝的アルゴリズムによる学校表の生成でした。
テーブル全体が一つの「有機体」です。汎用遺伝的アルゴリズムのアプローチには、いくつかの変更と注意事項がありました。
「不正なテーブル」に対してルールが作成されました。同じ教室で 2 つのクラス、1 人の教師が同時に 2 つのグループを教えるなど。これらの突然変異は即座に致命的であると判断され、「死亡した」ものの代わりに新しい「生物」が即座に発芽しました。最初のものは、合法的な (無意味な場合でも) ものを取得するための一連のランダムな試行によって生成されました。致死突然変異は、反復における突然変異の数にカウントされませんでした。
「交換」突然変異は「変更」突然変異よりもはるかに一般的でした。変化は遺伝子の意味のある部分の間だけであり、教師を教室に置き換えることはありませんでした。
特定の 2 時間をまとめたり、同じグループに同じ一般的な教室を順番に割り当てたり、教師の勤務時間とクラスの負荷を継続的に維持したりするために、少額のボーナスが割り当てられました。特定の科目に適切な教室を提供したり、授業時間を制限内 (午前または午後) に維持したりすることなどに対して、中程度のボーナスが割り当てられました。大きなボーナスは、指定された科目の正しい数を割り当てたり、教師に与えられた仕事量などにありました。
教師は、適切な重みを割り当てて、「その時は働きたい」、「その時は働いても大丈夫」、「その時は働きたくない」、「その時は働けない」という仕事量のスケジュールを作成できます。夜間は非常に望ましくないことを除いて、24 時間はすべて法定労働時間でした。
重み関数は...そうそう。重み関数は、選択された機能とプロパティに割り当てられた重みの巨大で巨大な積 (乗算のような) でした。それは非常に急勾配であり、1 つの特性によって簡単に上下に一桁変化する可能性があり、1 つの生物には数百または数千の特性がありました。これにより、重みとして非常に巨大な数値が得られ、直接的な結果として、計算を実行するために bignum ライブラリ (gmp) を使用する必要がありました。約 10 のグループ、10 人の教師、10 の教室からなる小規模なテストケースの場合、最初のセットは 10^-200 程度のノートから始まり、10^+300 程度で終了しました。もっとフラットだと完全に非効率でした。また、大きな「学校」になるほど、価値観の距離はさらに広がりました。
計算時間の点では、長期間にわたる小規模な母集団 (100) と、より少ない世代にわたる大きな母集団 (10,000 人以上) との間にはほとんど差がありませんでした。同時に計算すると、ほぼ同じ品質が得られました。
計算 (1 GHz CPU 上で) が 10^+300 付近で安定するまでに約 1 時間かかり、前述の 10x10x10 テスト ケースでは非常に見栄えの良いスケジュールが生成されます。
この問題は、計算を実行しているコンピュータ間で最良のサンプルを交換するネットワーク機能を提供することで簡単に並列化できます。
結果として得られたプログラムは、その学期に良い成績を収めることができました。ある程度の見込みはありましたが、GUI を追加して一般の人が使用できるようにするほどの動機は得られませんでした。
この問題は、見た目よりも厳しいです。
他の人が暗示しているように、これはNP完全な問題ですが、それが何を意味するのかを分析しましょう。
基本的に、それはあなたが考えられるすべての組み合わせを見る必要があることを意味します。
しかし、「見てください」は、あなたがする必要があることをあまり教えてくれません。
可能なすべての組み合わせを生成するのは簡単です。膨大な量のデータが生成される可能性がありますが、問題のこの部分の概念を理解するのに多くの問題はありません。
2番目の問題は、与えられた可能性のある組み合わせが以前の「良い」ソリューションよりも良い、悪い、または優れているかどうかを判断するものです。
このためには、「それは可能な解決策ですか」以上のものが必要です。
たとえば、同じ教師は週5日間x週間連続して働いていますか？たとえそれが実用的な解決策であっても、各教師がそれぞれ1週間を行うように、二人を交互にするよりも優れた解決策ではないかもしれません。ああ、あなたはそれについて考えていませんでしたか？覚えておいてください、これはあなたが扱っている人々であり、単なるリソース割り当ての問題ではありません。
1人の教師が16週間連続してフルタイムで働くことができたとしても、それは教師の間を交互にしようとするソリューションと比較して、最適下の解決策である可能性があり、この種のバランスはソフトウェアに組み込むのが非常に困難です。
要約すると、この問題に対する良い解決策を生み出すことは、多くの人々にとって多くの価値があります。したがって、分解して解決するのは簡単な問題ではありません。 100％ではないいくつかの目標を賭けて、それらを「十分に良い」と呼ぶ準備をしてください。
更新：コメントから...ヒューリスティックも必要です！
私はPrologと一緒に行きます...それからRubyやPerlなどを使用して、ソリューションをきれいな形にクリーンアップします。
teaches(Jill,math).
teaches(Joe,history).
involves(MA101,math).
involves(SS104,history).
myHeuristic(D,A,B) :- [test_case]->D='<';D='>'.
createSchedule :- findall(Class,involves(Class,Subject),Classes),
predsort(myHeuristic,Classes,ClassesNew),
createSchedule(ClassesNew,[]).
createSchedule(Classes,Scheduled) :- [the actual recursive algorithm].
私は（まだ）この問題に似たことをしているプロセスにいますが、今述べたのと同じパスを使用しています。 Prolog（機能的言語として）は、NPハードの問題を本当に簡単に解決します。
このようなスケジューリングには、遺伝的アルゴリズムがよく使用されます。
見つかった この例（遺伝的アルゴリズムを使用してクラススケジュールを作成） あなたの要件にかなりよく一致しています。
FETに実装された私の時刻表アルゴリズム（無料の時刻表現ソフトウェア、 http://lalescu.ro/liviu/fet/ 、成功したアプリケーション）：
アルゴリズムはヒューリスティックです。私はそれを「再帰スワッピング」と名付けました。
入力：一連のアクティビティA_1 ... A_Nおよび制約。
出力：TA_1 ... TA_Nのセット（各アクティビティのタイムスロット。簡単にするために、部屋はここで除外されます）。アルゴリズムは、制約を尊重して、各アクティビティを時間スロットに配置する必要があります。各TA_Iは0（T_1）とMAX_TIME_SLOTS-1（T_M）の間です。
制約：
c1）基本：同時にできないアクティビティのペアのリスト（たとえば、A_1とA_2、同じ教師または同じ生徒がいるため）;
c2）他の多くの制約（簡単にするために、ここでは除外）。
時刻表アルゴリズム（「再帰スワッピング」と名付けられました）：
- アクティビティを並べ替えて、最初に最も難しい。重要なステップではありませんが、アルゴリズムを10倍以上スピードアップします。
上記の順序に従って、各アクティビティ（A_I）を許可されたタイムスロットに配置してみてください。 A_Iの利用可能なスロット（T_J）を検索します。このアクティビティは、制約を尊重することができます。より多くのスロットが利用可能な場合は、ランダムなスロットを選択してください。ない場合は、再帰交換を行います。
a. 。スロットT_Jの各時間ごとに、A_IをT_Jに入れた場合に何が起こるかを考えてください。この動きに同意しない他のアクティビティのリストがあります（たとえば、アクティビティA_Kは同じスロットT_Jにあり、A_Iと同じ教師または同じ生徒がいます）。スロットT_Jの各時間ごとに競合するアクティビティのリストを保管してください。
b. 。競合するアクティビティの数が最も少ないスロット（T_J）を選択します。このスロットのアクティビティのリストには、A_P、A_Q、A_Rの3つのアクティビティが含まれています。
c. 。 t_jにa_iを配置し、a_p、a_q、a_rをunallocatedにします。
d. 。再帰的にA_P、A_Q、A_Rを配置しようとします（再帰のレベルが大きすぎない場合、たとえば14、およびステップ2以降にカウントされた再帰コールの総数があります）A_Iの開始は大きすぎません、たとえば2*n）ステップ2のように）。
e. 。 A_P、A_Q、A_Rが正常に配置された場合は、成功して戻ります。それ以外の場合は、他のタイムスロット（ステップ2 bに移動）を試して、次のベストタイムスロットを選択します）。
f. 。すべての（または合理的な数の）タイムスロットが失敗した場合、成功せずに戻ります。
g. 。レベル0で、A_Iを配置することに成功していない場合、手順2 b）および2 c）のように配置しますが、再帰はありません。現在、3〜1 = 2のアクティビティがあります。ステップ2に移動）（ここでは、サイクリングを避けるためのいくつかの方法が使用されています）。
クラスの時刻表と試験の時間計の両方の商用アルゴリズムを設計しました。最初に整数プログラミングを使用しました。 2番目の場合、スロットスワップを選択して目的関数を最大化することに基づいたヒューリスティックは、進化した元の手動プロセスと非常によく似ています。そのような解決策を受け入れることの主なことは、すべての現実世界の制約を表す能力です。そして、人間の時刻船が解決策を改善する方法を見ることができないようにするため。最終的に、アルゴリズムの部分は、データベース、ユーザーインターフェイス、部屋利用、ユーザー教育などの統計について報告する能力と比較して、非常に簡単で実装が簡単でした。
このペーパーでは、学校の時刻表の問題とアルゴリズムへのアプローチについては、かなりよく説明しています。」シラバスの開発 - 学校や大学のインタラクティブな制約ベースのスケジューラ。「[PDF
著者は、Syllabusソフトウェアがまだここで使用/開発されていることを教えてくれます。 http://www.scientia.com/uk/
私はまさにこれを行う広く使用されているスケジューリングエンジンに取り組んでいます。はい、それはnp完全です。最良のアプローチは、最適なソリューションを近似しようとしています。そしてもちろん、どれが「最高の」解決策であるかを言うには、多くの異なる方法があります。教師がスケジュールに満足していること、または学生がすべてのクラスに参加することがより重要ですか？
あなたが早期に解決するために必要な絶対的な最も重要な質問は このシステムを別のシステムよりも優れたスケジューリングの1つの方法を作るもの？つまり、ジョーンズ夫人が8時に数学を教え、スミス氏が9時に数学を教えるスケジュールを持っている場合、それは両方とも10時に数学を教えているものよりも優れていますか？ジョーンズ夫人が8時と2時に教えているジョーンズ氏の教えよりも優れているのか、それとも悪いのでしょうか？なんで？
ここで私が与える主なアドバイスは、問題を可能な限り分割することです - おそらくコースごと、おそらく教師ごとに教師、おそらく部屋ごとに部屋であるかもしれません - そして、最初にサブ問題の解決に取り組むことです。そこでは、選択する複数のソリューションが表示され、最も可能性の高いものとして1つを選択する必要があります。次に、「以前の」サブ問題に、潜在的なソリューションを獲得する際の後のサブプロメインのニーズを考慮して作業します。次に、「有効な解決策なし」状態に到達したときに、塗装された状況から抜け出す方法（以前のサブ問題でこれらの状況を予測できないと仮定して）に取り組む方法に取り組むかもしれません。
より良い結果を得るために、最終回答を「磨く」ために、ローカル検索最適化パスがよく使用されます。
通常、私たちは学校のスケジューリングで高度にリソースに制約のあるシステムを扱っていることに注意してください。学校は、1日の75％のラウンジに座っている空の部屋や教師がたくさんいて、一年中通り抜けません。ソリューションが豊富な環境で最適に機能するアプローチは、学校のスケジューリングに必ずしも適用されるわけではありません。
一般に、制約プログラミングは、このタイプのスケジューリング問題に対する適切なアプローチです。スタックオーバーフロー内とGoogle内の両方の「制約プログラミング」とスケジューリングまたは「制約ベースのスケジューリング」の検索がいくつかの適切な参照を生成します。それは不可能ではありません - 線形や整数の最適化などの従来の最適化方法を使用する場合、考えるのは少し難しいです。 1つの出力は、すべての要件を満たすスケジュールが存在しますか？それ自体は明らかに役立ちます。
幸運を ！
はい、遺伝的アルゴリズムでそれをテイクすることができます。しかし、あなたはすべきではありません:)。遅すぎる可能性があり、パラメーターのチューニングは時間をかけすぎている可能性があります。
他のアプローチが成功しています。すべてオープンソースプロジェクトで実装されています：
- 制約ベースのアプローチ
- で実装 ユニットタイム （実際には学校ではありません）
- さらに進んで整数プログラミングを使用することもできます。で正常に完了しました ウディーン大学 また、コマーシャルソフトウェア（ILOG CPLEX）を使用して、バイロース大学で（私はそこに関与していました）
- Heuristiscを使用したルールベースのアプローチ - 参照 Drools Planner
- 異なるヒューリスティック - フェット と 私自身
ここを参照してください 時刻表現ソフトウェアリスト
次のように、遺伝的アルゴリズムを使用する必要があると思います。
- 大規模な問題インスタンスに最適です。
- それは不正確な答えの価格の時間の複雑さの減少をもたらします（究極の最高ではありません）
- 満たされていないもののフィットネスの罰を調整することにより、制約と好みを簡単に指定できます。
- プログラム実行の時間制限を指定できます。
ソリューションの品質は、プログラムの解決に費やす時間に依存します。
私は誰もこのコードに同意することはわかりませんが、私は自分のアルゴリズムの助けを借りてこのコードを開発し、Rubyで私のために働いています。 SubjectFlagとTeacherFlagは、対応するIDとブール値のフラグ値を備えたハッシュです。どんな問題でも私に連絡してください......（-_-）
Periodflag.each do | k2、v2 |
if(TimetableDefinition.find(k2).period.to_i != 0)
subjectflag.each do |k3,v3|
if (v3 == 0)
if(getflag_period(periodflag,k2))
@teachers=EmployeesSubject.where(subject_name: @subjects.find(k3).name, division_id: division.id).pluck(:employee_id)
@teacherlists=Employee.find(@teachers)
teacherflag=Hash[teacher_flag(@teacherlists,teacherflag,flag).to_a.shuffle]
teacherflag.each do |k4,v4|
if(v4 == 0)
if(getflag_subject(subjectflag,k3))
subjectperiod=TimetableAssign.where("timetable_definition_id = ? AND subject_id = ?",k2,k3)
if subjectperiod.blank?
issubjectpresent=TimetableAssign.where("section_id = ? AND subject_id = ?",section.id,k3)
if issubjectpresent.blank?
isteacherpresent=TimetableAssign.where("section_id = ? AND employee_id = ?",section.id,k4)
if isteacherpresent.blank?
@finaltt=TimetableAssign.new
@finaltt.timetable_struct_id=@timetable_struct.id
@finaltt.employee_id=k4
@finaltt.section_id=section.id
@finaltt.standard_id=standard.id
@finaltt.division_id=division.id
@finaltt.subject_id=k3
@finaltt.timetable_definition_id=k2
@finaltt.timetable_day_id=k1
set_school_id(@finaltt,current_user)
if(@finaltt.save)
setflag_sub(subjectflag,k3,1)
setflag_period(periodflag,k2,1)
setflag_teacher(teacherflag,k4,1)
end
end
else
@subjectdetail=TimetableAssign.find_by_section_id_and_subject_id(@section.id,k3)
@finaltt=TimetableAssign.new
@finaltt.timetable_struct_id=@subjectdetail.timetable_struct_id
@finaltt.employee_id=@subjectdetail.employee_id
@finaltt.section_id=section.id
@finaltt.standard_id=standard.id
@finaltt.division_id=division.id
@finaltt.subject_id=@subjectdetail.subject_id
@finaltt.timetable_definition_id=k2
@finaltt.timetable_day_id=k1
set_school_id(@finaltt,current_user)
if(@finaltt.save)
setflag_sub(subjectflag,k3,1)
setflag_period(periodflag,k2,1)
setflag_teacher(teacherflag,k4,1)
end
end
end
end
end
end
end
end
end
end
end
