構(gòu)造人性化的排課算法

摘要：本文對現(xiàn)今部分教務(wù)管理系統(tǒng)中排課模塊的功能缺陷進(jìn)行了分析，闡述了編排課表的人性化理念，提出了在約束函數(shù)和目標(biāo)函數(shù)中分別加入優(yōu)化教師課表和學(xué)生課程表的人性化因子的設(shè)計思路，分析、研究并提出了一套可行的人性化排課解決辦法。

關(guān)鍵詞：人性化排課；回溯法；合理時間組合；累積疲勞系數(shù)；排課均勻系數(shù)

中圖分類號：G642.0 文獻(xiàn)標(biāo)識碼：B

文章編號：1672-5913（2007）06-0053-03

1 問題的提出

筆者多年從事教務(wù)管理工作，經(jīng)歷過十多年前每學(xué)期開學(xué)前的大規(guī)模手工排課，對其大強度腦力勞動和修改、調(diào)整課務(wù)的麻煩與低效率印象深刻。盡管知道課表問題在時間復(fù)雜度上屬于NP困難類問題，涉及的變化因素多，信息量大，編程比較困難，但還是在八年前就下決心寫了排課程序，對算法作過多次推敲和改進(jìn)，經(jīng)歷了從一開始追求能正確排出課表（只求有解），接下來追求能排出較合理的課表（在多解中選擇較佳解），再后來追求功能齊全、操作方便、極富挑戰(zhàn)性的設(shè)計過程。

隨著成套教學(xué)管理軟件的不斷推廣普及，筆者所在學(xué)校也用上了功能齊全、規(guī)模龐大的教務(wù)管理系統(tǒng)。但其中排課功能模塊的表現(xiàn)卻常常讓筆者不敢恭維。其中比較突出的，要數(shù)課表編排的人性化問題了。主要表現(xiàn)在總體時間結(jié)構(gòu)的選擇方面，經(jīng)常出現(xiàn)非常不合理的編排情況。比如，將一門課程的兩次課（每次2~3學(xué)時）安排在一天之中，導(dǎo)致學(xué)生在兩次課之間根本沒有時間去消化知識和完成作業(yè)；還比如，幾乎每學(xué)期都出現(xiàn)過將老師一周要上的大多數(shù)課程排在一天之中的“黑色周”課程表，使得老師每逢一周的某一天，就不得不從早到晚拼命上課，而在其他工作日中卻過于輕松愉快；在班級課表中，同樣明顯存在一周中的某一天課特別多，而有的天課又特別少的情況。其次，在對待不同門類的課程方面，也經(jīng)常出現(xiàn)不合理的上課安排。比如，將體育課排在上午第一節(jié)課，使許多剛剛吃完早飯的學(xué)生馬上就去進(jìn)行劇烈運動；還比如，在同一個班中，將專業(yè)主干課排在了非黃金時間（下午3~4節(jié)或晚上），而將較次要的選修課則排在了黃金時間，等等。

上述問題的出現(xiàn)，當(dāng)然是算法設(shè)計不當(dāng)造成的，主要是對人性化設(shè)計重視不夠，即在算法設(shè)計中對老師、學(xué)生及課程情況考慮較少，對教與學(xué)的規(guī)律尊重不夠。因此，構(gòu)造人性化的排課算法，編排出人性化的課表，是解決上述問題的關(guān)鍵。為此，筆者愿將前些年在排課問題上的個人研究心得概述如下，以期交流共進(jìn)。

2 算法人性化的基本原則

所謂課表編排人性化，筆者認(rèn)為，是指學(xué)校在編排課表時，要充分了解教師和學(xué)生的各種需求，充分尊重教與學(xué)的規(guī)律，尤其要充分考慮大多數(shù)教師從事課堂教學(xué)勞動的密度限制和強度承受能力。在此基礎(chǔ)上，編排出能最大限度地滿足各方需求的課表。為較好地解決此問題，除了要遵守為排出一般無差錯課表所要求的技術(shù)規(guī)則外，筆者認(rèn)為還應(yīng)遵守如下人本原則。

2.1 優(yōu)化結(jié)構(gòu)原則

這一原則主要包括兩點：

