6

大学の時間割を生成するアルゴリズムを実装する必要があります。私は多くのアルゴリズムを検索して見つけました。しかし、ここに問題があります。週ごとではなく、学期全体の時間割を生成するアルゴリズムが必要です。また、コースのパーツの定義済みの順序も考慮する必要があります。たとえば、演習 1 は講義 2 の後、講義 3 の前にする必要があります。何か提案はありますか?

ありがとう。

更新:
次の厳しい制約があります:
H1: 任意の時間帯に各部屋に 1 つのコース部分のみが割り当てられます。
H2: 部屋はすべての参加学生を収容でき、イベントに必要なすべての機能を満たします。
H3: 同時に複数のコースに参加する生徒はいません (少なくとも必須のコース)
。 H4: 同時に複数のコース部分を教える教師はいません。

ソフト制約は次のとおりです。
S1: コースの一部は、講師にとって都合の悪い時間帯に割り当てられるべきではありません。
S2: 教師のクラス間のギャップは最小限にする必要があります。
S3: 生徒のクラス間のギャップは最小限にする必要があります。
S4: クラスは、講師の好み (曜日と時間帯) を満たす必要があります。
S5: コースのパーツは、順序を事前に定義するようにスケジュールする必要があります。

例：
コース「ソフトウェアアーキテクチャ」 

Week No   Course    Room    Course Part   Day       Time
--------+---------+-------+--------------+----------+-----
Week 1:   SA        435     Lecture 1     Wednesday  8.15-11
Week 2:   SA        435     Lecture 2     Wednesday  8.15-11
Week 3:   SA        47      Lab 1         Monday     13-15
Week 3:   SA        436     Lecture 3     Wednesday  11-14
Week 4:   SA        243     Exercise 1    Monday     13-15
Week 5:   SA        436     Lecture 4     Wednesday  8.15-11
4

4 に答える 4

1

インターバル スケジューリングを検討することをお勧めします。演習の配置を許可する場所など、いくつかの制約を追加した修正版が必要になるようです。貪欲なアルゴリズムは通常、変更がかなり簡単で、基本的な IS アルゴリズムの変更済みバージョンがたくさんあります。

于 2010-06-20T06:47:19.847 に答える
0

ここで提案されたものの修正されたアルゴリズムで終わりました。反復フォワード アルゴリズムを使用してから、ソフト制約にシミュレーテッド アニーリングを適用しました。時間枠セットを変更して、週末と祝日を除いた学期の時間枠セット全体が含まれるようにしました。たとえば、学期が 6 週間あり、各週に 40 時間ある場合、タイムスロットのセットには 240 のタイムスロット全体が含まれます。

注文の制約も追加しました。この制約が満たされない場合、現在のソリューションの重みが高くなります。このようにして、アルゴリズムが順序にないコースを含むソリューションを選択するのを防ぎます。

于 2010-08-12T08:18:35.247 に答える
-1

IIRC のような問題は、アルゴリズムによって完全に解決できるわけではありません。

于 2010-06-20T15:34:09.857 に答える