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

https://stackoverflow.com/questions/210635

03-07-2019
|

質問

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

これが問題です。いくつかの制約を使用して、学校の時間スケジュールを作成する必要があります。これらは通常、次の 2 つのカテゴリに分類されます。

健全性チェック

教師は同時に 2 つのクラスを教えることはできません
生徒は 2 つのレッスンを同時に受講することはできません
一部の教師は週に少なくとも 1 日は休暇をとらなければなりません
すべての曜日がタイムテーブルに含まれている必要があります
被験者 X は毎週ちょうど何時間も時間をとらなければなりません
...

環境設定

各教師のスケジュールは可能な限りコンパクトにする必要があります（つまり、教師は、可能であれば休憩せずに一日中ずっと仕事をしなければなりません）
休日のある教師は希望の曜日を表明できる必要があります
パートタイムで働く教師は、授業の最初に働くか終わりに働くかの希望を表明できる必要があります。
...

解決策が見つからないまま数年が経ちましたが（その間にいくつかのことを学びました...）、私はこれが NP の難しい問題のような匂いがすることに気づきました。

NP困難であることが証明されていますか？

これを解読する方法について誰かがアイデアを持っていますか?

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

問題をより詳細に特定するための小さな補足。これは、すべての生徒が異なるクラスに所属するイタリアの学校スタイルの教室に適用されます (例:1 年目のセクション A) と教師はクラス間を移動します。同じクラスの生徒は全員同じスケジュールを持っており、どのレッスンに参加するかを選択することはできません。

解決

私は、学生情報システムのスケジューラ部分で働く開発者の一人です。スケジューリング問題の元のアプローチでは、制約充足問題を解決するための遺伝的アルゴリズムを研究しましたが、最初は成功していましたが、問題の解決はそれほど複雑ではないことがわかりました（学校のスケジューリングワークショップに参加した後）

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

これにより、最初にマスタースケジュールを作成してから、必要に応じて人間が調整することができます。

スケジューラの現在の実装はperlで記述されていますが、以前にアクセスした他のオプションはPrologとCLIPS（エキスパートシステム）でした

他のヒント

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

問題を分割します：

教師、クラス、および設定のリストを作成し、ユーザーが開始点として使用する設定をマップに入力できるようにします。
リストから1つの要素をランダムに取り出し、マップ上のランダムな自由な位置に配置しますリストが空になるまで健全性チェックを通過しない場合。特定の反復で、健全性チェックを超えることなくマップ上に要素を配置できない場合、マップ上の2つの位置をシフトして再試行してください。
マップがいっぱいになったら、マップ上の位置を移動して結果を最適化します。

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

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

私は過去に同様の計画/スケジュールの問題に取り組んだことがありますが、この種の問題に最も適している AI テクニックは「制約ベースの推論」です。

これは基本的にローレンティ氏が提案したような強引な方法ですが、このアプローチには、効率的な順序で制約を適用して、実行不可能な解決策を迅速に失敗させる、つまり必要な計算を最小限に抑えることが含まれます。

「Constraint Based Reasoning」でグーグル検索すると、この手法とそのスケジューリング問題への応用に関するリソースがたくさん出てきます。

自分の質問に答える：

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

アルゴリズムに関するいくつかの言葉：FET 発見的アルゴリズムを使用して、配置順番に、アクティビティ最も難しいもの。できない場合解決策を見つける潜在的な不可能な活動なので、エラーを修正できます。アルゴリズムその場合、アクティビティを再帰的にスワップしますのためのスペースを作るために可能です新しいアクティビティ、または極端な場合には、バックトラックとスイッチの順序評価。重要なコードは src / engine / generate.cpp。メールしてください詳細については私に連絡するか、メーリングに参加してくださいリスト。アルゴリズムは人間の時刻表の操作、私考えてください。

リンク

「制約ベースの推論」のフォローアップ; WikipediaのStringent Softwareに率いられて、これら興味深い段落があるページ：

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

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

