肖清雷

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

關鍵詞:學分制 自動排考 貪婪算法

中圖分類號:TP319 文獻標識碼:B 文章編號:1673-8454(2009)17-0031-04

一、引言

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

二、系統(tǒng)總體設計

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

1.系統(tǒng)流程

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

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

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

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

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

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

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

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

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

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

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

考試時間設定的功能是根據(jù)用戶設定考試開始和結束日期,每天三場次的考試時間段,生成時間段的場次號以及每場次的初始優(yōu)先級。

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

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

考試課程數(shù)據(jù)是從選課表中導出待排考學生選課數(shù)據(jù)?？荚囌n程確認,如果本學期課程特別多,有些專業(yè)課考試可由院系安排,沒必要由教務處安排統(tǒng)一考試,通過該模塊確定需教務進行全校排考課程。

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

(2)考試編排模塊

1)考試時間編排

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

“清除結果”:清除原有的編排結果。

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

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

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

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

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

2)考場編排

考場編排窗口的功能是編排各考試課程的考場。

設置考場優(yōu)先參數(shù):當樓棟的優(yōu)先級設好后,同一棟數(shù)的教室的初始優(yōu)先級按照樓棟和考場號優(yōu)先級變?yōu)樯??？梢酝ㄟ^修改優(yōu)先級數(shù)改變其安排優(yōu)先順序。

考場編排原則:有“考場最少”和“班級相鄰”?！翱紙鲎钌佟笔侵缚紙霭才艜r最優(yōu)先考慮盡可能產(chǎn)生最少考場人數(shù)碎片,以最先找到合適容量教室為原則,這樣所用的考場將最少,安排監(jiān)考人數(shù)較少,但有可能同一門課程分布在不同樓棟,不利于巡考。這個原則較適合在教室資源較為緊張時采用?！鞍嗉壪噜彙痹瓌t指盡可能考慮同一門課程安排在相互靠近的考場。效果是,由于不考慮產(chǎn)生考場人數(shù)碎片問題,使用考場較多,監(jiān)考人數(shù)安排較多,同一課程在相互靠近的考場考試,利于巡考。這個原則適合用于教室資源豐富時。

3)監(jiān)考編排

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

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

1)考務事務管理主要是打印功能:試卷分發(fā)單打印和考試簽到單打印。試卷分發(fā)單打印是將某個時間某門課程的考試學生人數(shù)打印,而考試簽到單打印是將某個時間某門課程某考場的學生名單打印出來,打印考試學生抽查單是用于核對學生身份。

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

三、考試時間編排算法設計

在學分制下排考要解決三大問題:

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

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

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

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

1.考試時間編排算法

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

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

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

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

座位使用率是一個經(jīng)驗值,一般會在0.8~1之間。

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

歷年來應用效果如表1所示。

考試時間編排算法如圖5所示。

2.考場編排算法

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

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

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

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

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

在對監(jiān)考人員自動編排時要解決的問題有:

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

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

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

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

四、應用效果

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

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

參考文獻:

[1]王素榮.教育信息化理論與方法[D].北京:社會科學文獻出版社, 2006.

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

[3]韓承雙,張春梅,王開友.自動排課系統(tǒng)迭代算法設計與實現(xiàn)[J].合肥學院學報(自然科學版),2005,15(3):52-56.

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

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

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

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

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