張宇

摘 要：為提高高校實(shí)驗(yàn)室的綜合利用率、減輕其管理人員的工作量，更為實(shí)現(xiàn)排課周延、選課方便、上課精準(zhǔn)的目標(biāo)，有必要并且迫切需要利用實(shí)驗(yàn)室信息管理系統(tǒng)來(lái)進(jìn)行排課，以系統(tǒng)自動(dòng)排課代替?zhèn)鹘y(tǒng)手工排課。該文重點(diǎn)分析基于實(shí)驗(yàn)室信息管理系統(tǒng)的排課算法設(shè)計(jì)，闡述設(shè)計(jì)原則，提出關(guān)鍵問(wèn)題，探討可行性和有效性。

關(guān)鍵詞：排課算法 設(shè)計(jì)原則 算法流程

中圖分類(lèi)號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2016）07（b）-0144-02

近年來(lái)，高校擴(kuò)招帶來(lái)了教育規(guī)模擴(kuò)大，高校在校學(xué)生數(shù)量增多，與此同時(shí)，高校畢業(yè)生動(dòng)手能力弱、實(shí)踐能力差也已成為不爭(zhēng)的事實(shí)，并影響著他們順利實(shí)現(xiàn)就業(yè)。因此，實(shí)驗(yàn)教學(xué)改革、實(shí)驗(yàn)室建設(shè)和管理也理所當(dāng)然成為高等教育工作的重點(diǎn)之一。傳統(tǒng)的手工排課已經(jīng)不能適應(yīng)迅猛發(fā)展和需求旺盛的實(shí)驗(yàn)教學(xué)需要，這一發(fā)展態(tài)勢(shì)要求高校必須采用計(jì)算機(jī)信息管理系統(tǒng)來(lái)實(shí)現(xiàn)實(shí)驗(yàn)室的課程安排與布局，以提高排課的效率和精度，同時(shí)也節(jié)約人工成本。

1 實(shí)驗(yàn)室排課系統(tǒng)應(yīng)實(shí)現(xiàn)的基本功能

依托實(shí)驗(yàn)室信息管理系統(tǒng)的實(shí)驗(yàn)室排課系統(tǒng)應(yīng)具備以下功能：系統(tǒng)支持管理員、教師和學(xué)生三種不同身份人群的登錄；通過(guò)排課系統(tǒng)，實(shí)驗(yàn)室管理員可以做到審核課程安排、自定義排課和查看課程安排信息；實(shí)驗(yàn)課授課教師可以提交課程安排、查詢(xún)課程安排和查看實(shí)驗(yàn)室信息；成為注冊(cè)用戶(hù)的學(xué)生，可以查詢(xún)課程安排、修改個(gè)人信息。以上由登錄權(quán)限模塊進(jìn)行支撐，此模塊包含了登錄界面和登錄驗(yàn)證處理內(nèi)容。系統(tǒng)基礎(chǔ)數(shù)據(jù)模塊集成了學(xué)校學(xué)生及教師的個(gè)人信息、學(xué)校開(kāi)設(shè)的實(shí)驗(yàn)課程、學(xué)校現(xiàn)有的院系班級(jí)和實(shí)驗(yàn)教室等信息。此外，系統(tǒng)還應(yīng)設(shè)置信息維護(hù)模塊，通過(guò)此模塊對(duì)學(xué)生、教師和班級(jí)排課信息進(jìn)行修改、刪除等維護(hù)操作。當(dāng)然，查詢(xún)?yōu)g覽模塊也必不可少，根據(jù)關(guān)鍵詞等查詢(xún)條件，可以快速、準(zhǔn)確地查找到需要的信息。

2 實(shí)驗(yàn)室排課算法設(shè)計(jì)應(yīng)遵循的原則

高校實(shí)驗(yàn)室信息管理系統(tǒng)自動(dòng)排課功能的實(shí)現(xiàn)，是在借鑒傳統(tǒng)人工排課經(jīng)驗(yàn)的基礎(chǔ)上，利用計(jì)算機(jī)來(lái)選擇合適的排課方案。排課問(wèn)題涉及到實(shí)驗(yàn)時(shí)間、授課教師、上課學(xué)生和實(shí)驗(yàn)室等要素，不僅要依據(jù)學(xué)期初既定的教學(xué)計(jì)劃，還要盡量滿足各種特殊要求（如：特殊時(shí)間、特定教室、排課等級(jí)），這是組合規(guī)劃問(wèn)題，其實(shí)是解決各個(gè)要素之間的沖突，也可以說(shuō)是一種用信息技術(shù)對(duì)抗和調(diào)和各種制約條件以達(dá)到課程安排最合理最優(yōu)化的方案。對(duì)照實(shí)驗(yàn)室排課的一些約束性條件，經(jīng)過(guò)整理、比較和歸納，發(fā)現(xiàn)編排高校實(shí)驗(yàn)室課程一般應(yīng)遵循以下基本原則。

