肖清雷

摘 要:在學(xué)分制教學(xué)管理模式下,由于學(xué)生選課的自主性和多樣性,相同專(zhuān)業(yè)的學(xué)生選課也不盡相同,給教學(xué)管理帶來(lái)一個(gè)極大難題。隨著高校擴(kuò)建和多校區(qū)格局的形成,其考試安排問(wèn)題尤為突出。本系統(tǒng)應(yīng)用了貪婪算法對(duì)考試時(shí)間安排這一實(shí)例進(jìn)行最優(yōu)化求解,同時(shí)合理地解決了考場(chǎng)分配、監(jiān)考安排問(wèn)題,成為智能考務(wù)管理有效實(shí)施的關(guān)鍵,且成效顯著。

關(guān)鍵詞:學(xué)分制 自動(dòng)排考 貪婪算法

中圖分類(lèi)號(hào):TP319 文獻(xiàn)標(biāo)識(shí)碼:B 文章編號(hào):1673-8454(2009)17-0031-04

一、引言

隨著教育體制改革的深入發(fā)展,實(shí)施學(xué)分制教學(xué)管理模式已成為我國(guó)各高等院校教學(xué)改革的發(fā)展方向。在該管理模式下,專(zhuān)業(yè)相同的學(xué)生選課也呈現(xiàn)多樣性,這給教學(xué)管理帶來(lái)一個(gè)極大難題,在考試安排上表現(xiàn)尤為突出。隨著高校擴(kuò)建和多校區(qū)格局普及,合理的學(xué)生考試時(shí)間安排、考場(chǎng)分配、監(jiān)考安排等問(wèn)題成為智能考務(wù)管理有效實(shí)施的關(guān)鍵,是高校信息化建設(shè)的迫切要求。針對(duì)上述問(wèn)題,我們提出了基于學(xué)分制多校區(qū)環(huán)境下考試安排管理的整體解決方案,并重點(diǎn)解決了學(xué)分制考試管理中三個(gè)核心難題:考試時(shí)間自動(dòng)安排算法、考場(chǎng)自動(dòng)安排算法、監(jiān)考自動(dòng)安排算法?；趯W(xué)分制多校區(qū)環(huán)境下的考試編排系統(tǒng)目前在國(guó)內(nèi)外尚屬空白,對(duì)高校實(shí)施學(xué)分制教學(xué)管理具有較強(qiáng)的指導(dǎo)意義。

二、系統(tǒng)總體設(shè)計(jì)

系統(tǒng)總體設(shè)計(jì)結(jié)構(gòu)如圖1所示。C/S應(yīng)用程序的使用對(duì)象主要是考務(wù)管理職能部門(mén);Web服務(wù)器使用對(duì)象是教師和學(xué)生,在多校區(qū)環(huán)境下考務(wù)信息發(fā)布中起著重要作用;JBoss服務(wù)器協(xié)同完成排考子系統(tǒng)中需要的業(yè)務(wù)操作,分擔(dān)Web的業(yè)務(wù)計(jì)算功能,在實(shí)際的應(yīng)用中JBoss服務(wù)器完成復(fù)雜業(yè)務(wù)計(jì)算,Web服務(wù)器完成頁(yè)面表現(xiàn);防火墻用來(lái)保護(hù)數(shù)據(jù)服務(wù)器及服務(wù)器安全;照片代理服務(wù)器用來(lái)提供照片顯示服務(wù),為巡考提供考場(chǎng)學(xué)生抽查相片信息服務(wù);身份認(rèn)證服務(wù)器用來(lái)對(duì)用戶使用本系統(tǒng)的合法性進(jìn)行認(rèn)證和分配權(quán)限。

1.系統(tǒng)流程

系統(tǒng)數(shù)據(jù)流圖如圖2所示。

系統(tǒng)流程如下:

(1)系統(tǒng)獲取基礎(chǔ)數(shù)據(jù),如考試時(shí)間、教室信息、考生數(shù)據(jù)、考試課程和院系監(jiān)考人數(shù);

