学校の時間割を作成するアルゴリズムの既知の解決策があるかどうか疑問に思っていました。基本的には、特定のクラス-科目-教師の関連付けについて、(教師とクラスの両方のケースで)「時間分散」を最適化することです。入力時に互いに関連付けられたクラス、授業科目、および教師のセットがあり、そのタイムテーブルは午前 8 時から午後 4 時の間に収まると仮定できます。
そのための正確なアルゴリズムはおそらくないと思いますが、誰かがそれを開発するための適切な近似またはヒントを知っているかもしれません。
質問する
81107 次
17 に答える
100
この問題はNP完全です！
簡単に言えば、許容可能なソリューションのリストを見つけるために、すべての可能な組み合わせを調査する必要があります。さまざまな学校で問題が発生する状況が異なるため (例: 教室に関して制約はありますか?、一部のクラスは時々サブグループに分割されますか?、これは毎週のスケジュールですか?など）すべてのスケジューリング問題に対応するよく知られた問題クラスはありません。おそらく、ナップザック問題には、これらの問題全般と類似する要素がたくさんあります。
これが困難な問題であり、人々が長年にわたって解決策を模索している問題であることを確認するには、この(主に商用の) ソフトウェア スケジューリング ツールの (長い) リストを確認してください。
関係する変数の数が非常に多いため、その最大の原因は通常、教員の欲求です;-)...、すべての可能な組み合わせを列挙することを検討することは通常非現実的です。代わりに、問題/解決空間のサブセットにアクセスするアプローチを選択する必要があります。
-別の回答で引用されている遺伝的アルゴリズムは（または、IMHOのように）この種の半誘導検索を実行するのに十分な設備が整っています（問題は、次世代のために保持される候補の適切な評価関数を見つけることです）
-グラフ書き換えアプローチは、このタイプの組み合わせ最適化問題にも役立ちます。
自動スケジュール生成プログラムの特定の実装に焦点を当てるのではなく、問題の定義のレベルで適用できるいくつかの戦略を提案したいと思います。
一般的な理論的根拠は、ほとんどの現実世界のスケジューリング問題では、明示的および暗示的なすべての制約ではなく、いくつかの妥協が必要になるということです: 完全に満たされるでしょう。したがって、私たちは次のことで自分自身を助けます：
- すべての既知の制約の定義とランク付け
- 一連の追加の制約を提供して、手動で問題領域を縮小します。
これは直感に反するように思えるかもしれませんが、たとえば、すべての制約を完全に満たす方法で最初の部分的に満たされたスケジュール (時間枠の約 30% など) を提供し、この部分的なスケジュールを不変と見なすことによって、候補ソリューションを作成するために必要な時間/スペース。
追加の制約が役立つもう1つの方法は、たとえば、「人為的に」制約を追加して、一部の曜日に一部の科目を教えないようにすることです（これが毎週のスケジュールの場合...）。このタイプの制約は、通常、かなりの数の適切な候補を除外することなく、問題/ソリューション空間を縮小します。 - 問題の制約の一部を迅速に計算できるようにします。これは、多くの場合、問題を表すために使用されるデータ モデルの選択に関連しています。アイデアは、いくつかのオプションをすばやく選択 (または除外) できるようにすることです。
- 問題を再定義し、いくつかの制約を数回 (通常はグラフの終了ノードに向かって) 破ることができるようにします。ここでのアイデアは、スケジュールの最後の数スロットを埋めるための制約の一部を削除するか、スケジュール全体を完了するのを恥ずかしがって自動スケジュール生成プログラムを停止させ、代わりに1ダースほどのもっともらしいリストを提供することです。候補者。示されているように、人間は多くの場合、自動化されたロジックと通常共有されない情報を使用して、いくつかの制約を破る可能性があり、パズルを完成させるのにより適した立場にあります (たとえば、「午後は数学なし」ルールが時々破られる可能性があります)。 「高度な数学と物理学」クラスの場合; または「スミスさんの要件の 1 つよりも、ジョーンズ氏の要件の 1 つを破る方が良いです ... ;-) )
この回答を校正すると、明確な回答を提供するのが非常に恥ずかしがり屋であることがわかりますが、それでも実用的な提案に満ちています. 結局のところ、「難しい問題」とは何か、これが助けになることを願っています。
于 2010-02-01T17:11:51.903 に答える
56
それは混乱です。王道の混乱。すでに非常に完全な回答に追加するために、私の家族の経験を指摘したいと思います. 私の母は教師で、そのプロセスに関わっていました。
コンピューターにそれをさせることは、それ自体をコーディングするのが難しいだけでなく、事前に焼き付けられたコンピュータープログラムに指定するのが難しい条件があるため、難しいことが判明しました。例:
- 教師はあなたの学校と別の教育機関の両方で教えています。明らかに、彼が 10 時 30 分にそこでレッスンを終了した場合、彼は研究所間を移動するのに時間がかかるため、10 時 30 分にあなたの施設でレッスンを開始することはできません。
- 二人の先生は結婚しています。一般に、同じクラスに 2 人の既婚の教師を持たないことは良い習慣であると考えられています。したがって、これら 2 人の教師は 2 つの異なるクラスを持つ必要があります。
- 2 人の教師は結婚しており、その子供は同じ学校に通っています。繰り返しますが、2 人の教師が子供がいる特定のクラスで教えないようにする必要があります。
- ある日はあるインスティテュートでクラスが行われ、別の日は別のインスティテュートでクラスが行われるように、学校には別々の施設があります。
- 学校は実験室を共有していますが、これらの実験室は特定の平日にのみ利用できます（たとえば、追加の人員が必要な場合など、セキュリティ上の理由から）。
- 月曜日、金曜日、水曜日を好む教師もいます。早朝に来ることを好む人もいれば、遅く来ることを好む人もいます。
- たとえば、最初の 1 時間は歴史を学び、次に 3 時間数学を学び、さらに 1 時間歴史を学ぶというような状況があってはなりません。生徒にとっても教師にとっても意味がありません。
- 引数を均等に分散する必要があります。週の最初の日を数学だけにして、残りの週を文学だけにするのは意味がありません。
- 一部の教師には、評価テストを行うために 2 時間連続して与える必要があります。
ご覧のとおり、問題は NP 完全ではなく、NP 非常識です。
彼らがしていることは、小さなプラスチック製のはめ込みのある大きなテーブルを用意し、満足のいく結果が得られるまではめ込みを移動させることです。ゼロから始めることはありません。通常、前年のタイムテーブルから開始し、調整を行います。
于 2010-02-01T17:33:31.507 に答える
29
2007年国際タイムテーブルコンペティションには、レッスンスケジュールトラックと試験スケジュールトラックがありました。多くの研究者がそのコンテストに参加しました。多くのヒューリスティックとメタヒューリスティックが試されましたが、最終的にローカル検索メタヒューリスティック（タブーサーチやシミュレーテッドアニーリングなど）は他のアルゴリズム（遺伝的アルゴリズムなど）を明らかに上回りました。
ファイナリストの一部が使用している2つのオープンソースフレームワークを見てください。
- JBoss OptaPlanner（Java、オープンソース）
- Unitime（Java、オープンソース）-大学向け
于 2011-12-20T16:53:00.523 に答える
18
私の半期の課題の 1 つは、遺伝的アルゴリズムの学校の表の生成でした。
テーブル全体が一つの「生物」です。一般的な遺伝的アルゴリズムのアプローチには、いくつかの変更と注意事項がありました。
「違法なテーブル」については、同じ教室で 2 つのクラスを教える、1 人の教師が同時に 2 つのグループを教えるなどの規則が作られました。これらの変異は即座に致死的であるとみなされ、新しい「生物」が「死んだ」代わりに即座に発芽しました。最初のものは、正当な (無意味な場合) ものを取得するための一連のランダムな試行によって生成されました。致命的な突然変異は、反復の突然変異の数にカウントされませんでした。
「交換」変異は、「変更」変異よりもはるかに一般的でした。変化は意味のある遺伝子の部分の間だけでした - 教師を教室で置き換えることはありませんでした.
一定の 2 時間をまとめること、同じグループに同じ一般的な教室を順番に割り当てること、教師の勤務時間とクラスの負荷を継続的に保つことに対して、少額のボーナスが割り当てられました。与えられた教科に対して適切な教室を提供したり、授業時間を拘束時間 (午前または午後) 内に維持したりすることなどに対して、適度なボーナスが割り当てられました。大きなボーナスは、与えられた科目の正しい数を割り当てたり、教師の仕事量を与えたりすることなどでした.
教師は、「その時は働きたい」、「その時は働いてもいい」、「その時は働きたくない」、「その時は働けない」というワークロードのスケジュールを作成し、適切な重みを割り当てることができます。夜間が非常に望ましくないことを除いて、24時間全体が法定労働時間でした.
重み関数...そうそう。重み関数は、選択された機能とプロパティに割り当てられた重みの巨大で巨大な (乗算のような) 積でした。それは非常に急勾配で、1つの特性がそれを1桁上下に簡単に変えることができました.1つの生物には数百または数千の特性がありました. これにより、重みとして絶対に膨大な数が発生し、直接的な結果として、計算を実行するために bignum ライブラリ (gmp) を使用する必要がありました。約 10 のグループ、10 人の教師、10 の教室からなる小さなテストケースの場合、最初のセットは 10^-200 程度で始まり、10^+300 程度で終了しました。それがもっと平らだったとき、それは完全に非効率的でした. また、値は、より大きな「学校」でより広い距離に成長しました。
計算時間に関しては、長い期間にわたる小さな人口 (100) と少ない世代にわたる大きな人口 (10k+) の間にほとんど違いはありませんでした。同じ時間の計算では、ほぼ同じ品質が得られました。
10x10x10 のテスト ケースでは、(一部の 1GHz CPU での) 計算が 10^+300 付近で安定するまでに 1 時間ほどかかり、非常に見栄えの良いスケジュールが生成されます。
この問題は、計算を実行しているコンピューター間で最適な標本を交換するネットワーク機能を提供することで、簡単に並列化できます。
結果として得られたプログラムは、学期の良い成績を得るために外で日光を浴びることはありませんでした. ある程度の見込みはありましたが、GUI を追加して一般の人が使用できるようにする十分な動機が得られませんでした。
于 2010-02-02T12:37:13.453 に答える
9
この問題は、見た目よりも難しいです。
他の人がほのめかしたように、これはNP完全な問題ですが、それが何を意味するかを分析しましょう。
基本的に、考えられるすべての組み合わせを調べる必要があるということです。
しかし、「見る」だけでは、何をする必要があるかはわかりません。
すべての可能な組み合わせを生成するのは簡単です。膨大な量のデータが生成される可能性がありますが、問題のこの部分の概念を理解するのにそれほど問題はないはずです。
2 番目の問題は、与えられた可能な組み合わせが良いか、悪いか、以前の「良い」ソリューションよりも優れているかを判断することです。
これには、「可能な解決策か」以上のものが必要です。
たとえば、同じ教師が週 5 日、X 週間連続で働いていますか? それが実用的な解決策であるとしても、2 人を交互に使用して各教師が 1 週間ずつ行うよりも良い解決策ではないかもしれません。え、考えてなかったの？覚えておいてください、これはあなたが対処しているのは人であり、単なるリソース割り当ての問題ではありません.
1 人の教師がフルタイムで 16 週間連続で働くことができたとしても、教師を交互に配置しようとするソリューションと比較すると、最適なソリューションではない可能性があり、この種のバランスをソフトウェアに組み込むことは非常に困難です。
要約すると、この問題に対する優れた解決策を生み出すことは、多くの人々にとって大きな価値があります。したがって、分解して解決するのは簡単な問題ではありません。100% ではないいくつかの目標を賭ける準備をして、それらを「十分」と呼んでください。
于 2010-02-05T22:10:21.717 に答える
8
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）を一度に1つずつ配置してみてください。A_iの使用可能なスロット（T_j）を検索します。このスロットでは、制約を尊重してこのアクティビティを配置できます。より多くのスロットが利用可能な場合は、ランダムなスロットを選択してください。使用できるものがない場合は、再帰的なスワッピングを実行します。
。_ タイムスロット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。A_iをT_jに配置し、A_p、A_q、A_rを未割り当てにします。
d。A_p、A_q、A_rを再帰的に配置してみてください（再帰のレベルが大きすぎない場合、たとえば14、およびステップ2以降にカウントされた再帰呼び出しの総数が多すぎない場合、たとえば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）に進みます（ここでは、サイクリングを回避するためのいくつかの方法を使用しています）。
于 2011-06-04T08:47:42.160 に答える
6
更新: コメントから ... ヒューリスティックも必要です!
私なら 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 困難な問題を簡単に解決できます。
于 2010-02-01T15:45:09.630 に答える
5
このようなスケジューリングには、遺伝的アルゴリズムがよく使用されます。
この例 (遺伝的アルゴリズムを使用してクラスのスケジュールを作成する)が見つかりました。これは要件に非常によく一致します。
于 2010-02-01T15:45:52.280 に答える
5
于 2010-02-01T15:50:05.737 に答える
4
この論文では、学校の時間割の問題とそのアルゴリズムへのアプローチについて非常によく説明しています。
著者は、SYLLABUS ソフトウェアがまだここで使用/開発されていることを知らせてくれました: http://www.scientia.com/uk/
于 2010-05-04T01:34:16.060 に答える
3
私は、まさにこれを行う、広く使用されているスケジューリング エンジンに取り組んでいます。はい、NP-Complete です。最良のアプローチは、最適解を近似しようとします。もちろん、どれが「最良の」解決策であるかについては、さまざまな言い方があります。たとえば、教師がスケジュールに満足していることと、生徒がすべてのクラスに参加できることのどちらが重要でしょうか?
早い段階で解決しなければならない絶対的に最も重要な問題は、このシステムのスケジューリング方法が他の方法よりも優れている理由は何かということです。つまり、ジョーンズ夫人が 8 時に数学を教え、スミス氏が 9 時に数学を教えるというスケジュールがある場合、それは両方とも 10 時に数学を教えるスケジュールよりも良いですか、それとも悪いですか? ジョーンズ夫人が 8 歳で教え、ジョーンズ氏が 2 歳で教えている場合よりも良いですか、悪いですか? なんで？
ここでの主なアドバイスは、問題をできる限り分割することです。おそらくコースごと、教師ごと、部屋ごとなどです。そして、最初に下位の問題を解決することに取り組みます。そこでは、複数のソリューションから選択することになり、最も可能性が高い最適なものを 1 つ選択する必要があります。次に、潜在的な解決策を採点する際に、後のサブ問題の必要性を考慮して、「前の」サブ問題を作成する作業を行います。次に、「有効な解決策がない」状態になったときに、隅々まで塗りつぶされた状況から抜け出す方法に取り組むことができます (以前のサブ問題でそのような状況を予測できないと仮定して)。
ローカル検索最適化パスは、より良い結果を得るために最終的な回答を「洗練」するためによく使用されます。
通常、学校のスケジューリングでは、リソースに非常に制約のあるシステムを扱っていることに注意してください。学校は、多くの空の部屋や教師が 1 日の 75% をラウンジに座っている状態で 1 年を過ごすことはありません。解決策が豊富な環境で最もうまく機能するアプローチは、必ずしも学校のスケジューリングに適用できるとは限りません。
于 2014-03-27T18:59:42.757 に答える
2
授業時間割と試験時間割の両方の商用アルゴリズムを設計しました。最初は整数計画法を使用しました。2 つ目は、スロット スワップを選択して目的関数を最大化することに基づくヒューリスティックで、進化した元の手動プロセスと非常によく似ています。このようなソリューションを受け入れる主な理由は、現実世界のすべての制約を表現できることです。人間の時刻表担当者は、ソリューションを改善する方法を見つけることができません。最終的に、アルゴリズムの部分は、データベースの準備、ユーザー インターフェイス、部屋の使用率などの統計に関するレポート機能、ユーザー教育などに比べて、非常に単純で簡単に実装できました。
于 2010-02-05T22:00:56.323 に答える
2
一般に、制約プログラミングは、この種のスケジューリングの問題に対する優れたアプローチです。スタック オーバーフロー内と Google の両方で「制約プログラミング」とスケジューリングまたは「制約ベースのスケジューリング」を検索すると、いくつかの良い参考文献が生成されます。不可能ではありません。線形最適化や整数最適化などの従来の最適化手法を使用する場合、考えるのが少し難しいだけです。1 つの出力は次のようになります。すべての要件を満たすスケジュールは存在しますか? それ自体は明らかに役に立ちます。
幸運を ！
于 2010-02-01T15:45:25.247 に答える
2
はい、遺伝的アルゴリズムで対処できます。しかし、あなたはすべきではありません:)。遅すぎる可能性があり、パラメーターの調整に時間がかかりすぎる可能性があります。
成功した他のアプローチがあります。すべてオープン ソース プロジェクトで実装されています。
- 制約ベースのアプローチ
- UniTimeに実装されています(実際には学校向けではありません)。
- さらに進んで、整数計画法を使用することもできます。ウーディネ大学とバイロイト大学 (私はそこに参加していました) で商用ソフトウェア (ILOG CPLEX) を使用して成功裏に完了しました。
- ヒューリスティックを使用したルールベースのアプローチ - Drools プランナーを参照
- 異なるヒューリスティック - FETと私自身
時刻表ソフト一覧はこちら
于 2012-05-04T08:18:04.690 に答える
1
この問題は私が働いている場所では大規模です - 1800 の科目/モジュールと 350,000 人の学生がそれぞれ 5 から 10 のモジュールを行っていると想像してください。1 時間から 3 日の長さの論文である 10 週間で試験を作成したいと考えています... 1プラスポイント - すべての試験はオンラインですが、システムの最大同時負荷 5k を超えることはできません。そうです、私たちは現在、スケーリング サーバー上のクラウドでこれを行っています。私たちが使用した「解決策」は、降順で「衝突」する他のモジュールの数 (学生が両方を行う場合) でモジュールを順序付け、それらを「バックパック」して、これらの長い論文が実際に重複することを可能にすることでした。終わり。したがって、物事が大きくなりすぎると、この「ヒューリスティック」が実用的であることがわかりました...少なくとも。
于 2021-07-29T08:31:04.750 に答える
0
次の理由から、遺伝的アルゴリズムを使用する必要があると思います。
- 大規模な問題のインスタンスに最適です。
- 不正確な答えを犠牲にして時間の複雑さを軽減します（究極の最善ではありません）
- 満たされていないフィットネス罰を調整することで、制約と好みを簡単に指定できます。
- プログラムの実行時間制限を指定できます。
ソリューションの品質は、プログラムの解決に費やす予定の時間によって異なります。
于 2011-01-04T15:01:31.450 に答える
0
誰かがこのコードに同意するかどうかはわかりませんが、私は独自のアルゴリズムの助けを借りてこのコードを開発し、ルビーで私のために働いています。 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
于 2015-04-09T05:32:38.347 に答える