algorithm - 教師のタイムスケジュールアルゴリズム

Question

これは私が長い間頭に浮かんだ問題です。教師とプログラマーの息子である私は、早い段階でそれを思いつきました...しかし、私はまだそれに対する解決策を見つけていません。

これが問題です。いくつかの制約を使用して、学校のタイムスケジュールを作成する必要があります。これらは一般的に2つのカテゴリに分けられます。

健全性チェック

教師は2つのクラスを同時に教えることはできません
生徒は同時に2つのレッスンに従うことはできません
一部の教師は、週の間に少なくとも1日休む必要があります
曜日はすべてタイムテーブルでカバーする必要があります
被験者Xは毎週正確にまあまあの時間を持っている必要があります
..。

環境設定

各教師のスケジュールは可能な限りコンパクトにする必要があります（つまり、教師は1日中、可能であれば一時停止せずに1日中すべての時間作業する必要があります）
休日のある教師は、どの日に好みを表現できる必要があります
アルバイトをしている教師は、学校の一日の初めと終わりのどちらで働くかという好みを表現できる必要があります。
..。

さて、解決策を見つけられなかった（そしてその間に1つか2つのことを学んだ...）数年後、私はこれがNP困難な問題のように聞こえることに気づきました。

NP困難として証明されていますか？

誰かがこのことをクラックする方法についてのアイデアを持っていますか？

この質問を見て、私はこの問題について、そしてこの場合に遺伝的アルゴリズムが使用できるかどうかについて考えさせられました。ただし、健全性チェックのルールを維持しながら可能性を変更することはかなり困難です。また、互換性のない要件を区別する方法もわかりません。

問題をより適切に特定するための小さな補遺。これは、すべての生徒が異なるクラス（たとえば、1年目のセクションA）に関連付けられ、教師がクラス間を移動するイタリアの学校スタイルの教室に適用されます。同じクラスのすべての生徒は同じスケジュールを持っており、どのレッスンに参加するかを選択することはできません。

score 23 · Accepted Answer

私は、学生情報システムのスケジューラ部分に取り組んでいる開発者の 1 人です。スケジューリング問題の最初のアプローチでは、制約充足問題を解決するために遺伝的アルゴリズムを研究しました。当初は成功していましたが、(学校のスケジューリングワークショップに参加した後) 問題に対するより単純な解決策があることに気付きました。

私たちの現在の実装はうまく機能し、短時間で有効なスケジュールを取得するために、スマートなヒューリスティックを使ったブルートフォースを使用しています。マスタースケジュール (教師へのクラスの割り当て) が最初に作成され、各教師が持つすべての制約を考慮しながら、(コースの要求に基づいて) 学生の競合の可能性を最小限に抑えます。次に、同じ方法を使用して学生をクラスにスケジュールします。

これを行うと、最初にマシンにマスタースケジュールを作成させ、必要に応じて人間がそれを微調整することができます。

スケジューラの現在の実装は perl で書かれていますが、私たちが早い段階で検討した他のオプションは Prolog と CLIPS (エキスパートシステム) でした。

score 2 · Accepted Answer

いくつかの制約が欠けているのではないかと思います。

可能な場合は、認定されたクラスに教師をスケジュールすることをお勧めします。

要求されたクラスと、それぞれの予想される人数が重要であると思われるかもしれません。

開始する場所は、すべての制約をリストし、それらを表すデータ構造を理解することだと思います。

次に、トライアルソリューションを構築するためのある種のエンジンを作成し、制約に従って適合性を評価します。

次に、楽しい遺伝的アルゴリズムの部分をそれに投げ込み、遺伝子が混ざり合うにつれて時間の経過とともに適応度を高めることができるかどうかを確認できます。

制約の小さなセットから始めて、成功が見られるようにそれらを増やします（成功が見られる場合）

制約を取り、線形計画法アルゴリズムのようなものと一緒にそれらを靴べらにする方法があるかもしれません。

同意します。それは楽しい挑戦のように聞こえます

score 2 · Accepted Answer

これは、会議のスケジュールに関するこのブログ投稿を思い出させます。ここにビデオの説明があります。

私はそれをどのように行うか：

人口に2つのことを含めさせます。

誰がどのクラスを教えているか（教師が1つの科目を教えることを期待しています）。
クラスが特定のタイムスロットで取るもの。

このようにして、競合を起こすことはできません（2つの場所にいる教師、または同時に2つの科目を持つクラス）。

適応度関数には次のものが含まれます。

各教師が1週間に与えるタイムスロットの数。
教師が同じ日に持っている時間枠の数（教師は丸一日の授業を行うことはできません。これもバランスを取る必要があります）。
クラスが同じ日に持っている同じ主題の時間枠の数（彼らは数学の丸一日を持つことはできません！）。

それらはバランスが取れている必要があるので、たぶんそれらすべての標準偏差を取ります。

score 2 · Accepted Answer

私は過去に同様の計画/スケジューリングの問題に取り組みましたが、このクラスの問題に最も適していることが多い AI 手法は「制約ベースの推論」です。

これは基本的に、ローレンティが提案したような力ずくの方法ですが、このアプローチには、必要な計算を最小限に抑えるために、実行不可能なソリューションを迅速に失敗させる効率的な順序で制約を適用することが含まれます。

「Constraint Based Reasoning」をグーグルで検索すると、この手法とそのスケジューリング問題への応用に関する多くのリソースが表示されます。

score 2 · Accepted Answer

私自身の質問に答える：

gnud が言及した FET プロジェクトでは、次のアルゴリズムを使用しています。

