黃藝燕 洪星星 孫燕君

摘 要：本科教育綜合改革提出培養(yǎng)跨學(xué)科人才，鼓勵學(xué)生在全校范圍內(nèi)跨越院系自由選課，一人一張課表。排課作為選課的基礎(chǔ)保障，如何順利實(shí)現(xiàn)跨院系選課、避免選課沖突，成為近年來高校排課工作中比較突出的困難。本文探析了排課問題的實(shí)質(zhì)，分析了北京大學(xué)的排課機(jī)制，提出了優(yōu)化排課制度的舉措。

關(guān)鍵詞：排課機(jī)制;大學(xué)教學(xué)改革;自由選課;跨院系選課;自動排課系統(tǒng)

北京大學(xué)本科教育堅持以學(xué)生成長為中心，秉持“加強(qiáng)基礎(chǔ)、促進(jìn)交叉、尊重選擇、卓越教學(xué)”教育理念，實(shí)施了包括修訂完善專業(yè)培養(yǎng)方案，凝練核心課程體系，建設(shè)跨學(xué)科專業(yè)、跨學(xué)科項目、交叉課程模塊等多層次、有特色的人才培養(yǎng)項目，支持學(xué)生在完成各專業(yè)畢業(yè)所需最低學(xué)分要求的基礎(chǔ)上修讀輔修或雙學(xué)位，逐步建立起了全面自由的選課制度，允許學(xué)生跨院系自由選課[1]。北京大學(xué)2016版教學(xué)計劃的特點(diǎn)是，將其他院系的專業(yè)核心課納入本專業(yè)的自主選修課模塊。這部分學(xué)分既屬于專業(yè)的主修學(xué)分，同時也可以用來申請其他院系的輔修證書。這種可以兩邊認(rèn)定學(xué)分的方式，使得學(xué)生有更大的動力去修讀其他院系的核心課程。新的輔修、雙學(xué)位管理辦法規(guī)定，輔修、雙學(xué)位專業(yè)課程與同專業(yè)主修課程同質(zhì)要求，同質(zhì)管理。雙學(xué)位和輔修不再采用過去那種利用周末針對性開班排課的方式，而是和主修專業(yè)同班上課。另外，輔修采取申請制，事先不報名，通過跨院系選課的方式修讀課程。在畢業(yè)審查階段，完成了輔修教學(xué)計劃的學(xué)生可以向相關(guān)院系申請輔修證書?？缭合颠x課量的增加，導(dǎo)致選課時間矛盾日益凸顯。為此，學(xué)校教務(wù)部通過制定排課時間和考試時間對應(yīng)規(guī)則，約束選課沖突和考試沖突問題。同時，通過院系教務(wù)辦公室統(tǒng)籌、協(xié)調(diào)上課時間，解決院系內(nèi)專業(yè)必修課時間沖突問題。

一、排課問題和排課機(jī)制

1.排課問題

排課問題作為多元約束問題，涉及的資源有教師、學(xué)生、教室。約束條件有：（1）同一個教室在同一個排課單元只能上一門課。

（2）同一位老師/學(xué)生在同一個排課單元只能上一門課。（3）一周的總排課單元是有限的。

（4）一個學(xué)校的教室總數(shù)是有限的。（5）一間教室的容量是有限的。（6）教室必須滿足課程的容量和類型要求。

排課問題本質(zhì)上是一個時間表問題。時間表是圖論中的經(jīng)典問題，幾十年來一直是許多學(xué)者研究的熱點(diǎn)。1963年Gotlieb將其定義為多元約束問題，并用形式化的語言進(jìn)行描述并構(gòu)建了數(shù)學(xué)模型，但當(dāng)時沒有找到有效的解決辦法。1976年S.Even通過證明指出，課表問題屬于NP完全類問題。這表明我們無法在有限時間內(nèi)找到全局最優(yōu)解[2]。此后，教育工作者和計算機(jī)專業(yè)人士的研究工作主要致力于給出局部最優(yōu)解的啟發(fā)式算法并取得了一些成果，例如模擬退火算法、禁忌搜索算法、遺傳算法以及蟻群算法等。目前，這些排課算法在全國各高校也有應(yīng)用，具有代表性的是清華大學(xué)的TISER（Timetable Scheduler）系統(tǒng)、浙江大學(xué)的正方現(xiàn)代教學(xué)管理信息系統(tǒng)等。北京大學(xué)于20世紀(jì)90年代自主研發(fā)了第一代排課系統(tǒng)，后經(jīng)不斷維護(hù)更新，于2005年前后開發(fā)了基于模擬退火算法的排課系統(tǒng)。

