張小紅

(湛江師范學(xué)院信息科學(xué)與技術(shù)學(xué)院，廣東湛江 524048)

高校教務(wù)工作中，排課是基本和重要的工作之一，其實質(zhì)是給教學(xué)計劃中設(shè)置的課程安排合適的時間和地點，保證教學(xué)工作順利進行。同時排課也是一項復(fù)雜的工作，涉及到教師、學(xué)生、教室等因素。在目前高校規(guī)模不斷擴大，教學(xué)資源緊張，教師總數(shù)不足的前提下，排課問題顯得尤為重要。

1 系統(tǒng)分析

1.1 排課的約束條件

(1)硬約束［2］。排課工作中應(yīng)遵守的規(guī)則:1)同一時間同一教師只能上一門課程;2)同一時間同一學(xué)生只能上一門課程;3)同一時間同一教室只能上一門課程;4)上課按最小的單位(節(jié))進行;5)某一課程被安排的教室座位數(shù)應(yīng)大于該門課程上課人數(shù)。

(2)軟約束。對排課的合理性和滿意性會產(chǎn)生影響的因素:1)一個班級的課程時間安排應(yīng)盡量分布均勻。2)一周的課程表中的每個時間有一定的裕度。3)教師對上課時間存在的期望;4)班級相鄰時間內(nèi)的上課地點盡可能近。5)體育課應(yīng)排在下午或上午3、4節(jié)，體育課后應(yīng)避免安排講授課。6)實驗、實習(xí)課程有其自身的排課方式。7)可先行手工排定某些課程的時間和教室。

1.2 系統(tǒng)需求描述

(1)以單個學(xué)生作為上課對象;(2)可以自動排課;(3)可以手工排課;(4)可以生成任意班級、任課教師和上課教室的課表;(5)可以提供教師、學(xué)生和教室管理者等查詢課表的接口;(6)可以設(shè)置不同操作者的系統(tǒng)使用權(quán)限;(7)可以形成報表，并以其他格式輸出。

2 系統(tǒng)設(shè)計

2.1 工作流程

高校的排課工作由教務(wù)處根據(jù)各院系制定的教學(xué)計劃，在每學(xué)期末生成下一學(xué)期的教學(xué)任務(wù)，并下發(fā)給各教學(xué)單位，審核上課的軟硬件條件約束，然后根據(jù)教學(xué)單位返回的學(xué)期教學(xué)任務(wù)，制定全校各班級的課表［3］?；玖鞒倘鐖D1所示。

圖1 排課系統(tǒng)工作流程

2.2 主要功能設(shè)計

排課系統(tǒng)的主要功能設(shè)計如下:

(1)教學(xué)資源管理。主要管理各類教室、實驗室、教學(xué)場館及場地的相關(guān)信息，對教學(xué)資源信息進行錄入、增加、修改、刪除等操作。

(2)課表框架設(shè)置。包括安排周學(xué)時、周數(shù)、學(xué)年、學(xué)期等上課的具體時間等。

(3)教學(xué)日歷管理。根據(jù)指定學(xué)期開始日期和結(jié)束日期，由系統(tǒng)自動生成教學(xué)日歷。

(4)排課相關(guān)條件設(shè)置。包括設(shè)置可排課時間、不可排課時間、課程性質(zhì)與排課時間之間的關(guān)聯(lián)。設(shè)置排課教室的類型與課程性質(zhì)之間的關(guān)聯(lián)。設(shè)置合班上課的時間、課程性質(zhì)及上課教室之間等關(guān)聯(lián)。

(5)特殊課程安排。對上課時間、地點有特殊要求的課程進行預(yù)先安排。

(6)智能排課。根據(jù)現(xiàn)有教學(xué)資源對所開設(shè)的課程自動合理的分配時間和教室等。

(7)手工排課。系統(tǒng)須具備手動處理排課結(jié)果的功能，即對系統(tǒng)己自動排好的課程或系統(tǒng)無法自動安排的課程，部門管理員在設(shè)定手動排課的時間內(nèi)進行手動調(diào)整或安排。

(8)課程更改處理。在實際操作中，可能因為一些客觀原因需對代課教師、上課的起止周或周學(xué)時等進行調(diào)整。

(9)停調(diào)補課處理。在實際教學(xué)過程中，停、調(diào)、補課現(xiàn)象時有發(fā)生，系統(tǒng)可對教師的停、調(diào)、補課進行實時安排。

(10)查詢統(tǒng)計處理。按照模塊中各種組合條件查詢上課情況并生成各類表格。

2.3 數(shù)據(jù)庫設(shè)計

(1)概念結(jié)構(gòu)設(shè)計

圖2 排課系統(tǒng)E－R圖

(2)邏輯結(jié)構(gòu)設(shè)計。根據(jù)概念結(jié)構(gòu)設(shè)計得到的E－R模型，該排課系統(tǒng)主要涉及到以下數(shù)據(jù)庫表:教師信息表、教室信息表、班級信息表、課程信息表、時間安排信息表和教學(xué)計劃信息表。

