多約束條件下排課系統(tǒng)模型的創(chuàng)建

黃嶺 秦春娣 陳偉

摘要：該文在探討國內(nèi)外對(duì)排課問題研究的基礎(chǔ)上，結(jié)合學(xué)校的教學(xué)體制的特點(diǎn)，提出一個(gè)多約束條件下采用任務(wù)優(yōu)先級(jí)、分治策略和貪心算法相結(jié)合的排課系統(tǒng)模型，并給出該模型關(guān)鍵庫的創(chuàng)建過程和后續(xù)加強(qiáng)改進(jìn)的方向。

關(guān)鍵詞：教務(wù);排課;多約束;算法模型

中圖分類號(hào)：TP312? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）17-0064-03

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（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

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

1 排課系統(tǒng)模型約束條件的分析

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

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

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

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

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

2 排課系統(tǒng)模型算法的分析

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

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

2）遺傳算法（Genetic Algorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。其優(yōu)勢(shì)是快捷簡(jiǎn)便易操作;具有并行計(jì)算能力和并行性;容錯(cuò)性強(qiáng);可擴(kuò)展性良好。其不足體現(xiàn)在缺乏靈活性;算法較為復(fù)雜，易過早收斂;約束增多效率下降。

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

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

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

3 排課系統(tǒng)模型的建立

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

3.1 時(shí)間模型庫的創(chuàng)建

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

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

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

3.2 課程優(yōu)先級(jí)計(jì)算模型的確定

課程優(yōu)先級(jí)計(jì)算模型主要結(jié)合各個(gè)學(xué)校教學(xué)計(jì)劃和實(shí)際需求而定。分析大部分學(xué)校的教務(wù)需求，主要包括以下幾個(gè)方面：一是開課班級(jí)較多的，如公共基礎(chǔ)課應(yīng)該優(yōu)先安排;二是純理論課或?qū)I(yè)理論課應(yīng)該優(yōu)先安排;三是周課時(shí)較多的課程應(yīng)該優(yōu)先安排;四是課程需要特殊功能教學(xué)場(chǎng)所的，如階梯大教室、多媒體、機(jī)房等應(yīng)該優(yōu)先安排;五是課程對(duì)上課時(shí)間有特定需求的應(yīng)該優(yōu)先安排。結(jié)合這些需求，可建立如下課程優(yōu)先級(jí)計(jì)算模型公式：

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

3.3 各排課時(shí)間數(shù)組模型的確定

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

3.4 排課系統(tǒng)模型運(yùn)行流程

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

4 后期排課模型的改進(jìn)

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

參考文獻(xiàn)：

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

[2] 梅曉勇. 基于動(dòng)態(tài)規(guī)則構(gòu)造的排課系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J]. 微機(jī)發(fā)展， 2002（6）： 12-14.

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

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

【通聯(lián)編輯：謝媛媛】