3

バックグラウンド

（アルゴリズムだけが気になる場合は、これをスキップしてください）

私が働いている大学では、私たちの学部で最大の問題の1つは教室のスケジュールです。説明のため、および問題の範囲をレイアウトするために、現在のスケジューリング方法は次のとおりです。

  1. 教授は、彼らが教えたいクラスのリストを、彼らが教えたいと思う時間枠とともに、優先度の高い順に（最も望ましいものから最も望まれないものへ）ランク付けしてくれます。
  2. 管理者は、私たちが割り当てることができる部屋のリストと、それらの部屋が私たちの部門で使用できる時間とともに提供します。
  3. 私たちは、さまざまな教授の好みを考慮に入れようとして（最初は）部屋に教授を割り当て始めます。
  4. 必然的に、対立が生じ、教授は変更を求め始め、計画は教授番号30あたりのどこかでバラバラになります。その時点で、基本的に私たちが収まるところならどこでも部屋を割り当て始め、しわくちゃの紙片はいたるところにあり、誰も幸せではありません。（なぜあなたのクラスが木曜日の午前9時30分であるのに、隔日で午後4時であるのか疑問に思ったことがあるなら、今あなたは知っています）

私は、ソフトウェアがこれをより最適に行うことができるかどうかを静かに調査するように求められました。

実際の質問

次の基準が満たされるように、リソースのセットを効率的にスケジュールするアルゴリズムはありますか？

  • アルゴリズムは、2人の教授を同時に同じ部屋に割り当ててはなりません。
  • すべての教授に部屋/時間が割り当てられるまで、タスクは完了しません。
  • アルゴリズムは、利用可能なタイムスロットの量に対して教授が多すぎることを心配する必要はありません。（私たちはそれほど資金がありません。）
  • 可能な限り、アルゴリズムは個々の教授のスケジュール設定を尊重する必要があります。

私はこれを最初に尋ねることはできないような気がします。これには効率的なアルゴリズムがありますか、それともブルートフォースでしかできないような問題ですか？

4

1 に答える 1

1

しばらくの間、時間割とスケジューリングの問題について書かれた論文があります。「timetablingpackage」という2つの単語をウェブで検索すると、このための商用パッケージやその他のパッケージが見つかります。

洗練された解決策を模索するけいれん的な試みにもかかわらず、人々がアドホックな解決策を実装するかなり基本的なプログラムを書くことになった問題領域を知っています-この分野での制度的学習の明らかな兆候はありませんでした。これについて述べられている理由は、特に問題を解決できず、制約を緩和する必要がある場合に、ユーザーがプログラムが決定を下す理由を理解する必要があるためです。

http://en.wikipedia.org/wiki/Assignment_problemを使用して、特定のコースを特定の部屋のタイムスロットに割り当てることで、特定の問題（最初に聞こえるほど単純な場合）を解決できる可能性があります。タスクへのエージェントの代わりに。

プログラムまたはアルゴリズムは、入力内の制約の相対的な順序によって影響を受ける可能性があります。特に、2つのソリューションが同等に優れている場合、同点に遭遇した場合はそうです。私はこれをチェックするために含まれ、もしそうなら、少なくともバイアスをランダムな運に変えようとして、プログラムまたはアルゴリズムに提示する前に入力をランダムに並べ替えます。

于 2012-12-13T05:01:14.780 に答える