開放教育排課問題約束分析與數學建模

錢海軍 郭澤睿

摘 要：高等教育教學管理信息化是高校提高競爭力的關鍵因素。開放教育作為一種成人性質的高等教育類型，教育資源的非均衡配置限制了開放教育的發展。高校排課問題是一個多目標、多約束的資源與時空組合優化問題。排課問題的求解能夠實現教育資源優化配置。本文基于開放教育的特點與教育資源的需求情況，以排課問題為切入點，分析排課問題的各種約束條件，利用數學方法構造求解排課問題的數學模型，為后續智能排課系統的設計與開發提供算法基礎。

關鍵詞：教學管理信息化；開放教育；多約束；數學模型；智能排課系統

中圖分類號：TP301.6 文獻標識碼：A

Abstract：Informationization of higher education teaching management is the critical factor to improve the competitiveness of colleges and universities.Open education，as a type of the adult higher education，is restricted by the unbalanced allocation of educational resources.Course arrangement is a combination-optimization problem of multi-constraint and multi-objective resources and space distribution.The solution to course arrangement can optimize the allocation of educational resources.Based on the features of open education and the requirements of educational resources，the paper takes course arrangement as the breakthrough point to analyze the constraints of course arrangement and construct the mathematical model of course arrangement，which provides some algorithm foundation for the design and development of the intelligent course arrangement system.

Keywords：teaching management information；open education；multi-constraint；mathematical model；the intelligent course

arrangement system

1 引言（Introduction）

隨著高等教育體制改革的不斷深化，高校信息化建設成為提升教育教學水平、提高管理效率、保證教學質量、全面增強學校綜合競爭力的關鍵因素。“十三五”規劃發展期間，同屬于國家高等教育序列的開放大學正在逐步進行結構調整和教學模式的轉型與優化。培養目標、專業設置、課程設置等方面的重新定位，教育教學資源的優化配置，為開放教育教學管理提出了更高的要求。隨著教學模式的改革、學生人數的日益擴大、開設專業的不斷創新、開設課程的不斷增多，教師教室資源的相對減少等因素，嚴重制約了開放教育的發展。尤其對于排課工作，傳統的手工排課由于上述制約因素無法編制有效地課表，一方面造成人力和物力的極大浪費，工作效率不高，保密性較差，文件數據維護、更新難度大，教學資源沒有發到最優化配置。另一方面，手工編制的課表會因為人為的錯誤而擾亂正常的教學秩序。因此，有效解決具有開放教育特征的排課問題[1]，編制科學的課程表是提高開放教育教學管理水平的關鍵。

2 問題描述（Problem description）

實際上排課管理工作可以歸結為基于時空組合的教學資源分配問題[2，3]。排課問題是一個復雜難解的非線性、多約束、模糊多目標優化的數學問題，且已經被證明是一種NP完全問題[4]。高校作為一個教學實施的整體，編排課程表需要考慮全校性的、多方面的因素，包括教師、教室、課程、班級、時間等對象，也就是說在滿足一系列的約束性條件的前提下，使得學校教學資源能夠得到最優化配置。

開放教育是以學生為中心，運用現代通信技術與各種多媒體進行遠程教育和面授相結合，并實行學分制的教育類型。學生對課程的選擇、媒體的適用具有一定的自主性。在學習方式、學習進度、學習地點、學習時間等方面，可由學生根據自身的情況自主決定；學生基本來自在職人群，學生修讀完本專業規定的畢業學分，頒發國家承認的本、專科學歷證書?；谶@些特征，開放教育的課程均安排在周一至周五的晚上，周末的白天與晚上。由于開放教育強調學生的自主性學習，面授課程時間通常僅為課程總學時的1/3—1/2，面授課時較少，學生的工學矛盾較突出。

排課的最終目的是合理安排教師、教室、時間等教學資源。開放教育的特殊性要求排課應在滿足各種教學資源需求的基礎上，編制可行性較高的課程表，盡量減少各種資源之間的沖突[5]，實現資源的優化組合[6]，緩解學生的工學矛盾，幫助開放教育學生的有效性自主學習。

3 問題描述（Problem analysis）

