多約束條件下排課系統模型的創建

黃嶺 秦春娣 陳偉

摘要：該文在探討國內外對排課問題研究的基礎上，結合學校的教學體制的特點，提出一個多約束條件下采用任務優先級、分治策略和貪心算法相結合的排課系統模型，并給出該模型關鍵庫的創建過程和后續加強改進的方向。

關鍵詞：教務;排課;多約束;算法模型

中圖分類號：TP312? ? ? 文獻標識碼：A

文章編號：1009-3044（2019）17-0064-03

開放科學（資源服務）標識碼（OSID）：

Abstract： On the basis of discussing the problems of course scheduling at home and abroad， and considering the characteristics of the school's teaching system， this paper puts forward a model of course scheduling system which combines task priority， divide-and-conquer strategy and greedy algorithm under multi-constraints， and gives the process of creating the key database of the model and the direction of further improvement.

Key words： Educational Administration; Course Scheduling; Multiple Constraints; Algorithmic Model

人工智能技術的不斷發展帶來的是人類雙手的解放，這也為人類可以擺脫繁雜重復性勞動，轉而從事思考創新帶來了前所未有的機遇。多年來排課問題一直是困擾學校教務的一個難題，而且以前的純手工安排課程現在看來也越來越無法適應當今飛速發展的教學需要，這一發展態勢要求學校必須綜合運用信息化手段來實現課程的安排與布局，以提高排課的效率和精度，同時也可以節約人工成本。排課問題是典型的資源調度問題，該問題已被證明為NP完全問題。課程表排課過程中的課程調度算法具有相當的難度[1]。

1 排課系統模型約束條件的分析

自動排課功能的實現其實是在總結傳統人工排課的經驗，建立模型讓計算機模擬人的思維來選擇合適的排課方案。排課問題是一個以各種特殊要求為約束條件，對時間、教師、班級和教室四個因素進行組合規劃的問題，簡而言之就是解決之間的沖突[2]。排課問題所涉及上課時間、上課教師、上課班級和上課教室等元素，不但需要符合已制定的教學計劃，而且還要盡可能滿足各種特殊要求，這是一個組合規劃的問題，其實是要調和各元素之間的矛盾沖突，換言之就是要借助計算機技術權衡各種制約條件，最終達到課程安排合理化的方案。

經過整理后可把排課過程中的約束條件分為三種：基本硬約束、硬約束和軟約束。

1）基本硬約束（Base-hard Constraints）是指教師、班級和教室在時間上不可發生的沖突，包括“同一時間同一班級不能上兩門不同的課程”;“同一時間同一教師不能上兩門不同課程”;“同一時間同一教室不能上兩門不同課程”，這些是排課最基本的約束條件，也是所有排課模型都會涉及的約束條件。

2）硬約束（Hard Constraints）是指根據各個學校的實際需求，在排課時必須遵循的原則，沒有它的排課也就沒有實際意義了。比如“課程按照最小兩節或四節進行”;“課程的總周數和周課時有要求”;“課程有特定教學場所和資源的要求”;“教室大小保證能容納下班級學生數”;“可手工預排某些課程”;“考慮多個校區教室間的扭轉時間”;“體育課不排1-2節”;“實踐類課程特殊安排方式”。

3）軟約束（Soft Constraints）是指在排課過程中能滿足最好，不能滿足無礙的約束條件。它的違反與否往往取決于排課模型完成的程度。比如“一周內每個班級的課程分布盡可能均勻”;“教師希望在某些時間段上課”;“教師不希望一天連續上六節及以上的課”;“給各時間段設置優先級”;“上下午中間課程切換教室之間的距離盡可能短”。

2 排課系統模型算法的分析

當前主流的排課算法，主要包括回溯算法、遺傳算法、貪婪算法、模擬退火算法、蟻群算法等，下面對這五種常用算法的特點加以描述。

1）回溯算法（backtracking algorithm）在求問題的所有解時，要回溯到根，且根的所有子都已被搜索過才結束;而在求問題的任一解時，只需搜索到問題的一個解就可結束。其優勢是程序結構明朗，易于理解;占用空間小;適用于解決組合數較大但有限的問題。其不足體現在時間復雜度較大，回溯層次多時過于耗時。

2）遺傳算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。其優勢是快捷簡便易操作;具有并行計算能力和并行性;容錯性強;可擴展性良好。其不足體現在缺乏靈活性;算法較為復雜，易過早收斂;約束增多效率下降。

3）貪心算法（greedy algorithm）是采用從頂向下、依次迭代的方法做出繼代選擇，每次迭代都會把所要解決問題縮小規模。其優勢是具有不可回溯性，有后效性;能在很低的時間復雜度下得到局部最優解。其不足該種算法側重明顯，無法從全局層面考慮均衡優化。

4）模擬退火算法（Simulated annealing algorithm）是來源于固體退火原理，是一種基于概率的算法。其優勢是計算過程較簡單;在約束條件少的前提下，能很快獲得最優解;適用于并行處理。其不足在于較難選擇參數，資源開銷相對較大;執行時間長，收斂速度慢;不易得到全局最優解。

5）蟻群算法（ant colony optimization）是一種用來尋找優化路徑的概率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發現路徑的行為。其優勢是健壯性明顯;全局搜索能力強大;并行實現方便。其不足是執行效率較低，搜索時間長; 容易出現停滯現象[3]。

3 排課系統模型的建立