(2)系統(tǒng)根據(jù)給定的考試時(shí)間范圍約束考試課程,采用本文設(shè)計(jì)的算法,自動(dòng)編排課程的考試時(shí)間,并保證同門(mén)考試課程在不同校區(qū)的考試時(shí)間一致;

(3)系統(tǒng)根據(jù)各校區(qū)的教室信息和規(guī)則自動(dòng)編排考場(chǎng);

(4)為編排好的課程進(jìn)行監(jiān)考人員編排及生成學(xué)生考試信息;

(5)學(xué)生考試信息發(fā)布,監(jiān)考信息發(fā)布。

2.系統(tǒng)功能模塊

根據(jù)學(xué)分制排考的業(yè)務(wù)需求,系統(tǒng)主要由以下功能模塊組成:數(shù)據(jù)準(zhǔn)備模塊、考試編排模塊、考務(wù)事務(wù)模塊和系統(tǒng)管理模塊。如圖3所示。

(1)數(shù)據(jù)準(zhǔn)備模塊

數(shù)據(jù)準(zhǔn)備模塊是為系統(tǒng)的運(yùn)行提供原始數(shù)據(jù):考試時(shí)間、教室信息、考生數(shù)據(jù)、考試課程和院系監(jiān)考人數(shù)。

考試時(shí)間設(shè)定的功能是根據(jù)用戶設(shè)定考試開(kāi)始和結(jié)束日期,每天三場(chǎng)次的考試時(shí)間段,生成時(shí)間段的場(chǎng)次號(hào)以及每場(chǎng)次的初始優(yōu)先級(jí)。

教室信息設(shè)定的功能是錄入或統(tǒng)計(jì)可用作考場(chǎng)的教室信息。

考生數(shù)據(jù)是從學(xué)生選課結(jié)果中獲取的要參加排考課程的學(xué)生信息。

考試課程數(shù)據(jù)是從選課表中導(dǎo)出待排考學(xué)生選課數(shù)據(jù)。考試課程確認(rèn),如果本學(xué)期課程特別多,有些專(zhuān)業(yè)課考試可由院系安排,沒(méi)必要由教務(wù)處安排統(tǒng)一考試,通過(guò)該模塊確定需教務(wù)進(jìn)行全校排考課程。

院系監(jiān)考人數(shù),院系可根據(jù)實(shí)際情況確定可派出每場(chǎng)監(jiān)考人數(shù),即“監(jiān)考教師人數(shù)”。院系對(duì)本部門(mén)教師要填寫(xiě)監(jiān)考校區(qū)意向,填報(bào)了的可用于參加監(jiān)考,因此可知“有地址人數(shù)”。

(2)考試編排模塊

1)考試時(shí)間編排

考試時(shí)間編排窗口的功能是編排每門(mén)課程的考試時(shí)間,并使用同門(mén)課程在不同校區(qū)的考試時(shí)間保持一致。編排時(shí)間將根據(jù)教室使用率和最大沖突人數(shù)、課程優(yōu)先數(shù)進(jìn)行編排。主界面如圖4所示。

“清除結(jié)果”:清除原有的編排結(jié)果。

“優(yōu)先級(jí)設(shè)置”:設(shè)置排考課程的主考校區(qū)和課程排考優(yōu)先級(jí)。優(yōu)先數(shù)據(jù)小的在條件情況一樣的情況下將優(yōu)先參加排考。

“沖突檢測(cè)”:可以顯示手工指定排考時(shí)間的課程是否存在考試沖突的學(xué)生名單。

“編排”:在輸入教室利用率和最大沖突人數(shù)后,進(jìn)行自動(dòng)編排考試時(shí)間。

“排考分析圖”:在編排完時(shí)間后,可以查看各場(chǎng)次的排考人數(shù)分布情況。為排考合理性提供直觀依據(jù)。

“場(chǎng)次數(shù)預(yù)測(cè)”:是預(yù)時(shí)間編排操作,為正式編排提供參考,以便做出合適調(diào)整。