2.各高校主流的排課機(jī)制

目前，在國內(nèi)高校中主要存在兩種排課機(jī)制：一級排課和二級排課。

一級排課指的是由高校教務(wù)處負(fù)責(zé)編排課表，二級學(xué)院負(fù)責(zé)協(xié)助和核對、確認(rèn)工作。這種排課模式早期比較流行，它的優(yōu)點(diǎn)是效率高，調(diào)整性強(qiáng)，不易沖突。一級排課模式比較適用于辦學(xué)規(guī)模不太大，資源分配權(quán)集中在教務(wù)處，而院系級個性化需求不高的高校。

二級排課指的是由高校教務(wù)處統(tǒng)籌協(xié)調(diào)課表的編排工作，由二級學(xué)院教務(wù)辦公室或者教務(wù)人員負(fù)責(zé)課程的安排，將課程執(zhí)行計劃錄入信息系統(tǒng)中。教務(wù)處借助信息系統(tǒng)分配資源，再對個性化需求的課程輔以人工調(diào)整。二級排課模式的優(yōu)點(diǎn)是將排課任務(wù)分解，理清高校教務(wù)處和學(xué)院之間的權(quán)限和責(zé)任，各司其職，有效分解了排課壓力，降低了排課的難度，特別適用于辦學(xué)規(guī)模較大，個性化要求較高，資源沖突比較突出的高校[3]。近年來這種模式逐漸推廣，已成為國內(nèi)主流的排課模式。北京大學(xué)從90年代后期就開始采用二級排課模式。這種模式不僅有效地分解排課難度，而且尊重教師的上課意愿，充分發(fā)揮院系的自主協(xié)調(diào)能力。

3.北京大學(xué)現(xiàn)有的排課機(jī)制

北京大學(xué)將排課工作分為課程容量、時間排布階段和教室分配調(diào)整兩個階段。教室分配調(diào)整采用系統(tǒng)協(xié)助分配，輔以少量的人工后期調(diào)整。學(xué)校現(xiàn)在使用的排課系統(tǒng)建設(shè)于2005年前后，采用的是給定時間下的模擬退火算法，主要解決教室資源的排布問題，以實(shí)現(xiàn)最大化利用教室資源。同時，由系統(tǒng)保證教室不沖突，避免教學(xué)事故[4]。

在課程容量和時間排布階段，院系教務(wù)辦公室根據(jù)歷年的經(jīng)驗(yàn)積累，人工排定課程的上課時間和上課人數(shù)，并錄入系統(tǒng)。院系教務(wù)辦公室在排課時需要遵循的原則有：（1）同年級同專業(yè)的專業(yè)必修課不沖突。（2）同專業(yè)不同年級必修課不沖突。（3）同年級同專業(yè)的必修、選修不沖突（盡量不沖突）。（4）同年級全院必修和所有各專業(yè)的必修不沖突。（5）不同年級的全院必修盡量不沖突，等等。上述五條原則的優(yōu)先級由高到低，根據(jù)實(shí)際情況按順序盡量滿足。

但上述這些原則沒有考慮到跨院系選課、輔修以及雙學(xué)位學(xué)生的選課需求。近年來，隨著教學(xué)改革不斷深入和自由選課制度逐步完善，北大已經(jīng)不是過去那種專業(yè)課由院系統(tǒng)一安排（同一個專業(yè)的學(xué)生統(tǒng)一上相同時間、相同地點(diǎn)的課程），僅公共課自由選擇的機(jī)制，面臨著一個學(xué)生一張個性化課表的復(fù)雜問題。以往單靠院系教務(wù)辦公室人工協(xié)調(diào)課程時間分布的排課模式受到了很大的挑戰(zhàn)。在排課問題上需要突破舊有的經(jīng)驗(yàn)，尋求更廣泛、更靈活的排課方法。

二、排課時間問題的制度調(diào)整