通過對常用的幾個算法的比較，排課系統模型的建立可采用任務優先級、分治策略和貪心算法相結合的算法模型，這樣一來可以減少單一算法過于側重局部，無法顧及全局均衡的問題，二來還可降低自動排課時課程調度產生的邏輯復雜性。任務優先級考慮運用在課程優先級調度時，根據教學計劃建立優先級公式為每門課程劃分優先級別，然后依據優先級公式所得出的順序從高到低進行課程調度;而在設計時間模型庫時，也采用任務優先級的方法，將歸納總結的最佳上課的時間組合模式設置為較高優先級。分治策略主要運用在借助分治策略將排課過程分成時間分配和教室匹配兩個階段來完成。貪心算法主要運用在時間分配階段，借助貪心算法的算法思想，在尚未分配的時間模型中選擇優先級別較高的時間模式來進行時間分配，以確保相應課程的教學效果最佳。

3.1 時間模型庫的創建

排課系統地最終目標還是要以學生上課的最佳教學效果為根本。從之前分析的基本硬約束、硬約束和軟約束條件已看出諸如：根據教學和學生學習的認知規律，一天或一周中哪些時間段的學習效果最佳;一周多次上課，給學生預留復習消化知識的間隔時間;特殊資源要求課程考慮優先排課。這些就需要排課人員需要具備豐富的排課經驗，并且能夠依據教學計劃合理規劃、組建時間組合，劃分相應的時間模式優先級，還可根據后續排課過程出現的異常及時調整時間模型庫的相應參數。

具體來說可以根據不同的課時要求把課程自高到低分為：K3（理論類課程：學習認知規律效果相對較好的上午時段）、K2（實踐類課程：上下午時間段都可）、K1（類似體育課程：一般不安排在1-2節和晚上）幾種等級。然后根據每種等級課程不同周課時數的所有可能的時間組合進行優先級分級T1、T2……，并按照優先級的高低順序依次存入時間模型庫。K3級別課程的2課時、4課時、6課時時間分配模型如表1所示。

上表中J11、J12……表示相應每天的節次，如“J11”中的第一個“1”表示周一，第二個“1”表示當天的1-2節課;“J22”中的第一個“2”表示周二，第二個“2”表示當天的3-4節課;“J54”中的“5”表示周五，“4”表示當天的7-8節課，其他依次類推。

3.2 課程優先級計算模型的確定

課程優先級計算模型主要結合各個學校教學計劃和實際需求而定。分析大部分學校的教務需求，主要包括以下幾個方面：一是開課班級較多的，如公共基礎課應該優先安排;二是純理論課或專業理論課應該優先安排;三是周課時較多的課程應該優先安排;四是課程需要特殊功能教學場所的，如階梯大教室、多媒體、機房等應該優先安排;五是課程對上課時間有特定需求的應該優先安排。結合這些需求，可建立如下課程優先級計算模型公式：

公式里的K（n）表示前面已經設置的三種課程等級：K3（理論類課程：學習認知規律效果相對較好的上午時段）、K2（實踐類課程：上下午時間段都可）、K1（類似體育課程：一般不安排在1-2節和晚上）;W（n）表示相應課程的周課時數;C（n）表示相應課程的開課班級數量;R（n）表示相應課程在教學場所或上課時間上的特定要求。這里的P1～P4可根據具體需要進行參數的微調，以適應教學需要，保證排課完成率[4]。

3.3 各排課時間數組模型的確定

排課模型初始化時需要給教師、教室和班級分別創建給建立排課時間數組。以某教室初始排課為例：建立某教室初始排課時間數組模型為（12345? 12345 12345 12345? 12345）。每一組數據中的“1、2、3、4、5”分別表示一周中的五天，而其中總共六組數據分別表示一天中的五個教學時間，當為某教室分配時間后， 相應的教學時間位就置0。例如， 某教室的排課時間數組為（ 01111100111111111011 11110） ， 則表示該教室在周一的1-2 節， 周二的3-4 節， 周三的3-4節和7-8 節，和周五的9-10節已經安排了課程， 剩下來的非0教學時間是還可以安排課程的。同樣的方法可完成對教師和班級的排課時間數組創建。

3.4 排課系統模型運行流程

完成各數組及庫的模型創建、初始化后，先使用之前建立的課程優先級計算模型公式對所有課程的優先級進行判斷，取出獲得優先級最高的課程開始排課;把查詢出的該課程班級的排課時間數組與該課程的排課時間數組相乘，得到上該課程班級的排課時間數組;然后再與該課程任課教師的時間數組相乘，得到該教師擔任該班課程的時間數組;接下來根據該課程的計劃課時和之前建立的時間模型庫相匹配;最后根據該課程對教學場地的需求查找合適的教室。

4 后期排課模型的改進

關于課程優先級值的定義還可以結合問卷調研形式綜合得出，這樣更加科學合理;增加排課滿意度參考指數并加入歷史排課經驗參考模型;涉及功能性教室的選擇，在資源緊張的情況下，班級人數或機位數可以有所寬松（可以選擇區間或臨界值的方式），以適應不斷變化的排課需求。

參考文獻：

[1] 鐘嘉鳴， 高春鳴. 智能排課系統及多約束條件下的資源分配模型[J]. 教育信息化， 2002（4）： 56-58.

[2] 梅曉勇. 基于動態規則構造的排課系統設計與實現[J]. 微機發展， 2002（6）： 12-14.

[3] 耿振余. 軟計算方法及其軍事應用[M]. 北京： 國防工業出版社， 2015（12）.

[4] 楊興旺. 基于回溯法的排課算法[J]. 電腦知識與技術， 2009（19）.

【通聯編輯：謝媛媛】