（1）排課“不沖突”原則。保證實(shí)驗(yàn)室排課不沖突，具體包括實(shí)驗(yàn)場(chǎng)地（機(jī)房）不沖突、實(shí)驗(yàn)教師上課時(shí)間不沖突、實(shí)驗(yàn)學(xué)生上課時(shí)間不沖突等，這是硬性條件，是基本規(guī)則，一旦違反了，就會(huì)釀成教學(xué)事故。

（2）排課實(shí)驗(yàn)室“基礎(chǔ)達(dá)標(biāo)”原則。實(shí)驗(yàn)室排課要充分考慮不同實(shí)驗(yàn)室的軟硬件條件，要根據(jù)實(shí)驗(yàn)室的基本功能合理排課，保證排定的實(shí)驗(yàn)室“達(dá)標(biāo)”，符合實(shí)驗(yàn)要求，為實(shí)驗(yàn)課提供“合規(guī)”“合理”的場(chǎng)地。

（3）排課“效用最優(yōu)”原則。要對(duì)實(shí)驗(yàn)室、實(shí)驗(yàn)課程、實(shí)驗(yàn)師生進(jìn)行調(diào)查研究，歸納“需求”，盤(pán)點(diǎn)“供給”，做好調(diào)度，實(shí)現(xiàn)各要素的有效對(duì)接、無(wú)縫銜接，這樣才能發(fā)揮實(shí)驗(yàn)室效用的最大化、最優(yōu)化，才能讓實(shí)驗(yàn)課上出效率、講出“效果”。比如，同一專(zhuān)業(yè)不同班級(jí)的實(shí)驗(yàn)課程進(jìn)度要相當(dāng)，實(shí)驗(yàn)教室的類(lèi)別、功能要相同，實(shí)驗(yàn)教師也要相對(duì)固定。

3 在實(shí)際操作中對(duì)高校實(shí)驗(yàn)室排課算法的設(shè)計(jì)

3.1 選擇算法的問(wèn)題

目前，尚未有比較成熟的排課算法，也沒(méi)有通用的排課系統(tǒng)。在該文中，筆者以回溯算法的結(jié)構(gòu)為例進(jìn)行實(shí)驗(yàn)室排課。因?yàn)樵S多復(fù)雜的、規(guī)模較大的問(wèn)題都可以使用回溯法來(lái)進(jìn)行解決，回溯算法有“通用解題方法”的美稱(chēng)?；厮菟惴刂平Y(jié)構(gòu)的核心思想就是一點(diǎn)：“試著走，走不通時(shí)就回頭”。這種算法向前搜索時(shí)是依據(jù)選優(yōu)條件來(lái)求結(jié)果的，經(jīng)過(guò)搜索比對(duì)，獲知原有方案不符合要求或不是最優(yōu)方案時(shí)，就后退進(jìn)行二次選擇、重新選擇，再次嘗試探尋最優(yōu)路徑，直至找到。回溯法就是一種選優(yōu)搜索法。

3.2 優(yōu)先排課的問(wèn)題

實(shí)驗(yàn)室信息管理系統(tǒng)其排課功能一般是以預(yù)約排課為實(shí)現(xiàn)方式的，即實(shí)驗(yàn)課程上課時(shí)間由學(xué)校教務(wù)系統(tǒng)事先進(jìn)行排定，或由實(shí)驗(yàn)教師提前自行約定。這樣，當(dāng)實(shí)驗(yàn)教師或相關(guān)教務(wù)人員一旦確定上課時(shí)間后，通過(guò)登錄信息系統(tǒng)來(lái)進(jìn)行實(shí)驗(yàn)室預(yù)約操作，系統(tǒng)會(huì)自動(dòng)依據(jù)實(shí)驗(yàn)課程所需要的實(shí)驗(yàn)室參數(shù)進(jìn)行排課。參數(shù)包括機(jī)位數(shù)量、硬軟件環(huán)境等。一般情況下，會(huì)綜合考慮選課人數(shù)、課程性質(zhì)、實(shí)驗(yàn)室條件、實(shí)驗(yàn)室設(shè)備的使用年限等因素。比如依據(jù)選課人數(shù)安排實(shí)驗(yàn)，應(yīng)“先大后小”，優(yōu)先考慮大班。依據(jù)課程性質(zhì)安排實(shí)驗(yàn)，應(yīng)必修實(shí)驗(yàn)課優(yōu)于選修實(shí)驗(yàn)課。依據(jù)實(shí)驗(yàn)室條件安排實(shí)驗(yàn)，應(yīng)硬件要求在前，操作系統(tǒng)次之，教學(xué)軟件最后。依據(jù)實(shí)驗(yàn)室設(shè)備使用年限安排實(shí)驗(yàn)，一般優(yōu)先選用使用年限較短、設(shè)備較先進(jìn)的實(shí)驗(yàn)室。