開放教育屬于成人高等教育性質，學生的學習以自主學習方式為主，具備多元化的特征。學校需要為學生提供相對完備的學習支持服務。因此，開放教育的排課問題復雜性高，考慮的因素較多。

3.1 排課因素分析

要編制出較為科學合理的課程表，則需要從整體的角度進行綜合分析，系統地考慮影響排課的各種教學因素。本研究主要從幾個因素進行分析。

（1）教學任務分析

開放教育的教學仍然延續原電大系統三級分工協作的現代遠程開放教育教學和教學管理機制。學校每學期開放教育的教學任務以國家開放大學與省開放大學的專業規則為核心文件，結合學校自身的教學資源配置情況，分別落實每個專業本學期開設的課程。

（2）授課時間分析

開放教育屬于成人繼續學歷教育的國家高等教育序列。排課過程中需要關注的時間因素包括：節次、上課時間段、教學周、天數。由于開放教育自身的特征，其上課的時間段、天數、節次與普通高校的安排有較大的區別。為了有效緩解成人繼續教育的工學矛盾，減少學生接受面授課的次數，開放教育授課時間一般為業余時間，把每個班級的課程主要安排在周末的白天，及平時的晚上，詳見表1。

一般來講，為了有效利用資源，開放教育設置15個教學周。部分課程如果與國家法定節假日沖突，則按照相關教學管理的要求，該課程當周的教學順延一周。

（3）教師分析

開放教育的教學特點決定了教師類型具有多樣性。學校以專任教師、兼任教師兩部分來構建開放教育師資隊伍。其中。兼任教師的師資來源主要由外聘（校外）教師和校內雙肩挑教師（承擔行政管理與教學的雙重工作任務）組成。按照學校相關制度要求，雙肩挑教師所承擔教學任務周學時不能超過6學時/周，專任教師基本工作量為144學時/學期，周學時8學時/學期。

（4）課程分析

課程是最基本的排課單元，具有課程編號、教學班級、教室類型、周學時、任課教師、起止周等屬性。開放教育的課程設置具有明顯的成人教育特征，各專業所開設的課程均由開放教育專業規則進行整體描述和設計。在開放教育專業規則中，課程從課程類型、課程性質、課程模塊三個維度進行定義和描述，詳見表2。

表2 開放教育課程屬性劃分

Tab.2 Attribute division of open education curriculum

定義和描述維度 劃分類別

課程類型 統設課、自設課、省開課

課程性質 必修課、選修課

課程模塊 公共基礎課、專業基礎課、專業課、通識課、專業拓展課、綜合實踐

其中，統設課是由國家開放大學開設的課程，這些課程由國家開放大學管理，實行統一課程名稱、統一教學大綱、統一教材、統一考試和統一評分標準。省開課由省開放大學管理，在全省電大系統內實行“五統一”，參加省電大統一命題考試。自設課則由市級電大管理，自選教材，自行命題考試。對于相同名稱的課程，由于其歸屬類型的不同，課程編碼也不相同，比如《基礎會計》，會計、工商管理專科是統設課，課程編碼是2003，而在旅游管理專業，屬于省開課，課程編碼是5857。

“以學生為中心”的開放教育采取多元化的現代教學手段為學生提供自主性學習的全方位學習支持服務。學校根據開放教育的學生的特點，課程的教學環節設置較靈活，形式多樣。所有課程均設置唯一的課程編碼與課程名程。通常每門課程聘請一位授課教師。開放教育實行春、秋兩季的本科與?？仆瑫r招生的機制。在這種招生制度下，每學期開設的課程數量較大，尤其是公共課程在每個學期都會開設。為了能夠優化教學資源配置，提高教學質量，公共課程的排課一般都采取合班教學，有些高校也稱為大班教學。一門課程可能會有面授輔導、實驗實訓、小組協作、小組討論等多種教學環節的設置。課程學時分配上，主要包括135學時、90學時、45學時、21學時（精講課）等類型。為了給學生提供較完備的學習支持服務，各教學任務安排的教室盡量固定，尤其是對于英語語音、計算機應用基礎、計算機類課程、會計電算化等實踐環節較多，實踐能力要求較高的課程來講，需要盡量固定教室與教室的類型，這樣學生與教師能夠逐漸熟悉和適應教學環境與教學設備。

（5）教室分析

