基于人工智能的自動排課算法

摘要：提出了一種基于人工智能的自動排課算法。

關鍵詞：自動排課 回塑算法 數據庫

中圖分類號：G434 文獻標識碼：B 文章編號：1002－2422(2008)03－0070－02

1 數學模型

班級課程表模型：每周五天，每天六節課，每兩節課連在一起上一門課，1至15表示節次；星期一下午固定為班會課，1至15用來將節次數字化，見表1。

每周為28節課需要排，設排4個班，每個班開四門課，而且由四個老師來上課，即每個老師全排滿課的情況下來排課，實際中這種情況是極少，教師不可能所有的時間都在上課。班級為A，B，C，D；教師為a，b，c，d：教師a授a1，b授b1，c授c1，d授d1課程具體的節數分配見表2。

2 排課算法

(1)數據初始化工作：

(2)設置好每一位教師每天上課可排的節數；

(3)設置好班級每天可排課的節數：

(4)按班級為單位排好記錄：

(5)讀入一條記錄；

(6)計算記錄科目的次數；

(7)按以下算法將其填入班級課表中，并在教師課表中，并在班級次當天可用課次數和教師當天可用課次數中減1；

(8)先按班級和教師中的可用節次對首先要排課的周次進行排序，按由大到小排序，即保證每次排課都是班級中最少課的周次，和教師上課最少課的天；

(9)對于(1)中找出的周次進行具體的節次進行轉換，由于是最空課的周次。因此肯定有空的節次；

(10)對應班級表中的節次i位置是否為空，Y則轉到(11)，N則轉到(9)；

(11)對應教師標志位是否為空，Y轉到(12)，N轉到(9)：

(12)在班級課程表和教師課程表中填入課程，班級和教師中的可用節次相應減1，k=k－1：

(13)k=0? Y則轉到(5)，N則進入(8)；

(14)如果產生沖突，記錄下產生沖突的教師，并設置一個優先值，則回到(4)對當前班級進行重排，重排時先排這個發生沖突的教師，當然要恢復排之前的數據。

3 程序實現

3.1排課所用的數據庫結構

排課的過程中采用了大量對表格的操作，所有的操作都用一個數據庫中的表格來操作；數據庫中的表有如下幾個表：Gbxx(用來錄入教師上課的基本信息)、Bikcb(用來存放排好的班級課程)、Bzxx(用來存放排好的教師課程)、BgtianBzxx(用來標志班級中那天空課的節次)、Jstian-ShangkeCs(用來標教師中可排的空課節次)、Px(用來對周次進行排序，即按班級空課次數和教師空課次數來排序)。

3.2產生排課班級節次沖突的處理方式

對于具體班級節次的沖突，采用了在班級當天排課中隨機產生當天節次的方式來處理沖突，班級每次排課的周次都是最空的周次所以肯定會有一節課可用的，從(10)和(11)跳轉到(9)。由于(9)中的周次每天所對應的節次最多為3，因此采用隨機的方式來遍歷，在程序中使用一個計數器，設置值為50次，也就說3次節次在50次隨機數中肯定都會出現。

3.3產生排課教師節次沖突的處理方式

當教師發生沖突時給發生沖突的教師一個優先值，這里采用回塑算法，即清除這個班的所有所排的課程，重新排這個班的課，重排時與前面有一點不同是，按優先值的高低來進行排序。

4 排出的結果

設計的軟件不但對于模型能很好地排出結果，而且對于上百個教師的課程進行排課設計也能很快地排出較滿意的結果，見表3。