基于優先選擇算法的中職排課系統設計與實現

柯廣利

(廣東省海洋工程職業技術學校，廣東 廣州 510320)

0 引言

中等職業教育是中國教育體系的重要組成部分，其目的是為社會培養建設、生產、服務和管理方面的高級技術應用型人才。近年來，隨著社會的進一步發展和時代的進步，中等職業教育的課程向著應用型和更加迎合社會需求及就業的方向不斷靠近，這對各種模擬實際工作環境的實驗室的需求不斷增加，使中等職業教學的課程編排工作變得更加復雜。因此，在中等職業教學中按照不同時間和地點，安排不同教學環境的排課系統就顯得尤為重要，合理的課程編排不僅有利于師生的教學平衡，有利于日常教學工作的順利進行，有利于教學資源的有效利用，有利于教學質量的不斷改進和提高，而且對和諧校園的建設具有相當重要的作用。

本文以中等職業學校的教育體系為基礎，在中等職業學校排課系統中引入了數學模型，提出了一個以優先算法為基礎的排課算法。該算法系統能夠簡化課程編排的復雜程度，在較短的時間內得到一個滿意的課程編排結果，給中等職業教學工作的順利開展提供便利。

1 排課問題的一般描述

在中等職業學校的教學與管理中，課程表的編排工作是一項相當艱巨和復雜的任務。排課工作是在綜合考慮了上課時間、課程、上課使用教室、上課區域、院系、班級、教師等各種因素后進行的教學安排工作。經過優化的排課系統，在任意時間段內，教師的教學不沖突，授課的內容不沖突，上課的班級不沖突，教室的使用同樣也不沖突，并且在宏觀的層面上權衡了全校所有的課表。如何有效利用有限的教學資源和有限的師資力量，結合中等職業教育特點排出合理的課程表非常重要。計算機排課較繁瑣的手工排課有較大優勢，它能使教學信息一目了然，有利于提高教學效率和優化學生的學習進程，因此推行高效的計算機排課系統和算法尤為重要。

排課的基本要求就是避免教室、學生以及教師的沖突問題，即:同一時間點1名教師只能上1門課;同一時間點1個班級只能上1門課;同一時間點1個教室只能上1門課程。在課程編排優化上還要注意有些課程在時間點上有特定要求。一個好的排課系統不僅能減少或者消除這些沖突，而且還應很好地滿足教師和教學的要求。

一個好的排課系統必須滿足以下條件才能減少以下沖突的發生:

①在同一時間點，同一班級不能安排超過1門的課程;

②在同一時間點，同一教師不能安排超過1門的課程;

③在同一時間點，同一教室不能安排超過1門的課程;

④在同一時間點，課程門數不能超過教室數;

⑤在同一時間點，學習同一課程的人數不能超過該教室的座位數。

在滿足以上5條基本原則的基礎上，為了使得課程編排有更好的滿意度和體現人性化需求，還要滿足以下約束條件:

①在同一時間點，同一教室不能被超過1個班級使用;

②在同一時間點，同一教師不能給超過1個班級上課;

③在同一時間點，同一班級不能上超過1門課;

④同一班級1 d中同一門課不能超過3個課時;

⑤3個課時的課只能排在下午;

⑥周課時大于等于4個課時的課程盡量安排在相鄰的2 d完成。

2 優先選擇算法的設計與實現

2.1 自動排課的預處理

從數學模型的角度分析，排課系統問題實際上是在時間、教室、教師以及學生(班級)的四維空間中，在基本原則和約束條件下，以教學計劃為基本研究內容的數學規劃問題。從另一個角度來講，排課問題就是用來解決這四維空間相互之間的沖突的。首先是要對課程的數據和時間進行預處理，主要包括等價類的劃分和時間的預處理。

等價類的劃分。不是所有的人都會選擇同一門課，特別是專業課，大多是同一專業的學生選擇同一門課程。同一專業的學生，在不同的年級也不會同時選擇同一門課。因此，在課程編排上系統也應按不同的年級進行等價類的分類，即在同一等價的類中包括了選擇同一門課的學生。這樣就只是在地點上存在沖突，在這個層次下就可以對其他的每個類進行分類排課處理和分析。其好處在于能夠從大到小對每個類進行處理，降低算法的復雜程度，提高課程編排的處理速度。

時間的預處理。本文是采用八皇后模型，唯一的不同是將八皇后模型8×8的矩陣拓展到x×y×z的三維矩陣上來完成。本系統設定x為1周上課的天數，即x=5;把每天的上課時間分為4個時段(即每2節課為1個段)，即y=4;z則表示需要排課的班級數。原則是要使這些課程要包含在該xyz的矩陣中不發生沖突。

本系統定義時間代碼為 N=1，2，…，20，其中當N=1，2，…，5時表示星期一到星期五的一二節課，當N=6，7，…，10時表示星期一到星期五的三四節課，當N=10，11，…，15時表示星期一到星期五的五六節課，當N=16，17，…，20時表示星期一到星期五的七八節課。另外，定義G［N］＆T［N］＆C［N］=1，代表在第N時間段中班級、教室和教師可用;G［N］＆T［N］＆C［N］=0代表在第 N 時間段中班級、教室和教師不可用。當 G［N］＆T［N］＆C［N］=1時才滿足排課條件，且當 G［N］、T［N］、C［N］只有一個等于0，則滿足了約束條件①、②、③。

