特殊要求時間段的排課問題數學模型

楊子蘭，李 睿，張 瑜

(云南大學 旅游文化學院，云南 麗江 674199)

特殊要求時間段的排課問題數學模型

楊子蘭，李 睿，張 瑜

(云南大學 旅游文化學院，云南 麗江 674199)

本文對排課問題的約束條件進行深入分析，將教師、班級、課程捆綁成一個教學任務單元，并以比較重要的課程盡可能地安排在授課效果較好的節次中且多學時課程安排要盡量均勻分布為目標函數，建立0-1整數規劃模型，最后結合自然班固定教室的特點，設計出啟發式算法求其可行解。

捆綁式排課；整數規劃；教學任務單元；啟發式算法

1962年Gotlieb提出了課表編排問題的數學模型[1]，從而使之成為計算機軟件應用專家和數學家共同研究的課題。1975年S.Even和cooper等人將排課問題理論化，證明了排課問題是NP完全問題[2]，當問題的規模增大時，其復雜度呈指數增長，在一般的實際情況中不可能準確地求出最優解。我國對于排課問題的研究始于20世紀80年代。1984年，林章希和林堯瑞發表了在排課問題上的實驗性研究成果[3]。2006年，任克強等給出了一種基于約束滿足的高校排課問題模型，提出了高質量排課系統方案[4]。2011年，宗薇根據教師、學生、教室、課程和課程時間段要求建立一個多約束條件的高校排課數學模型，采用隨機可行排課法產生可行排課方案，然后利用遺傳算法在可行方案中尋找最優排課方案[5]。2012年，楊彥明等人針對軍隊任職院校課程表編排特點，在分析軍隊任職院校排課因素、約束條件以及求解目標等問題基礎上，建立相應數學優化模型，構建其基本求解框架，并利用遺傳算法解決該問題[6]。2014年張麗麗等人在深入分析排課模型基礎上，采用三維立體編碼，提出基于三維立體遺傳編碼設計的排課系統，但是收斂速度過于緩慢[7]。2016年顧治程等利用FFD算法思想，提出只考慮教室分配問題的新算法[8]。周靖靖和楊梅以全體教師的滿意度最大為目標函數建立了0-1整數規劃模型，并以實例驗證了模型的實用性[9]。

上述文獻中的算法大多是遺傳算法，遺傳算法是模擬達爾文生物進化論的自然選擇和孟德爾遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優化的方法[10]。但遺傳算法比較復雜，且排課問題的約束條件較多時，遺傳算法可能找不到解。因此，本文分析排課問題的硬性約束條件，為得到較好的數學模型，特將教師、班級、課程捆綁成一個教學任務單元，并以比較重要的課程盡可能地安排在授課效果較好的節次中且多學時課程安排要盡量均勻分布為目標函數，建立0-1整數規劃模型，最后結合自然班固定教室等特點，設計出啟發式算法求其可行解。

1 問題描述及數學模型

1.1 問題描述

排課問題涉及多方面的問題，涉及到的因素主要有教師、班級、課程、教室、時間等五項基本因素，排課問題就是要尋求把這五個因素各自組合起來的一種方案，且這五項基本因素必須遵守以下硬性條件：（1）同一個時間點，每個班級最多安排上一門課程；（2）同一個時間點，每個老師最多安排上一門課程；（3）同一個時間點，每個教室最多安排上同一門課程；（4）教室上課人數不超過其最大容量；（5）每個班級的每個科目在一周內的課時數必須等于該門課程的課時要求。

1.2 建立數學模型

1.2.1 時間段編號

為得到較好的數學模型，特對時間段進行編號，且對時間段的編號不是按時間順序編號。具體如下：將一周分為5個工作日，每天設為5個時間段，分別為上午 8：00～9：50為 1-2節課；上午10：10～12：00 為 3-4 節課；下午 2：30～4：20 為 5-6節課；下午 4：30～6：20為 7-8節課；下午 7：30～9：20為9-10節課。這樣，每周五天工作日共有二十五個時間段。為了方便，特將25個時間段劃分為五種類型，并進行編號，如表1所示。

表1 時間段編號

1.2.2 變量描述