2)考場(chǎng)編排

考場(chǎng)編排窗口的功能是編排各考試課程的考場(chǎng)。

設(shè)置考場(chǎng)優(yōu)先參數(shù):當(dāng)樓棟的優(yōu)先級(jí)設(shè)好后,同一棟數(shù)的教室的初始優(yōu)先級(jí)按照樓棟和考場(chǎng)號(hào)優(yōu)先級(jí)變?yōu)樯颉？梢酝ㄟ^(guò)修改優(yōu)先級(jí)數(shù)改變其安排優(yōu)先順序。

考場(chǎng)編排原則:有“考場(chǎng)最少”和“班級(jí)相鄰”。“考場(chǎng)最少”是指考場(chǎng)安排時(shí)最優(yōu)先考慮盡可能產(chǎn)生最少考場(chǎng)人數(shù)碎片,以最先找到合適容量教室為原則,這樣所用的考場(chǎng)將最少,安排監(jiān)考人數(shù)較少,但有可能同一門(mén)課程分布在不同樓棟,不利于巡考。這個(gè)原則較適合在教室資源較為緊張時(shí)采用?！鞍嗉?jí)相鄰”原則指盡可能考慮同一門(mén)課程安排在相互靠近的考場(chǎng)。效果是,由于不考慮產(chǎn)生考場(chǎng)人數(shù)碎片問(wèn)題,使用考場(chǎng)較多,監(jiān)考人數(shù)安排較多,同一課程在相互靠近的考場(chǎng)考試,利于巡考。這個(gè)原則適合用于教室資源豐富時(shí)。

3)監(jiān)考編排

主要功能是對(duì)已排好的課程進(jìn)行監(jiān)考自動(dòng)編排。自動(dòng)編排原則有:第一監(jiān)考為課程所在院系原則、任務(wù)量均攤原則、不超過(guò)每場(chǎng)次派出最多人數(shù)原則。編排結(jié)束后,院系可對(duì)監(jiān)考進(jìn)行微調(diào),在未審核狀態(tài)下各院系可以通過(guò)網(wǎng)上更換監(jiān)考教師。審核通過(guò)后,院系就不能再申報(bào)監(jiān)考教師了,但考務(wù)管理人員可以指定監(jiān)考教師。

(3)考務(wù)事務(wù)和系統(tǒng)管理模塊

1)考務(wù)事務(wù)管理主要是打印功能:試卷分發(fā)單打印和考試簽到單打印。試卷分發(fā)單打印是將某個(gè)時(shí)間某門(mén)課程的考試學(xué)生人數(shù)打印,而考試簽到單打印是將某個(gè)時(shí)間某門(mén)課程某考場(chǎng)的學(xué)生名單打印出來(lái),打印考試學(xué)生抽查單是用于核對(duì)學(xué)生身份。

2)系統(tǒng)管理主要是完成以下三個(gè)功能:校區(qū)網(wǎng)上信息控制開(kāi)關(guān)、設(shè)置工作學(xué)期和打印設(shè)置。

三、考試時(shí)間編排算法設(shè)計(jì)

在學(xué)分制下排考要解決三大問(wèn)題:

第一,學(xué)生考試沖突。大規(guī)模的考試中,如期末考試,涉及學(xué)生面廣、課程多、考試時(shí)間短的情況下,求出沒(méi)有學(xué)生考試沖突的解是十分困難的,它的排列組合相當(dāng)大,耗時(shí)特別長(zhǎng)。因此,如何把學(xué)生個(gè)人考試沖突人數(shù)減少到最少是排考要解決的關(guān)鍵問(wèn)題。

第二,考場(chǎng)資源沖突。根據(jù)本校的考場(chǎng)信息資源,如何充分有效地利用教室,減少教室的分配碎片,提高教室利用率,是考場(chǎng)安排主要解決的問(wèn)題。

第三,監(jiān)考老師如何指派。根據(jù)學(xué)校的監(jiān)考人員庫(kù),盡可能將監(jiān)考任務(wù)平均分配出去,并要做到監(jiān)考人員時(shí)間不沖突,監(jiān)考任務(wù)平均分配。

