王麗華　汪海林　朱子軒　龍潤利

摘要：該文針對機房手工排課效率低下問題，采用計算機模擬手工排課法解決機房排課問題，改變了傳統(tǒng)的手工排課方式。實踐結果表明，這種改進不僅提高了工作效率，也提高了機房排課的科學性。

關鍵詞：機房排課；BIS架構；Ajax；ASP

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2015）19-0067-03

1概述

合肥工業(yè)大學計算機基礎實驗室承擔全校計算機基礎課的實驗教學任務，承擔基于網(wǎng)絡（非計算機類）課程的實驗教學任務，所開設的課程種類繁多。由于各個機房硬件環(huán)境不同，軟件環(huán)境也存在很大差異。多年來機房排課一直以傳統(tǒng)的手工方式操作，排課時教師必須親臨現(xiàn)場，不僅浪費了大量的人力資源，還容易產(chǎn)生沖突引發(fā)教學事故。

高校的機房排課問題實質(zhì)上是一個資源競爭問題，在機房排課過程中要全面考慮教師、課程、班級、機房和時間等多方面的因素，只有統(tǒng)籌兼顧，才能排出既符合教學規(guī)律、又滿足各方面要求的課表，因此排課問題在程序設計中是一個比較復雜的問題。

近幾年隨著研究的不斷深入，國內(nèi)外的研究專家已經(jīng)開發(fā)出各種類型的機房排課系統(tǒng)。由于各個學校的管理模式不同，約束條件也復雜多變，因此幾乎所有的機房排課系統(tǒng)都是以各個高校的實際情況作為參考對象，沒有一個通用的機房排課系統(tǒng)。因此運用現(xiàn)代化手段進行科學管理，制作一套符合我校實際情況的機房計算機自動排課系統(tǒng)迫在眉睫。

2機房計算機自動排課系統(tǒng)設計

2.1機房排課涉及因素

高校的機房排課涉及很多因素，需要考慮學生學習效果、學生有空的時間段、教師有空的時間段等。機房排課主要存在六個因素。課程編號、課程名稱、周學時、課程的優(yōu)先級。教師編號及姓名，教師可以對上課時間提出自己的特殊要求。班級編號、學生人數(shù)，班級學生人數(shù)不能超過機房的機位數(shù)。機房排課涉及學年、學期、周、天、時段、節(jié)次等。機房的軟硬件環(huán)境是否符合課程需求。機房的利用率。排課的時間問題。

2.2約束條件

機房排課的約束條件是課程、機房、班級、教師、學生不能在同一時間發(fā)生沖突。根

據(jù)學校實際情況，機房排課與教室不同，一個教室在一個時間段只能上一門課，而機房卻可以上多門課；機房的可用周跨度要滿足課程的面授周跨度；機房的可用節(jié)次要滿足課程的上課節(jié)次要求，本系統(tǒng)將一天劃分為12個時間片，即12節(jié)課。上午4節(jié)課，下午4節(jié)課，晚上4節(jié)課。某些特定的時間段（周日、國家法定的節(jié)假日、校運動會）機房不能排課，如果需要排課只能由admin用戶去排課。另外，排課要根據(jù)每門課程的特點，設置排課的優(yōu)先級，通常一些需要記憶的必修課（例如：大學英語網(wǎng)絡化教學等課程）要盡量安排在早上，下午盡量安排選修課，操作類的課盡量安排在晚上。課程設計屬于集中實踐環(huán)節(jié)，一般放在學期末集中幾周時間排課。

3模擬手工排課法解決機房排課問題

3.1基于優(yōu)先級的機房排課算法的設計原則

課表編排是一個時間、教師、學生、機房軟硬件環(huán)境、機房機位數(shù)五者的組合規(guī)劃問題。在時間、教師、學生、機房軟硬件環(huán)境、機房機位數(shù)五維關系中，時間是決定排課是否發(fā)生沖突的首要因素。根據(jù)課程優(yōu)先原則，確定每類課程的優(yōu)先次序，系統(tǒng)自動控制讓優(yōu)先級高的課程的任課教師先排課，具體做法是根據(jù)課程優(yōu)先級的高低，將任課教師劃分為不同的等級的用戶。

3.2基于優(yōu)先級算法描述及實現(xiàn)方案