設教師集合表示為T={T1,T2,…,Ti,…,Tm}（m個教師）；教室集合表示為 R={(R1,r1),(R2,r2),…,(Ri,ri),…,(Rn,rn)}（其中 Ri表示第 i個教室，ri表示第i個教室的容量，即該教室所能容納的人數）；課程集合表示為P={P1,P2,…,Pi,…,Pw}且已按課程重要程度排序（即當i＜j時，pi比 pj重要，且共有w門課程），與P對應的w門課程的周學時數依次為l1,l2,…,lw；時間段集合表示為 π={1,2，…,i,…,25}（25個時間段）；自然班級集合表示為C={(C1,c1),(C2,c2),…,(Ci,ci),…,(Cq,cq)}（其中 Ci表示第 i個班級，ci表示第i個班級的人數）。

1.2.3 數學模型

排課問題對應到數學上就是將五個集合重新排列組合，構成一個大集合，且大集合里的每個元素必須體現某班某時間由某老師在某教室上某課程的信息，這個重新的組合涉及到的最大難度就是沖突問題。一般情況下，由于每個學校某學期的開課計劃中已經安排好某教師上某班的某門課程的信息，故排課過程中可以直接利用這些數據資源。本文利用捆綁式排課的方法，即將教師集合T、班級集合C、課程集合P捆綁成一個教學任務單元TCP（假設教學任務單元已按課程重要程度排序，教學任務單元的總數| TCP|=l），教室集合R為一個單元，時間集合π為一個單元。因此，排課的主要問題變成了如何安排時間段和教室，實現某時間段某教學任務單元最多對應一個符合需求的教室，即遵守上述約束條件。為方便建立數學模型，引入三維0-1決策變量xijt，當第i個教學任務單元在第t個時間段在第 j個教室上課時xijt=1，否則xijt=0，則任一教室在同一時間段至多安排一個教學任務單元上課可用數學式子表示為

每周內每個教學任務單元對應的課程上課時間要等于該門課的周課時可用數學式子表示為

同一時間段至多有n個教學任務單元在n個教室上課可用數學式子表示為

第i個教學任務單元在第 j個教室上課時需滿足該教學任務單元中的教學班級人數ci不超出教室 j的容量rj可用數學式子表示為

在遵守上述基本條件的前提下，排課應該盡量滿足教學任務單元的優化安排需求，以便課程的安排盡可能地科學、合理。本文參考文獻[6]中的方法，用 Bj′(j′=1′,2′,3′,4′)表示課程的重要程度，也稱為權重，把課程劃分為專業核心課、專業基礎課、公共課程、專業選修課和全院選修課(設對應于教學任務單元TCP中的課程順序前m1門課為專業核心課，第m1+1至第m2門課為專業基礎課，第m2+1至第m3門課為公共課程，第m3+1至第m4門課為專業選修課，第m4+1至第m5門課為全院選修課)，為了體現出重要程度，假設其權重依次賦值為 4、3、2、0.6、0.4。所以當 j′=1′時，有B′=4（即當1≤i≤m1時有 Bi=4）；當 j′=2′時，有B′=3（即當 m1＜i≤m2時有 Bi=3）；當 j′=3′時，有B′=2（即當 m2＜i≤m3時有 Bi=2）；當 j′=4′時，有B4′=0.6（即當 m3＜i≤m4時有 Bi=0.6）；當j′=5′時 ，有 B=0.4（ 即 當 m＜i≤m時 有5′45Bi=0.4）。用 at′(t′=1′,2′,3′,4′,5′)表示課時質量，其中當 t′=1′時 a′=1表示第一個時間段(即第1、2節)的教學質量，故當1≤i≤5時有 ai=1；當 t′=2′時，有 a′=0.8表示第二個時間段(即第3、4節)的教學質量，故當 6≤i≤10 時，有 ai=0.8；當 t′=3′時，有 a′=0.6表示第三個時間段(即第5、6節)的教學質量，故當11≤i≤15時，有 ai=0.6；當 t′=4′時，有 a′=0.3表示第四個時間段(即第7、8節)的教學質量，故當16≤i≤20 時，有 ai=0.3；當 t′=5′時，有 a′=0.1表示第五個時間段(即第9、10節)的教學質量，故當21≤i≤25時，有ai=0.1。對于周學時較多的課程，要盡量將其間隔一天（含）以上安排。用ei(i=1,2,3,4)表示一門課程安排間隔i天的教學效果系數，設定間隔1、2、3、4天的值分別為 1、3、4、2。

本文考慮比較重要的課程要最大程度地安排在授課效果較好的節次中且多學時課程（周學時大于等于3）的安排要盡量均勻分布為目標函數，得出三維的0-1整數規劃模型如下：

2 算法設計