第一，是指優(yōu)化每門課程的授課時間結(jié)構(gòu)，這是課表編排人性化的基礎(chǔ)。比如，某一門周課時為4的課程，若將這4節(jié)課排在同一天之中，就是明顯的時間結(jié)構(gòu)不合理。若是分別排在周一、周三各上2節(jié)課，這種時間結(jié)構(gòu)就比較合理。為優(yōu)化課程的時間結(jié)構(gòu)，筆者在廣泛征求師生的意見后，以高校常見的每2課時為一個上課時間片（即一次課），分別專門編制了從每周上一次課到每周上五次課（周課為10節(jié)）的合理時間結(jié)構(gòu)代碼庫，剔除了師生們一致認(rèn)為明顯不合理的排法，并對同一周課時下各種不同的時間組合，按師生們認(rèn)可的優(yōu)先程度從高到低排序，賦予不同的優(yōu)先級，以方便排課程序首先從代碼庫中選擇最優(yōu)時間結(jié)構(gòu)信息，從而實現(xiàn)了每門課程授課時間結(jié)構(gòu)的優(yōu)化，為課表的整體優(yōu)化奠定了基礎(chǔ)。

第二，是指優(yōu)化排課的順序結(jié)構(gòu)，即合理地確定先排哪些課，后排哪些課。筆者曾經(jīng)作過對比試驗，發(fā)現(xiàn)采用不合理的排課順序，輕者會大大降低排課程序的運行效率，使程序運行時間成倍延長，重者則直接導(dǎo)致排課失敗。因而筆者認(rèn)為，確立良好的排課順序，是減少排課沖突、提高排課效率、確保排課成功的關(guān)鍵。經(jīng)多年實踐、比較與分析、歸納，筆者確定了“先難后易，先大后小，先多后少”的排課順序結(jié)構(gòu)。“先難后易”是指從總體上講，應(yīng)該先排牽涉面廣、資源要求高、統(tǒng)籌難度大的課，如多個教師在同一時間內(nèi)聯(lián)合上的跨班級，甚至跨年級的課，最典型的是多個班聯(lián)合分組教學(xué)的體育課、實驗課、實訓(xùn)課等；“先大后小”是指先排兩個或兩個以上班級在同一時間、同一教室合上大班課(即合班課)，再排小班課(即非合班課)；“先多后少”則是指先排有多個班課程的教師的課和總周課時多的教師的課，后排牽涉班級少、總周課時少的教師的課。

2.2 分類處理原則

這一原則指的是，為了使不同的課程獲得最適合的上課時間結(jié)構(gòu)，必須對課程進(jìn)行合理分類，然后為每一類課程設(shè)計出“量身定做”的專用排課算法。比如，可以將課程分為專業(yè)基礎(chǔ)課與專業(yè)課、實踐課、選修課等，理論課一般首先選擇上午1~2節(jié)、3~4節(jié)等黃金時間段，因為每天上午一般是師生精力最為充沛的時間段，故應(yīng)當(dāng)首先安排難度較大或較為重要的專業(yè)基礎(chǔ)課和專業(yè)課；實踐課一般首選上午3~4節(jié)或下午，而選修課則一般首選下午或晚上。

2.3 均衡編排原則

確立這一原則的主要意圖，是要在排課過程中，盡量避免教師或?qū)W生在一周中某一兩天內(nèi)連續(xù)上太多的課程，而其他天課又太少的大反差情況，以防止師生過度疲勞，影響教學(xué)效果和師生健康。因此，它包括教師課表的均衡性和班級課表的均衡性兩個方面。我采取了三項措施來貫徹這一原則。

第一，是為教師課表和班級課表分別設(shè)置日排課上限值。即為教師設(shè)置每天最高總授課節(jié)數(shù)，也為學(xué)生設(shè)置每天最大總上課節(jié)數(shù)。我校每天有5個可排課時間片：上午1~2節(jié)、上午3~4節(jié)、下午1~2節(jié)、下午3~4節(jié)、晚上1~2節(jié)，共10節(jié)課。顯然，無論是教師還是學(xué)生，都無法認(rèn)可把一天的10節(jié)課全排滿的算法，因而也把這兩個上限值列入調(diào)查內(nèi)容。經(jīng)過對部分師生所發(fā)放的調(diào)查問卷的匯總統(tǒng)計，筆者所得的這兩個數(shù)據(jù)分別為5.73和7.14，經(jīng)四舍五入后得到6和7。筆者將這兩個上限值寫入到了約束函數(shù)f1（T，C）之中，供排課程序在每作出一門課程的時間組合選擇時，調(diào)用它來作出相關(guān)評價。一旦發(fā)現(xiàn)其中任一個上限值被突破，則放棄本次選擇，繼續(xù)進(jìn)行下一時間組合的搜索。

