常用的幾種高校排課算法

摘要：由于民辦高校辦學層次較多課程設置的靈活性比較強等特點給教務工作帶來很大的工作量，此時現行的手工排課的缺點就越來越突出。利用計算機進行排課能夠快速地得到滿足約束條件的可行結果，具有時間短人力省和質量高的優點，不但能使教務人員從繁雜的排課任務中解脫出來，而且對于教學的發展也起到非常重要的作用。本文主要介紹現在比較常用的幾種排課算法。

關鍵詞：民辦高校 排課 算法研究

當前或者之前的一段時間里，大多數民辦高校采用的是手動排課的方式進行課程安排，但是這種手動排課的方式只是適用于很小的教學集體，當學校學生基數比較大教師比較多的時候手動排課顯得非常不合適，運作效率非常低。利用計算機進行排課具有時間短人力省和質量高的優點，不但能使教務人員從繁雜的排課任務中解脫出來，而且對于教學的發展也起到非常重要的作用。下面介紹幾種常用的排課算法：

一、基于優先級的排課算法

從數學上講，排課問題是一個在時間、教師、學生和教室四維空間，以教學計劃和各種特殊要求為約束條件的組合規劃問題。其實質就是解決各因素之間的沖突。在設計算法時，為了降低課程調度的算法復雜性，主要采用了化整為零的思想及優先級算法。

（一）排課的預處理

等價類的劃分：將具有共同聽課對象的任務劃分在同一等價類中，在每個等價類之間只存在地點上的沖突，而沒有時間上的沖突。然后按照的大小，從大到小進行處理。等價類的劃分可以先按年級分，然后再按系別分。

教室分類：為了合理使用教室，我們采用了教室分類的辦法，以便盡可能在課程編排過程中避免上課人數少的課程盲目強占容量大的教室現象。

（二）時間預處理

1.構造時間模式庫

時間模式是根據教務人員的經驗，為各種周學時數不同的課程指定的一種時間組合方式.例如，一門課程的周學時數為4，那么它的時間組合方式可以有：“11”，“41”；表示該課程一周上兩次，分別為周一的12節和周四的12節L同時，為了達到較好的上課效果，也要對這些時間模式進行分級。

2.時間數組

為了表示班級、教師、教室的可排課時間，分別為他們建立一維數組。例如，某位教師的初始可排課時間數組為（123456 123456 123456 123456 123456）。其中共有五組數據，分別表示一周中的五天；而一組數據共有6個字符“1、2、3、4、5、6”分別表示一天中的六個時間單元。當為某位教師分配時間后，相應的那位字符就置為0L例如，某位教師的可排課時間數組為（020456 103456 003456 120456 023456），則表示這位教師在周一的12節和56節，周二的34節，周三的12節和34節，周四的56節，周五的12 節已經安排了課程，如果要再安排課程的話，就應該安排在非0的時間單元L對于班級和教室也可以進行同樣的處理，分別標出可排課時間。

（三）每一子類的排課處理

在對每個子類的排課處理中，我們結合了分治法、貪婪法、回溯法三者的思想。首先，根據分治法的思想把整個排課過程分成時間分配和教室分配兩個階段。然后，依據貪婪法的算法思想，在時間分配時，總是在尚未分配的時間單元中選擇上課效果最好的單元。而在時間分配發生死鎖時，會向上回溯搜索到發生沖突的最近一個記錄，然后對它進行重排以解決沖突。

（四）查找適當的時間模式

找到可排課時間后，就應根據課程的周學時數在時間模式庫中匹配適當的時間模式。完成以上工作后，就確定了課程的上課時間和地點。如果在處理中發生死鎖，則可根據回溯法的思想向上回溯搜索到發生沖突的最近一個記錄，然后對它進行重排以解決死鎖，如果仍不能解決死鎖問題，則可以將該課程信息輸出到沖突列表中。

（五）人工干預的處理

本算法所設計的人工干預過程有：等價類劃分中參數的設置，教室類型的設置，時間模式庫的設置，優先級函數中參數的設置。用戶可以根據自己的具體要求對這些參數和庫進行設置。另外，對于計算機排出的課程表，用戶也可以通過人機交互進行適當調整，從而得到用戶滿意的課程表。

二、沖突檢測算法

此算法對班級及教室劃分等價類，對學校資源進行了合理的利用，以課程為中心，進行搜索匹配，取最先匹配的值；具有占有空間少，運算速度快的特點。

三、遺傳算法

遺傳算法是一種隨機的全局搜索和優化算法。它從一個種群（Population）開始的，該群種可能是問題的一個可能潛在解集。而一個群種是由經過一系列基因（Gene）編碼（Coding）的一定數目的個體（Individual）組成。每個個體可以看作帶有某些特征的染色體實體（Chromosome）。生物學中，染色體是多個基因的集合，是遺傳物質的主要載體，決定其內部表現。實質上在內部，染色體是某種基因組合，比如染色體中控制皮膚頭發顏色這一特征的基因經過組合，就決定了生物個體的皮膚是白色的還是黑色的。因此在工作之初，需要把實體表現出來的信息特征抽象為一些位串來表示，實現外部特征和位串的映射，并且為了簡化采用二進制編碼。產生了初始種群之后，將“適者生存，優勝劣汰”的生物進化原理應用到實際問題的解決中。

四、PSO算法

PSO算法是基于群體的，根據對環境的適應度將群體中的個體移到好區域。將每個個體看作是具有唯一速度在多維搜索空間中飛行的沒有體積的粒子，每個個體的速度由它飛行的經驗和同伴的飛行經驗來動態調整。進一步分析出用來結束迭代過程的條件。

粒子群優化算法PSO（Particle Swarm Optimization）是由Kennedy和Eberhart通過對鳥群、魚群和人類社會某些行為的觀察研究，于1995年提出的一種新穎的進化算法與遺傳算法類似，它也是基于群體迭代。變異算子，群體在解空間中追隨最優粒子進行搜索。PSO的優勢在于簡單且容易實現，同時又有深刻的智能背景，既適合科學研究，又適合工程應用。鑒于PSO的發展歷史尚短，它在理論基礎與應用推廣上都還存在一些問題，有待解決。當前PSO算法存在的問題，如：收斂速度慢、求解多峰函數優化問題時易陷入局部極小以及早熟收斂的缺點，提出了一種新的基于專業化分工與協作的尋優策略，以期對PSO算法做出改進。

粒子群優化算法是一種基于群體迭代的進化算法，以往的PSO改進方法使PSO算法的性能得到了提高，但是沒能充分發揮粒子群的群體優勢，我們希望就是在現有方法的基礎上，充分利用粒子群的群體優勢， 使之較好地適應復雜的實際環境。

參考文獻

[1]李赫男.粒子群優化算法綜述[J].現代計算機，2009，301（2）：22-27.

[2]陳冬亮.排課的數學模型和算法在教務管理系統中的應用研究.電腦知識與技術，2006，（6）.

[3]陳潔.學校教務部門排課問題的數學模型及算法.1999，（3）：53-56.

[4]張忠.課程表問題中的應用[J].華南金融電腦.2007（06）.

（作者單位：1青島科技大學；2青島黃海學院）