在以往的排課算法中，往往不考慮課程的時間段要求，且大多采用遺傳算法[6-8,11-12],本算法以比較重要的課程盡可能地安排在授課效果較好的節次中且多學時課程安排要盡量均勻分布為目標。假設課程i的周學時li是2的奇數倍或偶數倍，則原來的教學任務單元就視為個教學任務單元，假設課程i的周學時li是2的分數倍，則原來的教學任務單元就視為個教學任務單元，得到擴展后的教學任務單元集合S={s1,s2,…,sl}，其含有l個教學任務單元且設S中的元素已按課程的重要程度排序（此時S中有相同元素），其中si表示第i個教學任務單元。假設有q個自然班級，每個自然班都有固定的教室，普通課程都可以安排在相應的自然班教室上課，這樣就不用考慮教室的安排及容量問題。因此，本算法只考慮在普通教室上課的情形，且每個學校某學期的開課計劃中已經安排好某教師上某班的某門課程的信息，故排課過程中可以直接利用這些數據資源，考慮這些因素，設計出如下啟發式算法：

初始條件下，記S1=S，取 j=1。

第1步:在Sj中按順序選出與教學任務有沖突的教學任務單元，記為Sj+1，且令S(j)=Sj-Sj+1，當Sj+1≠Φ時，轉第2步，否則轉第3步；

第2步：將S(j)中的教學任務單元依次安排在第i個時間段且在對應的自然班固定教室上課，記，表示由第i個時間段在對應的自然教室上課的教學任務單元時間對構成的集合，令i=i+1，當i＜25時，令 j=j+1，轉第 1步開始處，否則無可行解；

第3步：將S(j)中教學任務單元依次安排在第i個時間段且在對應自然班固定教室上課，轉第4步；

第 4 步：在 ?S(j)′中按元素順序依次選出周課時數為2的分數倍的課程對應的教學任務單元，按照選出順序號，規定順序號為偶數的教學任務單元單周不變，雙周減一次課，順序號為奇數的教學任務單元雙周不變，單周減一次課，轉第5步；

第 5 步：輸出 ?S(j)′，算法停止。

算法復雜度分析：第1步的復雜度取決于與前面教學任務有沖突的教學任務單元個數，復雜度最多為O（|S|）；第2步最多循環25次（此時無可行解），復雜度不超出O（25| S(j)|）；第 3 步的復雜度取決于在第i個時間段被安排上課的教學任務單元個數，復雜度最多為O（|S(j)|）；第 4 步的復雜度取決于周課時數為2的分數倍的課程對應的教學任務單元個數，復雜度最多為；算法第5步復雜度為。故算法總復雜度不超出O（25|S|）。

3 算法有效性驗證

表2列出了我校信科系下學期的部分教學開課計劃表。對表2進行擴展后的教學計劃表如表3所示。

表2 信科系下學期的部分教學開課計劃表

表3 信科系下學期的部分教學開課計劃擴展表

為了方便，表3中的每個教學任務單元都用對應的序號表示，則教學任務單元集合可以表示為，在S1中選出與前面的教學任務單元有沖突的教學任務單元構成一個集合，記為S2，即，則S(1)=S1-S2={1 ,3,6}，將S(1)中的教學任務單元依次安排在第1個時間段且在對應的自然班固定教室上課，得到 S(1)′={(1 ,1),(3,1),(6,1)}；在S2中選出與前面的教學任務單元有沖突的教學任務單元構成一個集合，記為 S3，即，則，將 S(2)中的教學任務單元依次安排在第2個時間段且在對應的自然班固定教室上課，得到；在 S3中選出與前面的教學任務單元有沖突的教學任務單元構成一個集合，記 為 S4，即，則，將 S(3)中的教學任務單元依次安排在第3個時間段且在對應的自然班固定教室上課，得到；在 S4中選出與前面的教學任務單元有沖突的教學任務單元構成一個集合，記為 S5，即，則，將S(4)中的教學任務單元依次安排在第4個時間段且在對應的自然班固定教室上課，得到 S(4)′={( 2,4),(4,4),(5,4),(7,4),(9,4)}；在 S5中選出與前面的教學任務單元有沖突的教學任務單元 構 成 一 個 集 合 ，記 為 S6，即，則，將 S(5)中的教學任務單元依次安排在第5個時間段且在對應的自然班固定教室上課，得到；在 S6中選出與前面的教學任務單元有沖突的教學任務單元構成一個集合，記為 S7，即，則，將 S(6)中的教學任務單元依次安排在第 6個時間段且在對應的自然班固定教室上課，得到S(6)′={( 2″,6),(4″,6)} ；在 S7中選出與前面的教學任務單元有沖突的教學任務單元構成一個集合，記為S8，即 S8= Φ ，則，將 S(7)中的教學任務單元依次安排在第7個時間段且在對應的自然班固定教室上課，得到S(7)′={(8′,7)} ；在 ?S(j)′中按元素順序依次選出周課時數為2的分數倍的課程對應的教學任務單元，按照選出的順序號，規定順序號為偶數的教學任務單元單周不變，雙周減一次課，順序號為奇數的教學任務單元雙周不變，單周減一次課，得到