以上問(wèn)題的求解就是對(duì)三個(gè)公共資源的合理調(diào)度,因此我們嘗試使用貪婪算法去研究和解決問(wèn)題。

1.考試時(shí)間編排算法

在本系統(tǒng)中采用貪婪算法。貪婪法不追求最優(yōu)解,不要回溯,只希望得到較為滿意的解。雖然貪婪法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解,但對(duì)范圍相當(dāng)廣泛的求最優(yōu)解問(wèn)題來(lái)說(shuō),它是一種最直接的算法設(shè)計(jì)技術(shù),通過(guò)一系列局部最優(yōu)的選擇,即貪婪選擇可以產(chǎn)生整體最優(yōu)解。具體地說(shuō),通常所求問(wèn)題的一個(gè)整體最優(yōu)解,是從貪婪選擇開(kāi)始的,而且每作一步貪婪選擇后,原問(wèn)題可簡(jiǎn)化為一個(gè)規(guī)模更小的類(lèi)似子問(wèn)題,然后通過(guò)多步貪婪選擇,最終可得到問(wèn)題的一個(gè)整體最優(yōu)解。

課程時(shí)間編排是排考系統(tǒng)的核心模塊。排考算法主要在規(guī)定考試時(shí)間范圍內(nèi)和其他約束條件范圍內(nèi),有效地合理組合各課程及考試時(shí)間,獲得一個(gè)可以實(shí)施考試的解。按排列組合來(lái)做,將是一個(gè)耗時(shí)、耗計(jì)算的難題。如何快速求出一個(gè)有效解,是該算法的關(guān)鍵。在算法設(shè)計(jì)時(shí)涉及的要點(diǎn)有:

(1)考試最大容量:這個(gè)值不是所有考場(chǎng)座位數(shù)的總和。由于在一個(gè)考場(chǎng)安排時(shí)有可能會(huì)出現(xiàn)考場(chǎng)座位空閑的情況。因此,每個(gè)時(shí)間內(nèi)的考試最大容量公式:

考試最大容量=考場(chǎng)座位數(shù)×座位使用率

座位使用率是一個(gè)經(jīng)驗(yàn)值,一般會(huì)在0.8~1之間。

(2)允許沖突人數(shù):在學(xué)分制選課情形下,要盡可能避免同一時(shí)間同一考生參加兩門(mén)或多門(mén)考試的情況。但在實(shí)際操作中發(fā)現(xiàn),當(dāng)允許沖突人數(shù)為0時(shí),將會(huì)使整個(gè)考試時(shí)間周期拉長(zhǎng),這有時(shí)在考試安排中是無(wú)法滿足的。因此我們將允許沖突人數(shù)根據(jù)不同情況將其設(shè)置在一定范圍之間的一個(gè)值。發(fā)生沖突的考生可在有沖突的考試時(shí)間選一門(mén)考試,其他沖突的考試科目可采用備份試卷進(jìn)行緩考解決。

歷年來(lái)應(yīng)用效果如表1所示。

考試時(shí)間編排算法如圖5所示。

2.考場(chǎng)編排算法

根據(jù)考試課程時(shí)間的編排結(jié)果,考試編排就是要合理解決某時(shí)間所安排課程的具體場(chǎng)地問(wèn)題。有如下一些考慮因素:

(1)在考場(chǎng)足夠多的情況下,相同課程盡可能安排在相近的考場(chǎng)內(nèi)。這樣的排法,便于課程巡考及考務(wù)管理。但這種算法容易造成尾數(shù)考生占用整個(gè)考場(chǎng),降低了考場(chǎng)座位使用率。

(2)在考場(chǎng)有限的情況下,采用考場(chǎng)擇優(yōu)算法,根據(jù)課程人數(shù),選取一個(gè)最合適且能安排該課程的考場(chǎng)。這樣能充分提高座位使用率,但有可能會(huì)造成同門(mén)課程分散在不同地點(diǎn)的考場(chǎng)中進(jìn)行,不便于巡考等管理工作。