本系統(tǒng)在設計算法時，為了降低課程調(diào)度算法的復雜性，采用了基于優(yōu)先級的算法。優(yōu)先安排某一類課程先排課，實現(xiàn)方法是分時間段對不同等級的教師開放，讓優(yōu)先級高的教師先排課，即運用運籌學中分層規(guī)劃的思想，把排課問題在數(shù)學上看作為一個時間、教師、學生、機房軟硬件環(huán)境、機房利用率五維空間的調(diào)度問題，以教學計劃和各種特殊要求為約束條件進行組合規(guī)劃，采用了化整為零的思想，有效地抽象了實際排課問題，縮小了求解問題的空間。如圖1所示，系統(tǒng)對等級為3的用戶開放。

在排課算法運行時，需要在課程信息鏈表中的課程鏈表中找到合適的機房資源（即哪個機房能夠開設該門課程的實驗），只有能夠開設該門課程實驗的機房才允許被申請。該算法的求解步驟是從某一問題的初始解出發(fā)：

While約束條件do

求出可行解的一個解元素；

由所有解元素組合成問題的一個可行解。

3.3機房排課問題的數(shù)學模型

3.3.1算法設計

在算法的設計過程中，主要使用機房信息數(shù)據(jù)結構和課程信息數(shù)據(jù)結構，并采用結構體形式，兩者都由系統(tǒng)數(shù)據(jù)庫自動生成。機房信息數(shù)據(jù)結構主要用來存儲機房信息，包括主鍵、機位數(shù)、機房軟硬件環(huán)境、可用周次、節(jié)次等信息。課程信息數(shù)據(jù)結構主要用來存儲對應課程的信息，包括主鍵、班級、課程、申請周次、申請節(jié)次等。排課時首先初始化機房信息鏈表和課程信息鏈表，然后由課程信息鏈表開始循環(huán)求解，針對課程信息鏈表的每一個結點，根據(jù)算法準則在機房信息鏈表中進行循環(huán)查找，找到合適的機房資源，并且顯示出來，反之則不顯示。排課時我們先對時間片進行遍歷，從而獲得每個時間片的ID，借助于鼠標直接對時間片進行排課操作。

3.3.2算法的求解步驟

3.3.3數(shù)學模型

機房教學課表編排過程涉及的實體集合如下：

課程集合：L={L₁，L₂，…，L_i；}，L_i表示第i門課程。

班級集合：C={C₁，C₂，…，C_i，}，C_i表示第i個班級。

教師集合：T={T₁，T₂，…，T_i；}，T_i表示第i位教師。

時間集合：Q={Q₁，Q₂，…，Q_i}，Q_i表示第i個時間段。

機房集合：R={R₁，R₂，…，R_i}，R_i表示第i個機房。

上述五個因素的笛卡爾積L×C×X T×Q×R就構成了排課問題的解空間，而排課問題就是在這個解空間中找到一個滿足各種約束條件的解。在排課之前，根據(jù)教學計劃和教學任務安排，課程一班級一教師的對應關系已經(jīng)明確，所以為已知元組。機房排課問題就是為每門課程找到一個合適的時間和機房，所以為待求元組。因此，可以將機房排課問題簡化為解決關系和關系所構成的二分圖的最大匹配問題。排課算法也就簡化為班級、教師、機房三方面數(shù)據(jù)在具有共同的空閑時間片前提下的排列組合問題，三者關系在三維空間上的交點P表示一個排課組合的選擇，即可能的教學安排。排課遵循這一約束規(guī)則，在三維空間搜索空閑的時間片集合，該集合就是排課問題的解。

課表實際上是一個三維表，一周的每一天是列Y，每天的上課時間是行X，每學期的總周數(shù)做Z軸，組成的三維數(shù)據(jù)庫系統(tǒng)。但由于學校服務器上沒有三維數(shù)據(jù)庫的運行環(huán)境，所以在實現(xiàn)時，需要用二維表做字段冗余以模擬三維表的操作。

4.系統(tǒng)實現(xiàn)

4.1用戶排課操作關鍵技術