教室具有教室類型和容納人數等屬性。學校的教室類型分為普通多媒體教室、多媒體機房、專業實訓室、聽力語音室和多功能階梯教室。每間教室都具有唯一的教室編號。階梯教室適合安排公共基礎課，如中國特色社會主義理論概論、管理學原理、政治經濟學、大學英語等課程。其他類型的課程在某一個教學時段內僅安排一門課程，根據班級人數的多少可能會出現合班教學的情況。

3.2 數學描述

學校排課問題的解決與優化取決于學校教學資源的合理配置。主要涉及教師、班級、課程、教室和上課時間段等五個要素。假設學校有M位教師、N個班級、S門課程、P個教室與Q個上課時間段。根據排課問題五個要素的特點，本研究以集合的列舉法方式表示這五個要素，則排課問題的數學模型描述為：

專業人才培養方案（或稱為教學計劃）是學校教育教學工作的核心文件。由專職教學管理人員通過對人才培養方案的全面理解與深度分析后，編制學校學期開課計劃，確定該學期專業或班級所對應的課程和授課教師。根據開課計劃，排課所涉及的班級、課程、教師三個核心因素被唯一確定。借助

數學工具，可以定義一個三元組，即E=

Professors>，其中Stugroups、Courses、Professors分別表示班級、課程、教師三個集合。從這個意義上講，學校排課問題就被轉化成為該三元組E搜索到一個合適的“教室與教學時間段”配對的問題。

“教室與教學時間段”的優化組合問題可以通過教室集合Classrooms與教學時間段集合Times的乘積得以解決。在數學中，利用笛卡兒積描述集合的乘積，則集合Classrooms與集合Times的笛卡兒積表示為：

CT=Classrooms×Times={（R1，T1），（R1，T2），…，（R1，TQ），

（R2，T1），（R2，T2），…，（R2，TQ），…，（Rp，T1），（Rp，T2），…，

（Rp，TQ）}

4 約束條件分析（Constraint condition analysis）

對于排課這種組合規劃問題，需要通過設置合理的約束條件來實現最優解[7]。根據對排課問題的分析，可以將約束條件分為硬約束和軟約束[8]。硬約束條件是衡量排課方案可行性的標準，即課程表是否能夠切合實際的執行；軟約束條件則是描述排課方案質量優劣和滿意度高低[9]。在一定的約束范圍內，排課方案滿足軟約束條件的數量越多，編制的課程表滿意度與合理性就越高，課程表最優化程度也越高。

4.1 硬約束條件分析與建模

通過對開放教育教學過程與教學資源分析，本研究提出以下幾個硬約束條件：

（1）HConstraint1：在同一教學時間段內，同一個班級不能開設一門以上的課程；對于任意教學時間段，∈Times，

（4）HConstraint4：班級的學生人數應小于等于上課教室可容納的人數；對于任何一間能夠上課的教室，則。

（5）HConstraint5：課程必須滿足對教室類型的需求。學?，F有教室：多媒體機房、多媒體教室、計算機網絡實訓室、會計電算化實訓室、ERP沙盤演練實訓室。

4.2 軟約束條件分析與建模

排課問題的軟約束條件的優化目標是實現能夠較科學、較合理的排課規則，增強教學效果，提升教學水平和質量。滿足軟約束條件是衡量排課問題優化的關鍵，通過對教學任務、授課時間、教師、課程和教室等方面進行分析與整理，可以得出多個目標條件。從學校實際的情況出發，主要關注以下幾個軟約束條件。

（1）SConstraint1：上課時間段與教學效果有直接的關系。在課程編排過程中應盡量將較重要的課程安排在課堂教學效果較好的上課時間段?；陂_放教育教學的特征，將一個教學周劃分為11個時間段，詳見表1。開放教育學生接受面授教學的時間段具有一定的規律性，本文通過對某個學期學生周到課率數據進行收集、統計和處理，得到如表3所示的開放教育學期平均到課率。

從表3數據可以看出，除了周末的完整時間段之外，學生到校接受面授教學比較集中的時間段從高到低進行排序：星期一、星期四、星期二、星期三、星期五。為了提高教學質量，可以認為學生較集中的時間段安排較重要的課程。