即得到一個可行解，表2中的每個教學任務單元都已經被安排，從而驗證了算法的有效性。

4 結論

排課問題是一個多約束的組合優化問題，也是NP-完全類問題，很難找到多項式時間算法。本文對時間段進行特殊編號，將教師、班級、課程捆綁成一個教學任務單元集合，以比較重要的課程盡可能地安排在授課效果較好的節次中且多學時課程安排要盡量均勻分布為目標函數，建立0-1整數規劃模型，并根據自然班固定教室的特點，利用每個學校某學期的開課計劃數據資源信息，設計出啟發式算法求其可行解。該算法思想簡單，易懂，復雜度對多為O(25|S|)。如何進一步對算法進行豐富、修正，從而提高算法精度是本人今后將要開展的進一步工作。

[1]Gotlieb C C.The construction of Class-Teacher Time-Tables[J].Communications of the ACM,1962,5(6):73-77.

[2]Even S,Itai A,Shamir A.Onthecomplexityof timetableand multi-commodity flow problems[C].Proc of 16 thannual symposiumon foundations of computer science,1975:184-193.

[3]林漳希，林堯瑞.人工智能技術在課表編程中的應用[J].清華大學學報（自然版），1984，24（12）：1-8．

[4]任克強，趙光甫.基于約束滿足的高校排課問題研究[J].江西理工大學學報，2006，27（6）：70-72．

[5]宗 薇，趙光甫.高校智能排課系統算法的研究與實現[J].計算機仿真，2011，28（12）：389-392．

[6]楊彥明，岳翠翠，李其申．軍隊任職院校排課問題的數學建模[J].計算機與現代化，2012，11：14-17.

[7]張麗麗，許 峰，胡 娟．基于三維立體遺傳編碼設計的排課系統[J].重慶工商大學學報（自然科學版），2014，31（7）：9-13．

[8]顧治程，蔣 艷.基于FFD算法的高校排課系統設計與實現[J].軟件導刊，2016，15（1）：110-111.

[9]周靖靖，楊 梅.基于滿意度的最優排課方案[J].西南師范大學學報（自然科學版），2016，41（1）：185-187．[10]卓金武，李必文，魏永生，等.MATLAB在數學建模中的應用[M].2版.北京：北京航空航天大學出版社，2014：79．

[11]葉碧蝦．遺傳算法在排課系統中的優化研究[J].吉林師范大學學報（自然科學版），2014，2:185-187.

[12]Limkar S,Khalwadekar A,Tekale A,et al.Genetic Algorithm:Paradigm Shift over a Traditional Approach of Timetable Scheduling[C].Proceedings of the 3rd International Conference on Frontiers of Intelligent Computing:Theory and Applications(FICTA)2014.Springer International Publishing,2015:771-780.

Mathematical model of course scheduling problem with special requirements

YANG Zi-Lan,LI Rui,ZHANG Yu

（School of Tourism and Culture,Yunnan University,Lijiang Yunnan 674199,China)

This paper made an in-depth analysis of the course scheduling problem,bundled the teacher,class and course into a teaching task unit,and built the 0-1 integer programming model to maximize the effect of the teaching quality,and more school curricula will be evenly distributed as possible as the objective function.Finally,combined with the characteristics of natural classes of fixed classroom,a heuristic algorithm was designed to find the satisfactory solution.

binding scheduling;integer programming;teaching task unit;heuristic algorithm

A

1004-4329（2017）02-015-05

10.14096/j.cnki.cn34-1069/n/1004-4329（2017）02-015-05

2017-01-20

云南省教育廳科學研究基金項目（2016ZDX152）；云南大學旅游文化學院院級項目（2015XY08）資助。

楊子蘭（1985－ ），女，碩士，講師，研究方向：組合最優化與算法研究。