3.3 實(shí)現(xiàn)算法流程問(wèn)題

（1）依據(jù)前述優(yōu)先排課的方式，通過(guò)搜索，對(duì)當(dāng)下的排課訴求安排空余的實(shí)驗(yàn)室進(jìn)行解決。

（2）當(dāng)排課訴求沒(méi)有足夠、適當(dāng)?shù)目沼鄬?shí)驗(yàn)室滿足時(shí)，即是當(dāng)前擴(kuò)展結(jié)點(diǎn)不能繼續(xù)往縱深的方向移動(dòng)時(shí)，這個(gè)時(shí)候，就考慮往回移動(dòng)，可以移動(dòng)到最近的活結(jié)點(diǎn)處，活結(jié)點(diǎn)同時(shí)被認(rèn)可為當(dāng)前擴(kuò)展結(jié)點(diǎn)。

對(duì)（1）（2）所列的流程進(jìn)行不斷重復(fù)、試驗(yàn)，就可以找到符合系統(tǒng)要求的結(jié)果。

4 排課過(guò)程中“死鎖”問(wèn)題的解決

所謂“死鎖”，是指雖然進(jìn)行了準(zhǔn)確有效輸入，但排課訴求仍沒(méi)有足夠的資源進(jìn)行支撐。解除“死鎖”是排課算法要解決的關(guān)鍵問(wèn)題，關(guān)鍵問(wèn)題的重點(diǎn)是解決排課時(shí)間沖突問(wèn)題。為什么會(huì)出現(xiàn)“死鎖”問(wèn)題呢，究其原因，資源約束條件與排課原則之間的沖突是最主要的。舉個(gè)例子，如果在排課過(guò)程中，某一班級(jí)的某一課程一直沒(méi)有符合條件的教師或?qū)嶒?yàn)場(chǎng)所，也就是說(shuō)在某班級(jí)能夠上某一實(shí)驗(yàn)課程的時(shí)間段里，找不到空閑的教師或教室，那么這門(mén)課程就不可排，帶來(lái)的后果就是接下來(lái)的所有課程都安排不了，這個(gè)時(shí)候就出現(xiàn)了“死鎖”現(xiàn)象。此次課程的安排受到前期安排課程的制約，同時(shí)也影響著后期課程的安排，這個(gè)時(shí)候就需要返回上一門(mén)課程的安排，通盤(pán)統(tǒng)籌考慮，重新作出調(diào)整。當(dāng)發(fā)生“死鎖”現(xiàn)象時(shí)，一般由管理員根據(jù)系統(tǒng)提示的原因來(lái)進(jìn)行人工調(diào)整。具體有補(bǔ)充安裝教學(xué)軟件、對(duì)實(shí)驗(yàn)室信息管理系統(tǒng)的相關(guān)數(shù)據(jù)進(jìn)行更新以及調(diào)整課程時(shí)間、增加教師、教室資源等。

5 結(jié)語(yǔ)

計(jì)算機(jī)技術(shù)在各個(gè)管理領(lǐng)域得到了深入而廣泛的應(yīng)用，依托計(jì)算機(jī)技術(shù)的實(shí)驗(yàn)室信息管理系統(tǒng)的排課功能如果開(kāi)發(fā)得好、利用得好，不僅可以整合各種課程、師資、場(chǎng)地、設(shè)備資源，還有助于高校實(shí)驗(yàn)室實(shí)現(xiàn)規(guī)范化、科學(xué)化管理。基于回溯算法的實(shí)驗(yàn)室排課系統(tǒng)，不失為一種較好的路徑選擇，當(dāng)然也可以基于遺傳算法這一解決方案來(lái)進(jìn)行排課問(wèn)題的研究，原理雖有差異，但所要遵循的基本原則大體相似、所要追求的最終目標(biāo)基本一致。隨著研究的不斷深入和實(shí)踐的廣泛應(yīng)用，實(shí)驗(yàn)室自動(dòng)排課系統(tǒng)一定會(huì)越來(lái)越成熟，越來(lái)越“給力”，在實(shí)驗(yàn)室管理和實(shí)驗(yàn)課程建設(shè)中發(fā)揮越來(lái)越重要的作用。

參考文獻(xiàn)

[1] 劉智萍.高校機(jī)房排課系統(tǒng)研究[J].軟件導(dǎo)刊，2014，13（10）：97-99.

[2] 徐紅麗，羅奇，張芳.實(shí)驗(yàn)室排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2015（15）：58-59.

[3] 劉海琴，周勝.基于回溯算法的實(shí)驗(yàn)室排課系統(tǒng)的分析與設(shè)計(jì)[J].電腦與信息技術(shù)，2012，20（5）：54-56.