在高校教學(xué)管理中，排課的具體實(shí)施因校而異。各校排課機(jī)制首要是適應(yīng)本校的資源情況、權(quán)責(zé)分工情況，最關(guān)鍵的是要能保障學(xué)校的教育教學(xué)理念落地。排課算法理論研究大多考慮的是排課問題的學(xué)術(shù)特點(diǎn)，為了方便將其模型化、形式化描述，會忽略現(xiàn)實(shí)中的各種復(fù)雜因素和差異化問題，比如教師偏好、學(xué)生偏好、課程特點(diǎn)、教室資源、信息系統(tǒng)基礎(chǔ)情況等。因此，在選擇排課算法的時候，要考慮各校的具體情況，并針對實(shí)際情況，對排課機(jī)制和具體實(shí)現(xiàn)算法做出調(diào)整和優(yōu)化。

在深化本科教學(xué)改革，實(shí)現(xiàn)“以學(xué)生成長為中心”“立德樹人”大背景下，筆者通過研究北大現(xiàn)行的排課機(jī)制和排課數(shù)據(jù)，發(fā)現(xiàn)現(xiàn)有的機(jī)制存在改進(jìn)空間。

1.排課時段的分布調(diào)整

根據(jù)2016—2017年春季學(xué)期開課情況，我們統(tǒng)計了本科教學(xué)班的時段排布情況，發(fā)現(xiàn)每天的3～4節(jié)課和7～8節(jié)課是排課的熱門時段。這兩個熱門時段的課程班級數(shù)占比接近50%，而1～2節(jié)課程的班級數(shù)占比為15.5%，這表明在當(dāng)前排課機(jī)制下存在著排課時段利用率不足的

假如課表在時段排布上再均勻些，那么從宏觀角度來看，學(xué)生在時間上的選課自由度就會增加，這樣可以一定程度上減少時間沖突。因此從2017—2018學(xué)年開始，我們在排課制度上增加了對排課時段的要求，原則上各時段應(yīng)均勻排課，適當(dāng)增加1～2節(jié)時段的課程，同時限制熱門時段課程在院系所有排課時段總量的占比。對于超過比例的，學(xué)校教務(wù)部門在審核執(zhí)行計劃時不予通過，最終審核不通過的院系將無法參與安排教室。以下是排課制度中關(guān)于排課時段的相關(guān)規(guī)定：

為給學(xué)生選課提供更多的選擇，各院系課程應(yīng)合理安排好時間，排課時應(yīng)統(tǒng)籌安排各時段課程。原則上各時段均勻排課，尤其要增加1～2節(jié)時段的課程。

各院系安排在3～4節(jié)時段的課程不能超過院系所有排課時段總量的20%。不符合以上要求的，系統(tǒng)審核執(zhí)行計劃時不予通過。最終審核不通過的院系將無法參與安排教室。

上述制度開始執(zhí)行后，院系的排課時段分布漸漸趨向均勻，整體上相對合理。但是該制度在執(zhí)行過程中依然遇到了一些挑戰(zhàn)，例如受授課教師的意愿、習(xí)慣等因素影響，院系拒絕調(diào)整上課時段，或一些課程找不到合適的時段安排。另外，我們不得不承認(rèn)，宏觀上分布相對均勻的課表，并不等于微觀上學(xué)生選課就不沖突，不等于學(xué)生就能順利選上需要選的課程，更不代表學(xué)生就對課表的排布滿意。

那么，什么才是真正的好課表？怎么排課才是讓人滿意的課表呢？

2.關(guān)于課表優(yōu)劣的衡量

好的課表可以讓每個學(xué)生順利完成四年教學(xué)計劃，而更優(yōu)的課表是學(xué)生在完成四年培養(yǎng)計劃基礎(chǔ)保證上，還可以自由選上自己想選的課程。

課表優(yōu)劣的衡量指標(biāo)應(yīng)該包含：（1）學(xué)生所在專業(yè)教學(xué)計劃要求的課程能順利選上。

（2）學(xué)生主觀上喜歡上的課，不會因?yàn)闀r間沖突而無法選。第一點(diǎn)是一張合格的課表必須滿足的硬性指標(biāo)，而第二點(diǎn)是一個主觀性指標(biāo)，難以具體獲得，并且人人滿意的課表在現(xiàn)實(shí)中是不存在的。從教學(xué)管理角度看，應(yīng)該讓盡可能多的學(xué)生順利選上教學(xué)計劃所要求的課程。