どのように行うか：

人口に2つのことを含める：

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

こうすることで、競合することはありません（2か所の教師、または同時に2つの科目を持つクラス）。

フィットネス関数には次のものが含まれます。

各教師が1週間に与えるタイムスロットの数。
教師が同じ日にいくつの時間枠を持っているか（1日を教えることができないため、これもバランスを取る必要があります）。
クラスに同じ日に同じ科目のタイムスロットがいくつあるか（1日は数学を学べません！）

バランスを取る必要があるため、それらすべての標準偏差を取得することがあります。

これが @Stringent Softwareのと同じ根拠をカバーしているかどうかはわかりません答え（名前は少し異なるため）ですが、制約プログラミング。時刻表の作成は、彼らの研究の1つのアプリケーションです。

クリスジェファーソン博士というプログラムを作成しました Minion はSourceForgeからダウンロードでき、C ++で書かれた非常に高速なブルートフォース制約問題ソルバーです

いくつかの制約が欠落している可能性があると思います。

可能な限り、認定されたクラスに教師をスケジュールすることを好むでしょう。

要求されたクラスが疑われ、それぞれのクラスで予想される人数が重要になる。

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

その後、何らかのソリューションを構築するためのエンジンを作成し、制約に従って適合性を評価します。

次に、楽しい遺伝的アルゴリズムの部分を投げて、遺伝子が混ざり合うにつれて時間とともに増加するフィットネスを得ることができるかどうかを確認できます。

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

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

同意します。楽しいチャレンジのようですね

これまでで最悪のオープンソースWebページの1つですが、プロジェクトは有望に見えます。 http://www.lalescu.ro/liviu/fet/

ウェブベースのアプローチ：
phpScheduleIt （学校固有ではありません）

この質問を見て、考えさせられましたこの問題について、そして遺伝的アルゴリズムはこの場合。しかし、それはきれいだろう可能性を変えるのは難しい健全性チェック規則を維持します。また、どのように私には明確ではありません互換性のない要件を区別します。

遺伝的アルゴリズムは、このような問題に非常に適しています。染色体のまともな表現（この場合は、おそらく利用可能なすべてのクラススロットを表すベクトル）を思いついたら、ほとんどそこにいます。

突然変異フェーズ中に健全性チェックを維持することについて心配する必要はありません。突然変異はランダムです。健全性チェックと優先度チェックはどちらも選択フェーズに属します。健全性チェックに失敗すると、個人のフィットネスは大幅に低下しますが、選好に失敗するとフィットネスはわずかに低下します。

互換性のない要件はまったく別の問題です。それらが完全に互換性がない場合、有用なものに収束しない人口が得られます。

頑張って。この種の問題を抱えた父親の息子であることが、私を最終的に研究グループに連れて行った理由です...

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

基本的な考え方は、NPでない場合はかなり近いということです。そのため、解決策があると仮定するのではなく、特定の時間枠内で最適なものを見つけることに着手します。私はすべての制約にそれらを壊すためのコストで重み付けします：健全性チェックには莫大なコストがあり、好みはより低いコストになります（しかし、より多くのブレークのために増加するので、一度壊すことは二度壊すコストの半分未満です）。

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

数千回の反復の後、許容できるソリューションに近づきます。

ただし、この種の問題には博士号を取得する研究グループがいるため、非常に良い会社にいると信じてください。

また、線形計画法の分野にも興味があるかもしれません。 simplex など。

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

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

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

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

頑張って。私のメモはすべて消えてしまい、販売できるソリューションを実装することはできませんでした。これは、新しい言語（Basic、Scheme、C、VB、C ++）を学んだときにコーディングし直した特別なプロジェクトでした

楽しんでください

i Prologプログラムをデータベースに接続することで、この問題を解決できることがわかりますそして、プログラムは、制約のセットを与えられたスケジュールを作ることができます abt＆quot;制約充足問題プロローグ＆quot;を読んでください

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow