基于低冗余率模型的校園機(jī)房排課系統(tǒng)研究與實(shí)現(xiàn)

許兆祥 李慧燕

摘要：目前大部分機(jī)房排課系統(tǒng)的設(shè)計(jì)，多數(shù)是基于專業(yè)及班級(jí)人數(shù)固定而進(jìn)行研究的，而沒有考慮由于專業(yè)不同，班級(jí)人數(shù)不固定等需求的機(jī)房排課適配問題，本文提出了人數(shù)優(yōu)先的機(jī)房排課算法，建立了基于低冗余率的數(shù)學(xué)模型，研究解決班級(jí)人數(shù)不固定對機(jī)房機(jī)位不能很好匹配的問題，實(shí)踐證明通過這種基于低冗余率模型的設(shè)計(jì)，有效的提高了機(jī)房的使用率，實(shí)現(xiàn)機(jī)房教學(xué)資源利用效率大化，全面提高了排課質(zhì)量。

關(guān)鍵詞：人數(shù)優(yōu)先;低冗余率;機(jī)房;排課

一、引言：目前很多學(xué)校都存在專業(yè)不同，班級(jí)人數(shù)不相 同的情況，同時(shí)，由于中職學(xué)校學(xué)生開學(xué)報(bào)到人數(shù)的不確定性， 導(dǎo)致實(shí)際分班后，每個(gè)班的總?cè)藬?shù)存在較大差異;而學(xué)校機(jī)房 由于建設(shè)時(shí)間不同，機(jī)房機(jī)位數(shù)也不同，綜合這兩方面的原因， 導(dǎo)致使用傳統(tǒng)的機(jī)房排課系統(tǒng)，很難做到班級(jí)人數(shù)與機(jī)房機(jī)位 數(shù)的良好匹配。為解決這一問題，從學(xué)校的實(shí)際情況出發(fā)，設(shè) 計(jì)了基于人數(shù)優(yōu)先的校園機(jī)房排課系統(tǒng)，并將實(shí)驗(yàn)研究方案得 到的機(jī)房排課表與傳統(tǒng)排課得到的機(jī)房排課表進(jìn)行比較，通過 實(shí)踐結(jié)果來進(jìn)行研究結(jié)果的驗(yàn)證，以確保上課機(jī)房與班級(jí)實(shí)際 人數(shù)最大程度的匹配。

二、研究現(xiàn)狀

隨著計(jì)算機(jī)信息化的快速發(fā)展，信息化管理在學(xué)校基礎(chǔ)建 設(shè)中顯得尤為重要，越來越多的學(xué)校借助信息化手段進(jìn)行日常 教務(wù)運(yùn)營和管理，當(dāng)前國內(nèi)外研究人員在機(jī)房排課方面做了大 量研究，嘗試使用不同方案及不同算法來解決，主要集中在針 對班級(jí)人數(shù)大致相同的情況下進(jìn)行機(jī)房自動(dòng)排課的設(shè)計(jì)，又或 者是針對普通教室或以任課教師優(yōu)先級(jí)、課程性質(zhì)優(yōu)先級(jí)進(jìn)行 設(shè)計(jì)研究，對機(jī)房排課問題的研究也取得了一些研究成果，但 因?qū)W校發(fā)展和規(guī)模不同，對機(jī)房排課需求也不盡相同，在解決 機(jī)房排課問題時(shí)而沒有考慮班級(jí)人數(shù)不固定，無法與機(jī)房進(jìn)行 匹配問題，導(dǎo)致機(jī)房使用率低，教學(xué)資源分配不均等情況出現(xiàn)。 因此，結(jié)合學(xué)校實(shí)際情況，通過研究，提出了一個(gè)基于班級(jí)人 數(shù)優(yōu)先的低冗余率機(jī)房排課模型，從而為機(jī)房排課問題的研究 解決提供了新的思路。

三、 需求分析

機(jī)房排課問題涉及因素比較多，是一項(xiàng)比較繁雜的工作， 在機(jī)房排課過程中，以學(xué)校實(shí)際劃分的班級(jí)為最小排課單位進(jìn) 行排課，為了避免機(jī)房使用率不高，本文以某中職學(xué)校計(jì)算機(jī) 班機(jī)房上機(jī)排課為實(shí)驗(yàn)對象進(jìn)行需求分析，從而實(shí)現(xiàn)基于人數(shù) 優(yōu)先的低冗余率的排課系統(tǒng)設(shè)計(jì)，排課系統(tǒng)應(yīng)滿足如下需求：

3.1 基于班級(jí)人數(shù)優(yōu)先級(jí)進(jìn)行機(jī)房匹配，提高機(jī)房使用率， 降低機(jī)房冗余率。

由于計(jì)算機(jī)班額較多，每個(gè)班級(jí)的人數(shù)又不固定，采用傳 統(tǒng)方式進(jìn)行機(jī)房排課，會(huì)出現(xiàn)有些班級(jí)上機(jī)房課，存在大量機(jī) 器被閑置，從而導(dǎo)致機(jī)房冗余率過高，而有些班級(jí)的機(jī)房課幾 個(gè)學(xué)生共用一臺(tái)計(jì)算機(jī)，機(jī)房機(jī)器不夠用的情況，這就是由于 機(jī)房排課方案的不合理造成的，因此，設(shè)計(jì)以班級(jí)人數(shù)優(yōu)先級(jí) 進(jìn)行機(jī)房排課，這樣可有效避免機(jī)器閑置和浪費(fèi)，提高機(jī)房資 源使用率，降低機(jī)房冗余率。

3.2 班級(jí)人數(shù)與機(jī)房機(jī)位數(shù)進(jìn)行近似匹配，保障正常授課?秩序，提高授課質(zhì)量。

上機(jī)實(shí)踐課的目的，主要是幫助學(xué)生借助計(jì)算機(jī)來掌握相 關(guān)知識(shí)或技能，教師通過課堂上學(xué)生操作計(jì)算機(jī)的情況，可考 察檢驗(yàn)學(xué)生對知識(shí)掌握的程度，因此，為保證課堂教學(xué)質(zhì)量， 在機(jī)房排課過程中，要盡量確保當(dāng)前班級(jí)的每位學(xué)生都有一臺(tái) 計(jì)算機(jī)可以使用，實(shí)現(xiàn)班級(jí)人數(shù)與機(jī)房機(jī)位數(shù)進(jìn)行近似匹配， 盡量避免因個(gè)別學(xué)生操作失誤而需要單獨(dú)講解，使得教學(xué)工作 得以有效進(jìn)行，提高教師授課質(zhì)量。

四、基于低冗余率模型的排課系統(tǒng)設(shè)計(jì)

4.1 低冗余率模型概述

低冗余率模型采用優(yōu)先級(jí)的設(shè)計(jì)算法，優(yōu)先以班級(jí)人數(shù)進(jìn) 行排課，班級(jí)人數(shù)越多，優(yōu)先級(jí)越高，則越優(yōu)先進(jìn)行機(jī)房排課， 在班級(jí)人數(shù)相同的情況下，以班級(jí)編號(hào)為優(yōu)先級(jí)進(jìn)行排課，班 級(jí)編號(hào)越靠前，優(yōu)先級(jí)越高，則先進(jìn)行機(jī)房排課，直至排課結(jié) 束。

4.2 低冗余率排課設(shè)計(jì)，具體研究步驟如下：

（1） 按班級(jí)人數(shù)多少對班級(jí)進(jìn)行排序，如果班級(jí)人數(shù)相 同，則以班級(jí)編號(hào)進(jìn)行排序，以確定班級(jí)優(yōu)先級(jí)。

（2） 按機(jī)房機(jī)位數(shù)對機(jī)房進(jìn)行排序，如果機(jī)房機(jī)器數(shù)相 同，則以機(jī)房編號(hào)優(yōu)先級(jí)進(jìn)行排序，以確定機(jī)房優(yōu)先級(jí)。

（3） 依據(jù)班級(jí)優(yōu)先級(jí)和機(jī)房優(yōu)先級(jí)進(jìn)行近似匹配，降低 機(jī)房冗余率，實(shí)現(xiàn)機(jī)房排課。

（4） 根據(jù)實(shí)際情況，對排課結(jié)果輔助手工個(gè)別排課調(diào)整， 得到最終的機(jī)房排課表。

低冗余率排課模型流程圖，如圖 4.1 所示：

4.3 低冗余率排課數(shù)學(xué)模型

機(jī)房排課系統(tǒng)主要涉及到班級(jí)、機(jī)房、時(shí)間等集合因素， 班級(jí)、機(jī)房集合因素可用公式表示如下：

根據(jù)學(xué)校教學(xué)安排實(shí)際情況，上機(jī)課程一周安排為 30 課 時(shí)，每工作日安排 6 課時(shí)，上午 4 個(gè)課時(shí)，下午 2 個(gè)課時(shí)，每 兩個(gè)課時(shí)為一大節(jié)，可安排為一個(gè)上機(jī)時(shí)間段，因此，時(shí)間集 合及約束條件可用如下公式進(jìn)行表示：

時(shí)間段標(biāo)記：f={0，1}0 表示未安排課，1 表示已安排課。 要實(shí)現(xiàn)低冗余率的機(jī)房排課，也就是用班級(jí)人數(shù)與機(jī)房人 數(shù)進(jìn)行差值運(yùn)算，取出差值最小的班級(jí)。因此通過對班級(jí)、機(jī) 房、時(shí)間段因素進(jìn)行算法設(shè)計(jì)，得到如下 4.2 所示的公式評價(jià) 目標(biāo) P：

4.2 機(jī)房低冗余率排課公式

4.4 低冗余率排課算法描述

（1）把班級(jí)集合 C 按班級(jí)人數(shù)從大到小排序，從而 選出第一個(gè)需要排課的班級(jí)。

（2）把機(jī)房集合 J 按機(jī)房機(jī)器數(shù)從大到小排序，選 出機(jī)器數(shù)與班級(jí)人數(shù)比較接近的機(jī)房。

（3）按照上課時(shí)間節(jié)點(diǎn)，判斷該時(shí)間節(jié)點(diǎn)是否已排 課。

（4）如果沒有排課，則在該時(shí)間節(jié)點(diǎn)可以進(jìn)行排課， 把該時(shí)間段標(biāo)記 f=1。

（5）如果已排課，繼續(xù)步驟（2）并遍歷時(shí)間節(jié)點(diǎn)表。

（6）直到找出沒有沖突的時(shí)間節(jié)點(diǎn)可以進(jìn)行排課。

（7）遍歷所有班級(jí)，重復(fù)（2）至（6）的過程，直 到所有的班級(jí)排課結(jié)束。

基于低冗余率排課算法流程圖描述如圖 4.3 所示。

4.5 低冗余率排課實(shí)驗(yàn)演示

基于低冗余率排課系統(tǒng)的需求分析和模型概述設(shè)計(jì)，對機(jī) 房進(jìn)行排課，主要涉及班級(jí)人數(shù)、班級(jí)編號(hào)、機(jī)房機(jī)器數(shù)、機(jī) 房編號(hào)、上課時(shí)段等各方面的因素，結(jié)合學(xué)校機(jī)房建設(shè)情況， 機(jī)房如表 4.4 所示。

4.4 機(jī)房表

對機(jī)房優(yōu)先級(jí)排序后得到所示的機(jī)房優(yōu)先級(jí)表如 4.5。

4.5 機(jī)房優(yōu)先級(jí)表