假如用數(shù)據(jù)挖掘的方法去分析教學(xué)計劃的數(shù)據(jù)和學(xué)生的歷史選課數(shù)據(jù)，是否對我們的排課有所啟發(fā)呢？因?yàn)閷W(xué)生需要選什么課，這個信息在教學(xué)計劃中已經(jīng)給出答案。而學(xué)生喜歡上什么課程，在歷史選課數(shù)據(jù)中也可以捕捉到一定的證據(jù)支持。所以，借助計算機(jī)的運(yùn)算能力挖掘數(shù)據(jù)，啟發(fā)排課時間分配，算出來的課表會優(yōu)于院系教務(wù)辦公室的人工排課。

3.對人工安排課時的分析

我們觀察和分析了院系教務(wù)辦公室人工安排課時的具體操作，發(fā)現(xiàn)每個排課工作人員并不是在一張全空白的紙上排布全院的課程，而是在上年度相同學(xué)期排課結(jié)果的基礎(chǔ)上進(jìn)行當(dāng)前學(xué)期的排課工作。具體包括：與原有課程的授課教師確認(rèn)是否照以往時間安排上課;尋找新的合適的上課時間，分配給新開設(shè)的課程。當(dāng)發(fā)現(xiàn)沖突的時候，人工尋找調(diào)整空間。這表明，課表排布本身就是一個每學(xué)年都在迭代、優(yōu)化的過程。因此，我們借助計算機(jī)安排課表時，歷史的排課數(shù)據(jù)也是我們分析和提取有用信息的數(shù)據(jù)源。

三、排課再優(yōu)化

排課再優(yōu)化是指通過學(xué)校往年排課數(shù)據(jù)，結(jié)合各院系專業(yè)教學(xué)計劃，挖掘出課程間關(guān)系，找出哪些課程是學(xué)生傾向于同一學(xué)期選修。然后，再利用啟發(fā)式排課算法求解課表，避免出現(xiàn)專業(yè)課上課時間沖突的情況。這樣排出的課表將很好地支持學(xué)生的跨院系選課和輔修，以及雙學(xué)位選課，也減少了教務(wù)排課的人力勞動。

1.挖掘歷史選課數(shù)據(jù)，分析學(xué)生選課行為，得出課程對子

北京大學(xué)每學(xué)期專業(yè)課的選課數(shù)據(jù)占全部選課數(shù)據(jù)60%左右，約6萬條。這里面隱藏著學(xué)生的選課行為模式，例如一些專業(yè)課經(jīng)常被哪些專業(yè)的學(xué)生一起選，我們將這樣的課程稱為課程對子。當(dāng)同時選課人數(shù)達(dá)到某個值的時候，我們需要關(guān)注并盡可能在排課時將上課時間錯開。這樣，我們從選課數(shù)據(jù)挖掘出課程對子，并作為排課時分配上課時間的參考依據(jù)。

2.對歷年來主修與輔修、雙學(xué)位的修讀情況進(jìn)行數(shù)據(jù)分析，得出專業(yè)對子

我們經(jīng)過研究發(fā)現(xiàn)，主修和雙學(xué)位的修讀存在一定的聚集性。例如，數(shù)學(xué)學(xué)院、物理學(xué)院學(xué)生更傾向于選信息學(xué)院的雙學(xué)位，而光華管理學(xué)院、經(jīng)濟(jì)學(xué)院學(xué)生更傾向于選數(shù)學(xué)的雙學(xué)位課程。這就要求學(xué)校在排課的時候，要更多地考慮將這些院系相應(yīng)的專業(yè)課程排布開，以避免沖突。我們對現(xiàn)有的雙學(xué)位修讀情況進(jìn)行分析，以得出類似的專業(yè)對子。

3.分析教學(xué)計劃的課程模塊，挖掘跨院系選課的潛在需求