假設用表示授課時間段的優先級，其中，，表示安排星期一；，表示安排星期四；，表示安排星期二；，表示安排星期三；，表示安排星期五；星期六和星期天的全天時間段按照課程特點整體安排。

假設表示課程在整個專業規則中的重要程度，可以用課程的權重來描述。其中，“1”表示通識課，“2”表示專業拓展課，“3”表示綜合實踐、“4”表示專業課，“5”表示專業基礎課，“6”表示公共基礎課。則約束條件優化目標為：

（2）SConstraint2：根據學期教學的執行計劃，盡量滿足部分教師提出的上課時間與教室屬性的要求。教師按照職稱的級別分為高級（教授、副教授、研究員、副研究員、高級實驗師）、中級（講師、工程師、實驗師）、初級（助教）等三個級別。

假設職稱的級別系數為，值分別是1，2，3；同時假設教師在規定時間段上課的意愿程度系數為，其中“2”表示愿意，“1”表示可以接受，“0”表示不愿意；則約束條件優化目標為：

（3）SConstraint3：根據開放教育的學生特點，針對多學時課程（≥45學時，周學時≥6），授課時間應盡量保證間隔一天以上，這樣可以有效保證面授教學的學習效果。假設一門課程的授課時間間隔為i天的教學效果系數為，設定1，2，3，4，5天的系數值分別為1，4，5，3，2，為課程的權重，則約束條件優化目標為：

（4）SConstraint4：同一課表中班級的課程密度盡量均勻。由于開放教育教學時間的限制，本約束僅考慮班級的周課時分配的合理性，即應避免某個班級某一周課程較多而另外一周課程較少的情況。某個班級的周課時分布均勻程度為：

其中，ed班級GN在第d周上課的課時數，則約束條件優化目標為：

其中，N表示全校班級的總數。

（5）SConstraint5：教室利用率最大化，即根據班級學生的人數分配教室。假設某個班級人數為xN與教室可容納的學生人數為yS之間的比值，比值越大，教室利用率越高，最大值為1，則約束條件優化目標為：

5 結論（Conclusion）

本文基于開放教育的特征與排課工作的特點，以整體的角度考慮教學資源的分配問題。通過對排課關鍵因素的綜合分析，提出問題并建立數學模型，解決開放教育教學資源優化配置問題，實現了排課問題的數學描述，為后續采用人工智能算法開發和設計排課系統提供理論基礎。

參考文獻（References）

[1] Adewumi A O，Sawyerr B A，Montaz A M.A Heuristic Solution to the University Timetabling Problem[J].Engineering Computations，2009，26（8）：972-984.

[2] Pillay N，Banzhaf W.A Study of Heuristic Combinations for Hyper-heuristic Systems for the Uncapacitated Examination Timetabling Problem[J].European Journal of Operational Research，2009，197（2）：482-491.

[3] S.Yang and S.N.Jat.Genetic Algorithms and Local Search Strategies for University Course Timetabling[J].IEEE Transactions on Systems，Man，and Cybernetics，Part C：Applications and Reviews，2011，1（41）：93-106.

[4] Shi Juan.Research on Application of IGA （Immune Genetic Algorithm） to the Solution of Course-timetabling Problem[C].Proceedings of 2009 4th International Conference on Computer Science and Education，Nanning，China，2009：1105-1109.

[5] 徐錦國.基于遺傳算法的排課系統研究[D].西安：西安石油大學，2010.

[6] 蘇明杰，陳建勛.基于線性規劃模型的高校排課系統[J].微計算機信息，2011，27（8）：197-200.

[7] Abuhamdah A，Ayob M.Multi-neighborhood Particle Collision Algorithm for Solving Course Timetabling Problems[C].Proceedings of the 2nd Conference on Data Mining and Optimization，2009：21-27.

[8] 張學平，朱顥東，吳洪麗.基于三維免疫遺傳算法的高校排課問題研究[J].計算機工程與應用，2012，48（5）：217-220.

[9] 朱顥東，李紅嬋.采用十進制最佳個體置換遺傳算法求解高校排課問題[J].計算機工程與科學，2011，33（6）：186-190.

作者簡介：

錢海軍（1979-），男，碩士生，副教授.研究領域：系統理論，

數據挖掘.

郭澤睿（1998-），男，本科生.研究領域：應用數學.