第二，是為教師課表設(shè)置“累積疲勞系數(shù)”，用于比較和評判教師課表的整體優(yōu)劣情況。方法是先在為排課設(shè)置的教師課表矩陣T_m×n（設(shè)有m個教師，每個教師每周均有n個時間片，本算法中n=5×5=25）中增設(shè)一列初值為0的元素（第n+1列），用于存放每位教師課表的“累積疲勞系數(shù)”，如t_{i， n+1}（1≤i≤m）表示第i個教師課表的“累積疲勞系數(shù)”。該系數(shù)是這樣計算的：教師課表中每出現(xiàn)相鄰兩個時間片連續(xù)排課，相應(yīng)的t_{i， n+1}值就加1。很顯然，對于每一份教師課表，該值是一個非負(fù)值，并且越接近0越好，理想狀態(tài)是0；然后設(shè)計一個專用目標(biāo)函數(shù)f2(T)，用于在每排出一種方案后，統(tǒng)計出該方案中每位教師課表的累積疲勞系數(shù)和該方案的平均累積疲勞系數(shù)；再設(shè)計一個專用目標(biāo)函數(shù)f3(T)，用于在完成了一定數(shù)量（如2~8種）的排課方案后，找出其中最小平均累積疲勞系數(shù)所對應(yīng)的方案，即為教師課表最優(yōu)方案。

第三，是為班級課有設(shè)置“排課均勻系數(shù)”，用于比較和評判班級課表的整體優(yōu)劣情況。方法與上面類似，首先在班級課表矩陣S_k×n(設(shè)有 k個班級，每個班每周均有n個時間片)中增設(shè)一列初值為0的元素s_{i， n+1}(i∈{1，2，…k})，用于存放每個班級課表的排課均勻系數(shù)。筆者采用了班級每日排課節(jié)數(shù)的均方差作為該班的排課均勻系數(shù)。很顯然，該系數(shù)也是一個非負(fù)數(shù)，并且其值也是越接近0越好。同樣，在多個班級課表方案中，平均排課均勻系數(shù)最小的方案即為最優(yōu)方案。為此，筆者同樣設(shè)計了專用目標(biāo)函數(shù)f4(S)。

3 算法人性化的實現(xiàn)描述

筆者所構(gòu)造的上述人性化算法原則的實現(xiàn)，限于篇幅，主要簡介以下四點。

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

除與教師、班級、教室、課程等信息相關(guān)的數(shù)據(jù)庫表外，這里主要強調(diào)一下編制合理時間結(jié)構(gòu)庫的問題。即分別編制各種不同周課時下課程授課時間組合代碼庫，并確定其中每一組代碼的優(yōu)先級，存入專門的數(shù)據(jù)庫表中。編碼規(guī)則為：一周最大有5天可排課，每天最多有5個可用時間片；每兩位數(shù)碼表示一個選定的時間片，其中第一個數(shù)碼表示星期，第二個數(shù)碼表示時間片。比如，代碼“23”表示每周2的第3個時間片，即星期二下午第1~2節(jié)有課，如表1所示。在此過程中，筆者剔除了雖然理論上可行，但在調(diào)查中師生共同反對的不合理組合，比如周課時為4節(jié)的時間組合中，類似1112、1113、…，1415、1555等的代碼組合均被剔除。這里特別要說明的是，因特殊原因，特別指定的排課時間，如遠(yuǎn)道而來的外聘教師的突擊授課，則不受此限制，另有專門程序處理。

3.2 定義數(shù)據(jù)結(jié)構(gòu)

在排課程序設(shè)計中，除了需要多個數(shù)據(jù)庫表配合外，主要是需要定義兩種數(shù)據(jù)結(jié)構(gòu)：一是用于存儲排課方案矩陣的二維表結(jié)構(gòu)，共需定義三個，分別對應(yīng)教師課表矩陣T、班級課表矩陣S和教室課表矩陣R。二是用于存儲實際排課路徑的堆棧式線性表結(jié)構(gòu)。該堆棧的每個元素Pi由五項數(shù)據(jù)組成：教師號、課程號、教室號、班級號（最多允許存3個不同班級號）和時間組合序號（即所采用的時間組合代碼在數(shù)據(jù)庫表中的編號）。之所以要設(shè)計這種后進(jìn)先出的堆棧結(jié)構(gòu)，是為了配合在排課過程中所用的回溯法，實現(xiàn)對剛排定課程的取消操作，同時對該課程查找下一個可行排法。

3.3 約束函數(shù)和目標(biāo)函數(shù)設(shè)計

此項設(shè)計已在“均衡編排原則”中闡明，此處不再贅述。

3.4 排課核心程序算法設(shè)計

筆者所寫的排課程序，整體采用的是回溯算法。由于在搜索可行排法時，是從事先已優(yōu)化了的時間組合代碼庫中依次取值判定，所以這相當(dāng)于在局部采用了限界剪枝法的思想，因而既可提高課表局部質(zhì)量，即單課程編排質(zhì)量，又免除了需要設(shè)計局部目標(biāo)函數(shù)的麻煩。該程序主要算法步驟如下：

