[解決済み] 学校の時間割を作成するアルゴリズム

質問

学校の時間割を作成するアルゴリズムについて、既知のソリューションがあるかどうか疑問に思っています。基本的には、与えられたクラス、科目、教師の関連付けに対して、quot;時間分散(教師とクラスの場合の両方)を最適化することです。入力時にクラス、レッスン科目、教師のセットが互いに関連付けられ、時間割は午前8時から午後4時の間に収まるはずだと仮定することができます。

おそらくそのための正確なアルゴリズムはないと思いますが、どなたか良い近似値や開発のヒントをご存じかもしれませんね。

どのように解決するのですか？

この問題は NP-completeです。 !

一言で言えば、許容できる解のリストを見つけるために、すべての可能な組み合わせを探索する必要があるということです。 なぜなら、この問題が現れる状況は学校によって様々だからです（例えば。例えば、教室に制約があるのか、クラスの一部がサブグループに分かれているのか、週単位のスケジュールなのか、など）、すべてのスケジューリング問題に対応するよく知られた問題クラスは存在しません。 もしかしたら、その ナップザック問題 は、広くこれらの問題と類似した要素を多く持っています。

これが難しい問題であり、人々が常に解決策を求める問題であることを確認するために、次のものを確認してください（長い）。 (ほとんどが商用) ソフトウェア スケジューリング ツールのリスト

関係する変数の数が多いため、その最大の原因は、典型的には、教員の願望です;-)...、それは典型的には すべての可能な組み合わせを列挙することは非現実的です。 . その代わりに、私たちは問題/解決空間のサブセットを訪問するアプローチを選択する必要があります。

- 遺伝的アルゴリズム は、別の回答で引用されている（または、IMHO。 は は、この種の半誘導探索を実行するのに十分な能力を備えています（問題は、次世代に残すべき候補のための良い評価関数を見つけることです）。

- グラフリライティング のアプローチは、この種の組合せ最適化問題にも有効である。

スケジュール自動生成プログラムの特定の実装に焦点を当てるよりも、むしろ私は 適用可能ないくつかの戦略を提案したいと思います。 問題の定義のレベルにおいて .

一般に、現実のスケジューリング問題では、何らかの妥協が必要であり、明示的・暗示的を問わず、すべての制約が完全に満たされるわけではない、というのがその根拠である。 そのため、私たちは以下の方法で自分たちを助けています。

• すべての既知の制約を定義し、ランク付けする
• 問題空間を縮小し、手作業で、一連の 追加 制約を提供する。
  
  これは直感に反するように思えるかもしれませんが、たとえば、すべての制約を完全に満たす方法で、部分的に埋められた初期スケジュール (たとえばタイムスロットの約 30%) を提供し、この部分スケジュールを不変とみなすことによって、候補解を生成するために必要な時間/スペースを大幅に削減します。
  
  制約を追加する別の方法は、たとえば、(これが週間スケジュールである場合、)いくつかの曜日でいくつかの科目を教えることができない制約を人為的に追加することです。このタイプの制約は、通常、かなりの数の良い候補を除外せずに、問題/ソリューション空間を縮小する結果になります。
• 問題の制約のいくつかが迅速に計算されることを保証すること。 これは、しばしば問題を表現するために使用されるデータモデルの選択と関連しています。アイデアは、いくつかの選択肢を素早く選ぶ（または切り捨てる）ことができるようにすることです。
• 問題を再定義し、制約のいくつかを何度か破れるようにします（通常、グラフの終端ノードに向かって）。 ここでのアイデアは、以下のいずれかを削除することです。 <項目 一部 スケジュールの最後の数スロットを埋めるための制約、または自動スケジュール生成プログラムが全スケジュールを完了する前に停止して、代わりに1ダースほどのもっともらしい候補のリストを提供することです。 人間は、通常自動化された論理と共有されていない情報を使って、示されたように、制約のいくつかを破ってパズルを完成させるより良い立場にいることがよくあります (たとえば、quot;午後は数学なし" 規則は、上級数学と物理学のクラスのために時々破ることができます; またはquot;スミス先生の要件の1つを破るよりジョーンズ先生の要件の1つを破る方が良いです ...;-)...このように、人間はパズルを作るために、より多くの制約を破らなければなりません。)

この回答を校正してみると、明確な回答を提供するのはかなり恥ずかしそうですが、それにも増して実用的な提案に満ちていることがわかります。 結局のところ、難しい問題なのですが、これが助けになることを願っています。