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

關(guān)鍵詞：民辦高校 排課 算法研究

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

一、基于優(yōu)先級的排課算法

從數(shù)學(xué)上講，排課問題是一個在時間、教師、學(xué)生和教室四維空間，以教學(xué)計(jì)劃和各種特殊要求為約束條件的組合規(guī)劃問題。其實(shí)質(zhì)就是解決各因素之間的沖突。在設(shè)計(jì)算法時，為了降低課程調(diào)度的算法復(fù)雜性，主要采用了化整為零的思想及優(yōu)先級算法。

（一）排課的預(yù)處理

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

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

（二）時間預(yù)處理

1.構(gòu)造時間模式庫

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

2.時間數(shù)組

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

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

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

（四）查找適當(dāng)?shù)臅r間模式

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

（五）人工干預(yù)的處理

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

二、沖突檢測算法

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

三、遺傳算法

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

四、PSO算法

PSO算法是基于群體的，根據(jù)對環(huán)境的適應(yīng)度將群體中的個體移到好區(qū)域。將每個個體看作是具有唯一速度在多維搜索空間中飛行的沒有體積的粒子，每個個體的速度由它飛行的經(jīng)驗(yàn)和同伴的飛行經(jīng)驗(yàn)來動態(tài)調(diào)整。進(jìn)一步分析出用來結(jié)束迭代過程的條件。

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

粒子群優(yōu)化算法是一種基于群體迭代的進(jìn)化算法，以往的PSO改進(jìn)方法使PSO算法的性能得到了提高，但是沒能充分發(fā)揮粒子群的群體優(yōu)勢，我們希望就是在現(xiàn)有方法的基礎(chǔ)上，充分利用粒子群的群體優(yōu)勢， 使之較好地適應(yīng)復(fù)雜的實(shí)際環(huán)境。

參考文獻(xiàn)

[1]李赫男.粒子群優(yōu)化算法綜述[J].現(xiàn)代計(jì)算機(jī)，2009，301（2）：22-27.

[2]陳冬亮.排課的數(shù)學(xué)模型和算法在教務(wù)管理系統(tǒng)中的應(yīng)用研究.電腦知識與技術(shù)，2006，（6）.

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

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

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