1）定義相關(guān)結(jié)構(gòu)體數(shù)組并賦初值（排課狀態(tài)二維表、路徑堆棧、完整路徑二維表（可存多個完整排課方案）、目標(biāo)函數(shù)值數(shù)組、課程序號計數(shù)器、時間代碼串序號計數(shù)器、排課方案序號計數(shù)器等）。

2）從相關(guān)數(shù)據(jù)庫表中獲取欲排課程信息（包括對不同類課程規(guī)定的時間代碼串的不同選取范圍，用優(yōu)先級數(shù)進(jìn)行限制）。

3）依次對每一門課程，從規(guī)定范圍的時間組合庫中按序獲取一個相應(yīng)時間代碼串，運行約束函數(shù)，進(jìn)行匹配判斷。

4）若滿足約束條件，則將相關(guān)信息分別存入教師課表、班級課表、教室課表等二維表和排課路徑堆棧后，進(jìn)入下一步5）；若不滿足約束條件，則判斷時間代碼串序號是否已到最大值：若是，則轉(zhuǎn)6）；若否，則對其值加1后，轉(zhuǎn)3）。

5）判斷課程是否全排完。若否，則課程順序號加1、課程時間代碼串序號重置1后，返回3）；若是，則將本次排課完整路徑值存入完整路徑二維表中，并調(diào)用目標(biāo)函數(shù)先分別進(jìn)行教師課表平均累積疲勞系數(shù)和班級課表平均排課均勻系數(shù)計算，然后按“平均累積疲勞系數(shù)×0.6＋平均排課均勻系數(shù)×0.4”合并成最終目標(biāo)函數(shù)值，存入目標(biāo)函數(shù)值專用數(shù)組，并標(biāo)記相應(yīng)方案號。最后，排課方案計數(shù)器加1。

6）從堆棧中取出剛排定的課程信息，進(jìn)行撤消排定操作。

7）判斷上一步撤消課程的時間代碼串序號是否已達(dá)最大值：若否，則對其值加1后，轉(zhuǎn)3）；若是，則當(dāng)其課程序號不為1（即尚未回到首門課程）時轉(zhuǎn)6），而當(dāng)其課程序號為1時，轉(zhuǎn)下一步。

8）掃描目標(biāo)函數(shù)值數(shù)組，找出最小值，查找對應(yīng)的方案號，然后按方案號找到相應(yīng)的完整排課路徑值，按此值建立相應(yīng)的課程表，并將其存入相應(yīng)數(shù)據(jù)庫表。

9）結(jié)束整個程序運行。

4 運行結(jié)果與結(jié)論

上述設(shè)計，經(jīng)反復(fù)調(diào)試、修改后，早已能排出相當(dāng)合理的課表。本文開頭所列舉的種種不合理情況，在本算法下可以完全避免。但是，本算法在剛開始調(diào)試時，曾經(jīng)“矯枉過正”，出現(xiàn)過無解情況。后來，經(jīng)過分析、計算，發(fā)現(xiàn)時間組合代碼庫中所存合理代碼種類不全，丟失了大量可用代碼，并且對不同類別課程選擇時間組合種類的限制過窄。于是有針對性地對部分時間組合代碼庫作了大量增補、優(yōu)化，并適當(dāng)放寬了對不同類課程所對應(yīng)的時間組合代碼的選擇范圍，比如允許主干課程在搜尋不到黃金時間（優(yōu)先級為1）的情況下，選擇非黃金時間中的較佳時間片（優(yōu)先級為2），也允許輔修課程在主干課程排表結(jié)束后將搜尋范圍由非黃金時間擴大到黃金時間（即優(yōu)先級為1、2、3均可），使問題得到較好的解決。

參考文獻(xiàn)：

[1] 齊德昱.數(shù)據(jù)結(jié)構(gòu)與算法[M].北京：清華大學(xué)出版社，2003.

[2] 周培德.計算中的基本理論與方法[M].北京：北京理工大學(xué)出版社，1997.

[3] 陳誼，楊怡，張國龍，等.基于優(yōu)先級自動排課算法PCSA的設(shè)計與實現(xiàn)方案[J].北京工商大學(xué)學(xué)報，2002，20（2）：32-35.

[4] 魯井蘭.高校課表編排的原則與要點探析[J].中國科技信息，2006，（1）：87-89.

收稿日期：2006-11-05

作者簡介：鄒躍（1958-），男，江蘇泰州，講師，主要研究方向：算法設(shè)計，數(shù)據(jù)庫應(yīng)用，操作系統(tǒng)教學(xué)設(shè)計。