張健立，馮永祥

(1.集寧師范學院 計算機系，內(nèi)蒙古 烏蘭察布 012000；2.內(nèi)蒙古工業(yè)大學 信息學院，呼和浩特 010080)

?

集寧師范學院排課系統(tǒng)的設計與實現(xiàn)

張健立1，馮永祥2

(1.集寧師范學院 計算機系，內(nèi)蒙古 烏蘭察布 012000；2.內(nèi)蒙古工業(yè)大學 信息學院，呼和浩特 010080)

摘要：以集寧師范學院為例，分析排課中會涉及到的各個要素，同時考慮到排課中的基本約束問題和模糊約束問題，通過計算機模擬手工排課過程，實現(xiàn)自動排課功能，以期為大幅度提高教務人員的工作效率提供借鑒。

關鍵詞：手工排課；算法；排課約束

一、設計排課系統(tǒng)的背景及意義

近幾年來，隨著集寧師范學院招生規(guī)模的不斷擴大，學校所開設的專業(yè)和課程也在逐年增加，教學資源日益緊缺，教學管理任務也變得越來越繁重，其中排課問題是教務管理工作中一項重要且繁雜的任務。一個好的排課系統(tǒng)，不僅能夠讓教務管理工作人員擺脫煩瑣的手工排課工作，而且能夠在很大程度上提高工作人員的效率，節(jié)省工作時間[1]。因此，設計開發(fā)一個合理有效的自動排課系統(tǒng)，對于提高教務管理人員的工作效率是很有意義的。

二、排課系統(tǒng)的詳細設計

(一)排課問題中所涉及到的各種變量

排課問題中所涉及到的各種變量包括：時間、教師、課程、教室、班級等。

(二)排課變量之間的約束

排課涉及到兩種約束，分別是基本約束和模糊約束?；炯s束是指在排課過程中必須要遵循的原則，而模糊約束是要盡量堅持滿足的原則。

課表要遵循的基本約束條件有：同一時間段內(nèi)不能給一名教師安排兩門不同的課程[2]；同一時間段內(nèi)一個班級只能安排一門課程[3]；同一時間段內(nèi)一個教室只能安排一門課程；教室的最大容量應不小于上課的學生人數(shù)。

模糊約束條件有：根據(jù)課程類型以及學生的接受程度，來為這類課程安排最合適的時間段；如：專業(yè)課、必修課一般安排在早上，而文體類的課程通常安排在下午；理論性課程盡量分散安排，理論與實踐并重的課程最好將理論與實踐課穿插安排；學生的上課時間不能過分集中，應盡量避免某一天課程安排得很滿而另一天卻沒課的情況；考慮教師的工作負荷，一天內(nèi)上課一般不超過四節(jié)；教師或?qū)W生接連上兩門課程的地點盡量比較接近；對于教師、學生可能提出的一些特殊要求，根據(jù)情況安排，如若合理，盡量滿足。此外，對于計算機預排的結(jié)果，還可以根據(jù)實際情況，通過人工交互的方式進行修改。

(三)排課問題的求解目標

本文的目標是在滿足基本約束條件的情況下編排出無沖突的課表，并且編排出的課表盡可能多地滿足模糊約束條件，從而使得排出的課表是可行的，且盡量達到優(yōu)化。

使用計算機來排課，實際上就是要利用計算機來模擬人工排課的過程。進行手工排課，首先需要有三類表，分別為班級、教師以及教室課表。排課人員在對一門課程進行安排時，首先要確定這門課程的總學時，從而確定每周的課時數(shù)，然后在班級、教師以及教室的課表中選擇一個時間來安排這門課程。然而通常時間的選擇并不容易，排課人員要對與之相關的所有課表進行排列組合，并對其中部分課程的時間進行調(diào)整，直至形成最優(yōu)的解決方案。

(四)手工排課流程

首先每周一至周五為上課時間，每天分為8小節(jié)課，上午和下午各安排4節(jié)，每2小節(jié)作為1個課時單元。表中黑色部分表示這個時間段、這個班級、教師以及教室已經(jīng)安排了課程。若當前待安排課程為X(某專業(yè)課)，任課教師為Y，涉及的班級為Z，課程X每周要安排3次課，對X課程可以分為下面4個步驟來進行安排：

1.首先查詢班級Z的當前課表

排課人員可以在多種排列組合中選擇，同時由于考慮到學生在早上的學習效率會相對高一些，排課人員大多會優(yōu)先考慮將課程X安排到上午的1—2節(jié)，對于安排不下的課程則繼續(xù)選擇合適的時間點順延，同一門課程盡量不要安排在一起。假設在表1中，標記為“N”表示該時間段已安排課程，則按前面提到的要求，可考慮將課程X安排在星期一、星期三的1—2節(jié)，以及星期五的3—4節(jié)，標記為“Y”。