為了方便操縱頁面中的各種對象，以及交互效果，處于安全性和跨平臺的考慮，機房排課客戶端操作運用Javascript技術。排課時教師只要用鼠標點擊、拖動技術即可完成全部排課工作，無需輸入漢字。其關鍵技術是通過獲取用戶id，（函數(shù)構建function funClick（username）{}）進而判斷滿足用戶需要的機房，并從數(shù)據(jù)庫中提取相應機房的信息，如果機房不為空，并且滿足課程所需，在相應的時間段內(nèi)通過用鼠標點擊即可進行排課，（函數(shù)構建function chk（id，zc）{1）此時我們將課表看成是一個二維表，一周的每一天是列Y，每天的上課時間是行X，通過對行列的遍歷，（函數(shù)構建function chksq（id，zc）{}）獲取課程名稱、班級名稱，username賦值給單元格的innerHTML（函數(shù)構建function funSetCellData（th，roW，col，zc）{}）。

在課程調(diào)度方面，關鍵技術主要是對單元格的拖動，（函數(shù)構建function DragedTable（tableld）{}）點擊（onmousetup）即可獲得目標單元格的內(nèi)容，顯示圖層，獲取過渡圖層，同時計算中間過渡層的位置，并且賦值（函數(shù)構建function showDiv0{}）；鼠標拖動（onmousemove），計算鼠標的位置，是否在某個單元格的范圍之內(nèi)，松開鼠標（onmousedown），交換文本（函數(shù)構建functiondragDiv（）{}），同時清除原單元格和目標單元格的樣式，并且清除提示圖層（函數(shù)構建function hideDiv（）{}）。

考慮到在同一個時間段可能有很多教師通過遠程網(wǎng)進行排課，為了減少了數(shù)據(jù)傳輸量，提高Web響應速度，采用Ajax技術，這樣用戶提交信息時不必刷新整個頁面，而是可以進行并發(fā)操作，在不重載頁面的情況與web服務器交換數(shù)據(jù)，大大減少通訊的數(shù)據(jù)量，加快系統(tǒng)的反應時間，給用戶帶來全新的感受。

4.2沖突檢測

為了避免沖突首先要保證機房資源的正確分配，教師申請機房時，先創(chuàng)建教學任務，程序自動判斷能開設該課程的機房是否存在，存在則顯示，反之則不顯示。其次，就是檢測沖突，方法是“先判斷后安排”，即先對機房課表的時間片進行遍歷，從而獲得機房課表中每個時間片的ID，當ID非“0”時才能排課，在課表編排過程中無需回溯，進而能夠從根本上切實保證編排出的課程表絕對沒有沖突。

5.研究的主要成果

5.1主要功能模塊

系統(tǒng)的主要功能模塊如圖2所示。系統(tǒng)ER圖，如圖3所示。

5.2主要功能模塊的實現(xiàn)

5.2.1教師排課

系統(tǒng)設計時將一天劃分為12個時間片，每個時間片為一堂課。上課節(jié)次與星期X形成一張二維表，教師首先創(chuàng)建一個教學任務，程序自動判斷教師申請的課程允許在哪個機房使用，并且顯示出能夠開設該門課程的機房，反之則不顯示。教師用鼠標選擇機房，點擊創(chuàng)建的任務，點擊相應的時間段，即可完成排課工作。如圖4所示：

對于同等級別的用戶，系統(tǒng)采用先來先服務的方式工作，系統(tǒng)自動進行沖突檢測。

5.2.2排課結果

教師排課結束，系統(tǒng)自動生成教師個人的上機安排表以及全部機房上機安排表。匿名用戶可以直接查詢上機安排表。教師查詢上機安排表，選擇機房空閑的時間段自主排課，實驗人員查詢上機安排表為后續(xù)的實驗課程做好充分的準備工作，學生查詢上機安排表選擇機房空閑的時間段零星上機。

5.2.4課表調(diào)度

對于教師已申請的課表，admin用戶有權進行調(diào)整。選擇周次，選擇機房，用鼠標拖動課程到所需要的位置，如圖6所示粉紅色為拖動后的位置，點擊保存按鈕即可。

6結束語

本系統(tǒng)在合肥工業(yè)大學計算機基礎實驗室正式投入使用已經(jīng)四年多了，系統(tǒng)運行穩(wěn)定，顯示的結果正確，其設計目標得以實現(xiàn)。它對于穩(wěn)定實驗教學秩序，提高實驗教學質(zhì)量，起到十分重要的作用。系統(tǒng)通過靜態(tài)設置任務的優(yōu)先級，劃分時間片，動態(tài)遍歷相關資源的算法，同樣適合于其他需要安排時間表的場合，例如非機房實驗室的排課，會議室的安排等。