2.4 遺傳算法設(shè)計

文中采用的遺傳算法設(shè)計，根據(jù)系統(tǒng)的具體情況，對算法的實際使用做了適當(dāng)?shù)男薷?，具體設(shè)計步驟如下。

(1)染色體編碼:采用教師、班級、課程以及教室和教學(xué)時間段的組合作為染色體，即使用每個教師的課表作為染色體，盡可能地將課程表的各種類型沖突和各項常識表現(xiàn)在內(nèi)。

(2)產(chǎn)生初始種群:多個染色體組成”個體”，也就是一種排課方式。多個”個體”組成種群。根據(jù)課程多少，動態(tài)安排種群大小。

(3)沖突檢測和消除:對初始種群中的個體進行沖突檢測，如存在各類沖突，例如“一師多班”沖突、“固定時段”沖突等，則確定沖突的行、列，然后在同一行找另一隨機位置，將這兩個位置的數(shù)值互換。直至無沖突存在。

(4)計算適應(yīng)度值:按照適應(yīng)度函數(shù)計算適應(yīng)度值。

(5)選擇操作:按照適應(yīng)度值計算選擇率和期望的選擇數(shù)，進行選擇產(chǎn)生下一代種群。從選擇數(shù)的算式可知，具有較高適應(yīng)度值的父代更有可能在下一代中產(chǎn)生一個或多個子代。

(6)交叉操作:根據(jù)選擇操作的結(jié)果選取兩個較好的排課結(jié)果作為父體，將兩個染色體的上課教師和上課時間段進行交叉。

(7)變異操作:按概率決定變異的次數(shù)。對參與變異的個體隨機選一行，在該行隨機生成兩個變異的位置，然后將這兩個位置的教師編碼互換。值得注意的是當(dāng)這兩個編碼中至少有一個是固定教學(xué)時段碼時，則取消本次交換，重新執(zhí)行該步驟，直到交換完成。

(8)沖突檢測和再消除:經(jīng)過交叉和變異操作后，可能會產(chǎn)生沖突，因此要進行沖突再檢測，并解決沖突。

經(jīng)過一次遺傳算法步驟，新一代種群的適應(yīng)度值可能有所提高，問題的解便朝著最優(yōu)解的方向前進，將這個過程進行下去，最終將逼近全局最優(yōu)解，而每一步的操作較簡單，且對問題的依賴性較小。

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

通過智能排課功能模塊可以實現(xiàn)排課數(shù)據(jù)條件設(shè)置、系統(tǒng)智能排課、人機交互式排課、考試安排、調(diào)停補課申請?zhí)幚?、其他上課時間地點安排、查詢打印等功能。智能排課模塊子菜單的實現(xiàn)界面如圖3所示。

圖3 智能排課模塊主界面

系統(tǒng)自動排課后，用戶通過人機交互方式來調(diào)整教師上課時間地點，調(diào)整課程過程中系統(tǒng)將自動檢測沖突。對滿意的班級、教師或場地課表，用戶可直接預(yù)覽打印或輸出Excel。人機交互式排課功能實現(xiàn)界面如圖4所示。

圖4 自動排課功能界面

課程、教師、教室、班級優(yōu)先級設(shè)定，實現(xiàn)界面如圖5所示。

4 結(jié)束語

通過該系統(tǒng)可以較大程度上減少教務(wù)人員的工作量，避免手工排課可能導(dǎo)致的沖突，提高辦公效率。排課問題是一個多目標(biāo)的組合優(yōu)化問題，系統(tǒng)中還存在一些未能考慮到的實際問題，所有的約束條件也并未完全涉及，還需在實際應(yīng)用中不斷完善和改進。

圖5 課程、教師、教室、班級優(yōu)先級設(shè)定功能界面［4］

［1］ 李富星.自動排課系統(tǒng)的設(shè)計與實現(xiàn)［D］.西安:西安電子科技大學(xué)，2010.

［2］ 張長庚.基于遺傳算法的浙江水利水電?？茖W(xué)校排課系統(tǒng)設(shè)計與實現(xiàn)［D］.成都:電子科技大學(xué)，2010.

［3］ 蒲靜，陳華月，傅饒.通用排課系統(tǒng)的設(shè)計與實現(xiàn)［J］.福建電腦，2010(6):170－171.

［4］ 薩師煊，王珊.數(shù)據(jù)庫系統(tǒng)概論［M］.3版.北京:高等教育出版社，2000.

［5］ 李玉吉，盧才武，劉冠.蟻群遺傳算法在高校智能排課系統(tǒng)中的應(yīng)用［J］.現(xiàn)代電子技術(shù)，2010，33(14):129 －131.

［6］ 屈正庚，劉雅莉.基于TGC的高校排課算法［J］.電子設(shè)計工程，2011(8):22－24，27.