表1　班級Z課表安排

2.查詢?nèi)握n老師的當前課表

由于在第一步中已選擇星期一、星期三的1—2節(jié)和星期五的3—4節(jié)，此時對任課教師Y的時間安排進行查詢，教師Y的課表安排如表2所示。由于Y教師星期五3—4節(jié)已安排課程，所以需要回到第一步對表1中已安排好的課程重新進行安排。

表2　教師課程安排

3.查詢教室的當前課程安排時間表

表3為教室當前課程安排狀態(tài)?？紤]到前面兩步中所安排好的課程X的時間和班級Z的學生人數(shù)，在教室安排課表中找到可以滿足時間和座位需求的空教室，如果未能找到，則同樣需要回到第1步進行重新安排。

表3　教室課程安排

4.確定課程X的上課時間

根據(jù)以上3個步驟，即可確定班級Z所授課程X的上課時間和教室。

通過上面4個環(huán)節(jié)的不斷重復、調(diào)整，為所有教室、教師都已安排好課程。通過這些可以發(fā)現(xiàn)手工排課某種程度上能夠得到最優(yōu)排課方案，但是如果涉及大量課程，則各個課程之間難免會有時間上的沖突，同時反復不斷地調(diào)整涉及到的工作量非常大，最終又不一定能得到全局最優(yōu)解。

(五)排課算法流程

1.算法提出的假設條件

(1)一周只能上5天課，每天8節(jié)課。(2)一個系分成若干個專業(yè)，一個專業(yè)有若干年級。(3)所有教室資源硬性分配給不同專業(yè)的年級。也就是說，不同專業(yè)的不同年級的上課地點是相互獨立的。只能在自己分配的教室上課。(4)公共課只能是同一專業(yè)的同一年級的所有學生在同一時間同一地點一起上課。

2.排課算法流程

(1)連接SQL Server數(shù)據(jù)庫獲得課程信息、班級信息、教室信息、公共課程信息、系別信息。(2)計算學期的總共教學周和每周課時。(3)通過假設情況1規(guī)定：一周只能上5天課，每天8節(jié)課。并且控制同一天不能上2節(jié)同樣的課。將課程按照隔一天時間進行排課。如果課程數(shù)超過40，則表示學生所學課程數(shù)過多(輸出排課失敗信息)。(4)檢測同一天，多個班級同時上一個課程的沖突。當班級數(shù)較多時，每天上課數(shù)少于班級個數(shù)的課程，在進行課程節(jié)輪訓時會有沖突，不夠輪訓的用-1代替(熊婷，2006)。(5)設置同一天，不同班級的課程不能同時上課。并將同一專業(yè)，同一年級的所有課程排好。(6)調(diào)整公共課，檢測公共課要放的位置并重排公共課。(7)進行一個專業(yè)，一個年級的教室單元初始化分配。(8)安排班級去教室上課，進行沖突檢測，即檢查教室容納人數(shù)與班級人數(shù)是否符合。(9)檢測已經(jīng)排好的課中是否有教室沖突，并調(diào)整教室。(10)如果沒有沖突退出排課，并輸出排課結(jié)果。

三、結(jié)語

本文的排課算法實現(xiàn)了教師、教室、課程、時間等資源在教學活動中的合理配置與安排，大幅度地提高了教務人員的工作效率。雖然實現(xiàn)了自動排課功能，但是在實際應用中，還應該考慮到因為一些特殊原因?qū)е碌男枰止ふ{(diào)節(jié)課表安排的情況，所以在今后還需要完善這方面的功能。

參考文獻：

[1]大學教務管理系統(tǒng)設計[EB/OL].豆丁網(wǎng)，2013-09-21.

[2]汪力君.分治算法在排課系統(tǒng)中的分析與應用[J].安徽建筑工業(yè)學院學報：自然科學版，2007，(6).

[3]周芬.遺傳算法在多校區(qū)排課系統(tǒng)中的應用[J].科技信息,2010，(6).

(責任編輯：朱嵐)

中圖分類號：G642

文獻標志碼：A

文章編號：1001-7836(2015)01-0027-02

作者簡介：張健立(1978—)，男(蒙古族)，內(nèi)蒙古赤峰人，講師，碩士,從事計算機技術研究；馮永祥(1962—)，男，內(nèi)蒙古豐鎮(zhèn)人，計算機系副教授，碩士生導師。

基金項目:內(nèi)蒙古自治區(qū)高等教育科學“十二五”規(guī)劃課題“遺傳算法在高等學校智能排課問題方面的研究”(課題批準號:NGJGH2014083)

收稿日期：2014-11-10

doi:10.3969/j.issn.1001-7836.2015.01.013