依據(jù)學(xué)校對班級(jí)的劃分，班級(jí)情況如表 4.6 所示。

4.6 班級(jí)表

對班級(jí)優(yōu)先級(jí)排序后得到所示的班級(jí)優(yōu)先級(jí)表如 4.7。

4.7 班級(jí)優(yōu)先級(jí)表

在實(shí)際排課過程中，考慮到時(shí)間段的因素，先把班級(jí)優(yōu)先 級(jí)最高的班級(jí)同機(jī)房機(jī)器數(shù)匹配，取出差值最小的最行排課， 在進(jìn)行排課過程中，如果當(dāng)前時(shí)間段已經(jīng)排過課，則到下一個(gè) 時(shí)間段進(jìn)行排課，直到該班級(jí)課程在機(jī)房排課結(jié)束，根據(jù)公式 4.2，以周一至周五，每工作日 1-2 節(jié)進(jìn)行實(shí)驗(yàn)，得到可行的排 課方案與傳統(tǒng)排課方案對比如圖 4.8 所示：

4.8 人數(shù)優(yōu)先排課方案與傳統(tǒng)排課方案對比

通過對某中職學(xué)校計(jì)算機(jī)專業(yè)進(jìn)行排課實(shí)驗(yàn)驗(yàn)證，把基于 低冗余率的排課結(jié)果和傳統(tǒng)的機(jī)房排課結(jié)果進(jìn)行比較，降低了 機(jī)器空閑數(shù)，機(jī)房使用率得到了有效的提升，結(jié)果表明使用班 級(jí)人數(shù)優(yōu)先的算法在排課效果上優(yōu)于之前的排課系統(tǒng)，說明基 于低冗余率的以班級(jí)人數(shù)優(yōu)先對機(jī)房機(jī)器數(shù)進(jìn)行近似匹配的 算法，有效的提高了機(jī)房使用率。

五、結(jié)束語

機(jī)房自動(dòng)排課系統(tǒng)的設(shè)計(jì)結(jié)合學(xué)校的實(shí)際情況主要解決 學(xué)校機(jī)房排課問題，通過一定的算法實(shí)現(xiàn)機(jī)房的自動(dòng)排課功能， 并以手工排課功能作為輔助，對提高機(jī)房使用率，維護(hù)正常的 教學(xué)秩序具有重要的現(xiàn)實(shí)意義，它是學(xué)校信息化管理的重要組成部分，具有較高的使用價(jià)值 。

參考文獻(xiàn)：

1 蘇軍波.基于優(yōu)化的啟發(fā)式算法進(jìn)行排課的研究[碩士學(xué) 位論文].長春：東北師范大學(xué)，2018.

2 周現(xiàn)甫.駐馬店技師學(xué)院排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[碩士學(xué) 位論文].天津： 天津職業(yè)技術(shù)師范大學(xué)，2019.

3 張貴軍，陳安，胡俊.基于蒙特卡洛遺傳算法的排課問題研究.實(shí) 驗(yàn)技術(shù)與管理，2019，36（3）：170-174.

4 張煥君，潘遠(yuǎn)東.遺傳算法在排課系統(tǒng)中的應(yīng)用.無法互聯(lián) 科技，2017，（2）：199.

5 楊 偉 明 . 計(jì) 算 機(jī) 機(jī) 房 的 建 設(shè) 與 管 理 . 黑 龍 江 科 學(xué)，2017，8（04）：38-39.

6 蘇媛媛.高校機(jī)房排課系統(tǒng)的探討.河北化工醫(yī)藥職業(yè)技 術(shù)學(xué)院，2018，（3）：142.

作者簡介：

許兆祥，1982.11.27，男，漢，山西省運(yùn)城市新絳縣，職位： 經(jīng)貿(mào)與信息技術(shù)系副主任，職稱：講師，研究方向：計(jì)算機(jī)軟 件與理論、數(shù)據(jù)庫與 Web 技術(shù)。