(3)為了充分提高考場(chǎng)座位使用率,還要有將尾數(shù)考場(chǎng)進(jìn)行合并操作的功能。將某一時(shí)間的零散考生集中到同一考場(chǎng)中進(jìn)行考試。

3.監(jiān)考編排算法

在對(duì)監(jiān)考人員自動(dòng)編排時(shí)要解決的問(wèn)題有:

(1)監(jiān)考盡可能要派與開(kāi)考課程相關(guān)的教師。

(2)監(jiān)考人員編排應(yīng)根據(jù)其所在校區(qū),盡可能派該校區(qū)監(jiān)考。在多校區(qū)模式下,避免監(jiān)考人員跨校區(qū)奔波。

(3)盡可能將監(jiān)考任務(wù)平攤給監(jiān)考人員,不會(huì)出現(xiàn)個(gè)別人、個(gè)別院系監(jiān)考任務(wù)過(guò)重的情況。

(4)監(jiān)考編排算法滿足監(jiān)考的一般實(shí)際要求,對(duì)于一些監(jiān)考的特殊要求,可以局部采用手工方式進(jìn)行補(bǔ)充。

四、應(yīng)用效果

江西財(cái)經(jīng)大學(xué)自1994年實(shí)施完全學(xué)分制已有14年,在考務(wù)管理上積累了一些經(jīng)驗(yàn)。考務(wù)管理系統(tǒng)多次更新。本系統(tǒng)是在學(xué)校擴(kuò)建形成了多校區(qū)格局環(huán)境下產(chǎn)生,至今已運(yùn)行4年多了,涉及3個(gè)校區(qū),每次考試涵蓋學(xué)生人數(shù)達(dá)1萬(wàn)多人。本系統(tǒng)廣泛應(yīng)用于期末考試、期中考試、補(bǔ)考考試、二專(zhuān)考試等各類(lèi)考試安排,發(fā)揮著重要的技術(shù)支撐作用,取得了很好的效果。

本系統(tǒng)通過(guò)對(duì)班級(jí)、學(xué)生、課程、考場(chǎng)、時(shí)間和監(jiān)考老師等實(shí)體關(guān)系的分析,以貪婪算法為理論基礎(chǔ),較好地解決了考試時(shí)間、考場(chǎng)和監(jiān)考人員安排問(wèn)題,得到了一個(gè)近似最優(yōu)的解決方案?；趯W(xué)分制和多校區(qū)環(huán)境下的考試安排智能化系統(tǒng)在國(guó)內(nèi)外均屬空白,因此該方案對(duì)高校實(shí)施學(xué)分制教學(xué)管理具有較強(qiáng)的指導(dǎo)意義。

參考文獻(xiàn):

[1]王素榮.教育信息化理論與方法[D].北京:社會(huì)科學(xué)文獻(xiàn)出版社, 2006.

[2]聶小東.基于貪婪算法的排課系統(tǒng)的研究與實(shí)現(xiàn)[D].廣東工業(yè)大學(xué), 2006.

[3]韓承雙,張春梅,王開(kāi)友.自動(dòng)排課系統(tǒng)迭代算法設(shè)計(jì)與實(shí)現(xiàn)[J].合肥學(xué)院學(xué)報(bào)(自然科學(xué)版),2005,15(3):52-56.

[4]趙曉慶,熊璋,方義.高校智能排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)與現(xiàn)代化,2004(11):102-105.

[5]李端明,李宇翔.學(xué)分制下排課的數(shù)據(jù)組織與算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2006(19).

[6]任虹燦,李世晨.學(xué)分制環(huán)境下學(xué)習(xí)預(yù)警信息系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2007(10).

[7]胡世清,葛幸平.高校自動(dòng)排考軟件的優(yōu)化設(shè)計(jì)[J].教育信息化,2001(3).

[8]黃勇,蘇守寶.一種新的高校自動(dòng)排考算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007(12).