當課時長度等于3，N≥11時就滿足了約束條件⑤。當一個星期的課時長度大于等于4，本系統設前一次的課程時間為Z，則控制(Z-N)%5!=0，這樣就可以滿足約束條件④。|Z-N|≠1、4、6、9、11、14、16、19 且 Z!=0 的條件下滿足約束條件⑥。

2.2 優先選擇算法原理

算法原理是對給出的條件或限制進行逐一比較，直到算法結束。流程如圖1所示。在本例中按照預設條件進行預排課，矩陣 C［i，j］與T［i，j］進行比較，如果滿足條件就再與 R［i，j］比較，通過，則三矩陣表保存。如果不滿足條件，則繼續尋找符合條件的教室，找到則停止操作。如果T［i，j］不滿足條件，修改值并返回重新比較。

圖1 優先選擇算法流程圖

2.3 基于優先選擇算法的排課系統實現

1)設置課程編排的先后順序。目的在于使課程的信息表按周課時編排，且是按降序排列。

2)編排周課時為2、4、6課時的課程。設第一次排課的時間為Z，則要保證同一天中同一班級的一門課不超過3個課時就必須使得(Z-N)%5!=0;|Z-N|≠1、4、6、9、11、14、16、19 且 Z!=0的條件下就使得同一班級的一門課2次課排在相鄰的2 d中。

3)周課時為3課時的課程。當排課時間N≥11時，保證周課時為3課時的課程會在下午排課。

4)周課時為5課時的課程。此類課程分2次來編排，在排第1次時無約束條件，第2次按照周課時為3課時的課程編排，但是要求N≥11且(Z-N)%5!=0，這樣就可以保證連上3節的課安排在下午且不與上一次課程編排在同一天，|Z-N|≠1、4、6、9、11、14、16、19 且 Z!=0 的條件下就使同一班級的一門課2次課排在相鄰的2 d。

2.4 排課的后處理

一門課安排了一次課之后就必須進行以下后處理的工作，即:將課程相關的信息錄入排課的結果欄中;重新設計該課程的教師、班級和教室的相關可用時間。

為了保證下一次排課的成立，用“1”代表該時間段可用，“0”代表不可用，在排完課程之后就應使教師、班級和教室由“1”變為“0”。

3 防死鎖方法

死鎖是指在系統中查詢，正常的查詢命令不能找到可用的上課時間和地點。這里介紹防止死鎖的兩種類型。

3.1 順序死鎖

順序死鎖是指在安排一門課的時候可用的課時單元不足以滿足該課程的時間量。其原因是一門課程的編排受到了其他課程的約束。如圖2中2 個班級G1、G2 分別上課程C1、C2，且G1、G2 要共同去上課程C3，C1占用時間T1，C2占用時間T2，這樣就產生了C3不能編排的問題。

圖2 C1、C2、C3 的相互沖突

只要調整一下編排的順序就可用避免這種死鎖，將C3安排之后再去安排C1、C2，如圖3。在排課中根據周課時數來確定優先級，也可通過人工調整來決定課程的優先級。

圖3 調整優先級來防止死鎖

3.2 地點死鎖

地點死鎖是指在一個時間段上安排一門課時可用的地點不足以滿足該課程的要求。原因是指在可用的時間段上地點的使用不均或者是在座位多的教室安排了人數少的班級，防止死鎖的方法是在安排座位的順序時適當將可用的教室范圍減小，這樣就避免了使用不均或者是在座位多的教室安排了人數少的班級。

4 結語

本文以中等職業學校的教育體系為基礎，在中等職業學校的排課系統實例中引入了課程編排的數學模型，提出了一個以優先算法為基礎的排課算法。通過劃分等價類以及計算的優先級，將整個排課問題分層處理以降低算法的復雜程度，獲得了比較滿意的中等職業排課系統，實現了計算機自動編排課程的功能。

［1］陳誼，楊怡，張國龍，等.基于優先級自動排課算法PCSA的設計與實現方案［J］.北京工商大學學報，2002，20(2):32-35.

［2］業寧，梁作鵬，董逸生.一種基于遺傳算法的TTP問題求解算法［J］.東南大學學報:自然科學版，2003(1):41-44.

［3］蘭懷玉，馬若飛.一個自動編排課表系統的設計與開發［J］.中央民族大學學報，2002(7):167-178.

［4］楊怡.高等院校自動排課系統的設計與實現［D］.北京:北京工商大學，2001.

［5］黃干平，姚自珍，張軼靜.使用模擬退火算法解課表問題［J］.武漢大學學報:自然科學版，2000，46(5):559-563.

［6］何軍華.課表編排系統的算法研究與實現［J］.湖北師范學院學報，2003，23(1):84-87.