教學(xué)計劃定義了完成專業(yè)學(xué)習(xí)所必需的所有課程及學(xué)分規(guī)則，這是學(xué)生選課的依據(jù)。北京大學(xué)2016版教學(xué)計劃除了凝練專業(yè)核心課這一最大特點(diǎn)之外，還有一個創(chuàng)新的做法，即每個專業(yè)都將學(xué)部內(nèi)或?qū)W部外其他院系的專業(yè)核心課程納入本專業(yè)教學(xué)計劃的自主選修模塊中。這樣的教學(xué)計劃意味著學(xué)生有了明確的跨院系選課要求。分析每個專業(yè)教學(xué)計劃中其他院系的專業(yè)核心課，就可以挖掘出學(xué)生潛在的跨院系選課需求。在排課階段，這部分?jǐn)?shù)據(jù)具有很好的指導(dǎo)意義。

4.分析歷史排課數(shù)據(jù)，挖掘課程的排課規(guī)律，繼承良好的時間排布經(jīng)驗(yàn)

通過分析歷年的排課數(shù)據(jù)，會發(fā)現(xiàn)一些課程有著特殊而相對穩(wěn)定的排課習(xí)慣，而這些習(xí)慣是需要保持的。例如，部分院系開設(shè)的平行班需要設(shè)置在同一時段，以方便統(tǒng)一安排考試;許多通選課、公選課每學(xué)期都固定排在某一天的某一節(jié)課;一些數(shù)學(xué)類課程傾向于安排在上午，而許多通選課、公選課等傾向于安排在晚上。這些好的排課經(jīng)驗(yàn)，需要計算機(jī)排課系統(tǒng)繼承下來。

5.自動排課系統(tǒng)

在完成上述幾項數(shù)據(jù)分析之后，我們著手開發(fā)一個自動排課系統(tǒng)，將挖掘出來的課程對子、專業(yè)對子當(dāng)成排課的規(guī)則集合，通過計算機(jī)自動搜索的方式進(jìn)行排課。院系只需事先錄入專業(yè)必修課程的班級情況，在時間上只填寫一周上幾次課、每次課連上幾節(jié)的需求，便可由系統(tǒng)自動分配出建議的上課時間。從尊重教師意愿、滿足其授課時間要求的角度，我們還要求自動排課系統(tǒng)允許教師設(shè)置有關(guān)上課時間的具體期望，并按意愿強(qiáng)度設(shè)置備選的若干個時段，以便更好地滿足教師的教學(xué)需要。

我們邀請計算機(jī)專業(yè)的三名學(xué)生建立了自助排課系統(tǒng)的模型，并利用系統(tǒng)的自動運(yùn)算搜索獲得了2017—2018學(xué)年第一學(xué)期的課表。在此過程中，我們以圖染色算法為起點(diǎn)，逐步考慮各種跨院系選課、主修和輔修/雙學(xué)位、課程的排課習(xí)慣等因素，進(jìn)而優(yōu)化算法求解課程的時間排布。同時，我們創(chuàng)新性地增加點(diǎn)權(quán)和邊權(quán)。點(diǎn)權(quán)賦值參考的是歷年排課數(shù)據(jù)中的排課習(xí)慣、排課規(guī)律，邊權(quán)賦值參考的是上述數(shù)據(jù)挖掘中計算出來的課程對子、選課的熱度等。

相較于往年教務(wù)手工排課，自動排課系統(tǒng)排課出來的課程分布結(jié)果更加均勻。過去教務(wù)人工排課有一定的集中性，上午1～2節(jié)課安排比較少，周一3～4節(jié)課和周三3～4節(jié)課安排最多，超過了270個教學(xué)班;而自動排課系統(tǒng)排出來的課表相對均勻，排課最多的是周一1～2節(jié)課和7～8節(jié)課，有225個教學(xué)班，好于人工排課。

參考文獻(xiàn)：

[1] 孫燕君，賀熙. 自由選課背景下高?？荚嚬芾韱栴}的探索——北京大學(xué)的實(shí)踐[J].北京大學(xué)教育評論：2014年高等教育管理?？?，2014（12）.

[2] 陳輝，何軍. 排課問題的數(shù)學(xué)模型研究[J].沈陽工程學(xué)院學(xué)報（自然科學(xué)版），2017，13（3）：273-274.

[3] 劉慧，崔澤永，郭嘉. 基于我校實(shí)際的二級排課管理模式研究[J].科教文匯，2018（1）：117-118.

[4] 耿幼平，方明，陳光. 模擬退火算法在排課問題中的應(yīng)用[C]//中國高等教育學(xué)會教育信息化分會第九次學(xué)術(shù)年會論文集，2008.

[責(zé)任編輯：夏魯惠]