アルゴリズムについて: FET はヒューリスティックアルゴリズムを使用して、最も難しいものから順番にアクティビティを配置します。解決策が見つからない場合は、潜在的に不可能なアクティビティが示されるため、エラーを修正できます。アルゴリズムは、可能な場合はアクティビティを再帰的に交換して、新しいアクティビティ用のスペースを確保します。極端な場合は、バックトラックして評価の順序を切り替えます。重要なコードは src/engine/generate.cpp にあります。詳細については、私に電子メールを送信するか、メーリングリストに参加してください。このアルゴリズムは、人間の時刻表の操作を模倣していると思います。

リンク

ウィキペディアでストリンジェントソフトウェアがリードする「制約に基づく推論」をフォローすると、興味深い段落を含むこれらのページにたどり着きました。

有限領域で制約充足問題を解くことは、一般に NP 完全問題です。研究により、多数の多項式時間サブケースが示されています。これらのほとんどは、許可されたドメインまたは制約、または制約を変数に配置できる方法を制限することによって得られます。研究は、制約充足問題と、有限モデル理論やデータベースなどの他の分野の問題との関係も確立しています。

score 2 · Accepted Answer

これはマッピングの問題です。1 週間のすべての時間とすべての教師のアクティビティ (特定のクラスまたは空き時間に教える) にマッピングする必要があります。

問題を分割します。

教師、クラス、および設定のリストを作成し、ユーザーが地図上にいくつかの設定を入力して、開始点として使用できるようにします。
リストから 1 つの要素をランダムに取得し、リストが空になるまでサニティチェックを通過しない場合は、マップ上のランダムな空き位置に配置します。特定の反復で、正気度チェックを通過せずに要素をマップに配置できない場合は、マップ上の位置を 2 つずらしてから再試行してください。
マップがいっぱいになったら、マップ上の位置をずらして結果を最適化します。

ステップ 2 と 3 では、各反復をユーザーに表示します。リストに残っているアイテム、マップ上の位置、および計算された次の移動をユーザーに介入させます。

私はこれを試しませんでしたが、これが私の最初のアプローチです。

score 1 · Accepted Answer

Looking at this question made me think about this problem, and whether genetic algorithms would be usable in this case. However it would be pretty hard to mutate possibilities while maintaining the sanity check rules. Also it's not clear to me how to distinguish incompatible requirements.

Genetic Algorithms are very well suited to problems such as this. Once you come up with a decent representation of the chromosome (in this case, probably a vector representing all of the available class slots) you're most of the way there.

Don't worry about maintaining sanity checks during the mutation phase. Mutation is random. Sanity and preference checks both belong in the selection phase. A failed sanity check would drastically lower the fitness of an individual, while a failed preference would only mildly lower the fitness.

Incompatible requirements are a different problem altogether. If they're completely incompatible, you'll get a population that doesn't converge on anything useful.

score 0 · Accepted Answer

幸運を。このような問題を抱えた父親の息子であることが、私を研究グループに連れて行った理由です...

私が子供の頃、父が地元のスポーツリーグで試合の役員を予定していたとき、これには同様に長い制約のリストがあり、私は何か助けになるものを書こうとしました。大学に着いたとき、私はそれを最終年度のプロジェクトとして使用し、最終的にはモンテカルロの実装に落ち着きました（シミュレーテッドアニーリングモデルを使用）。

基本的な考え方は、NPでなければかなり近いので、解決策があると仮定するのではなく、与えられた時間枠内で最良のものを見つけることに着手するということです。すべての制約をそれらを破るコストで重み付けします。健全性チェックには莫大なコストがかかり、設定のコストは低くなります（ただし、休憩が増えると増加するため、1回破ると2回破るコストの半分未満になります）。

基本的な考え方は、「ランダムな」ソリューションから始めて、コストをかけたということです。次に、少数の割り当てを交換して変更を加え、それを再評価してから、変更を確率的に受け入れるか拒否しました。

何千回も繰り返した後、許容できるソリューションに近づきます。

しかし、私を信じてください。このクラスの問題には、研究グループが博士号を取得しているので、あなたはとても良い仲間になっています。

また、シンプレックスなどの線形計画法の分野にも興味があるかもしれません。

score 0 · Accepted Answer

はい、これはNP完全だと思います-または少なくとも最適なソリューションを見つけるにはNP完全です。

私は大学で同様の問題に取り組みました。友人の父親（教師でした）に、適切なプログラムが見つからない場合は彼のスケジュールの問題を解決できると話しました（これは1990年頃に遡ります）。

自分が何に夢中になっているのかわかりませんでした。幸いなことに、私がしなければならなかったのは、制約に適合する1つの解決策を見つけることだけでした。しかし、私のテストでは、解決策があるかどうかを判断することを常に心配していました。彼にはあまり多くの制約がなく、プログラムはさまざまなヒューリスティックとバックトラッキングを使用していました。とても楽しかった。

ビル・ゲイツも高校や大学でこのようなシステムに取り組んだと思います。でもわからない。

幸運を。私のメモはすべてなくなり、市場に出すことができるソリューションを実装することはできませんでした。これは、新しい言語（Basic、Scheme、C、VB、C ++）を習得したときに再コーディングした特殊なプロジェクトでした。

それを楽しんでください

score 0 · Accepted Answer

この問題は、Prolog プログラムをデータベースに接続することで解決できることがわかりました。このプログラムは、一連の制約を指定してスケジュールを作成し、「制約充足問題のプロローグ」を読み上げることができます。

algorithm - 教師のタイムスケジュールアルゴリズム

10 に答える 10

Related

Reference