基于學校滿意度的院系兩級排課問題數學模型

楊子蘭，李 睿，楊慧娟

（1.云南大學旅游文化學院信息科學與技術系，云南麗江 674199；2.昭通學院數學與統(tǒng)計系，云南昭通 657000）

隨著教育的不斷改革，高校的不斷擴招，排課問題變得越來越復雜。排課的主要任務就是根據學校每學期的開課計劃，針對全校不同類型學生的所有課程的時間、地點以及授課教師進行合理安排，確保不發(fā)生沖突。早在20世紀50年代末，國外就有人開始研究課表編排問題。到1975年S.Even和Cooper等人將排課問題理論化，證明了排課問題是NP-完全問題〔1〕，當問題的規(guī)模增大時，其復雜度呈指數增長，在一般的實際情況中不可能準確地求出最優(yōu)解。我國對于排課問題的研究始于20世紀80年代。1984年，林章希和林堯瑞發(fā)表了在排課問題上的實驗性研究成果〔2〕。由于每個學校的實際情況不同，目前還沒有一個可以通用的排課算法。近年來排課問題備受關注〔3-9〕，越來越多的學者采用了捆綁式排課的方法〔5，9〕。隨著高校的不斷發(fā)展，目前，很多高校具有多校區(qū)、多教學樓等特點，為適應高校的發(fā)展需求，越來越多的學校采用院系兩級共同排課的模式。鑒于此，根據院系兩級教務共同排課的特點，將教師、教學班級、課程捆綁成一個教學任務單元，擬建立基于學校滿意度的院系兩級排課問題數學模型。

1 問題描述

基于院系兩級任務的排課問題實質上是指由學校教務處和系部相關工作人員共同完成的排課問題：由各個系完成教學計劃，開課系部指定任課教師；公共類課程由教務處統(tǒng)一安排授課時間及地點，專業(yè)類課程由學生所在系部安排授課時間及地點。院系兩級共同排課模式比傳統(tǒng)排課模式更靈活、高效。由于每個學校某學期的開課計劃中已經安排好某教師上某班的某門課程的信息，故排課過程中可以直接利用這些數據資源。利用捆綁式排課的方法，即將教師集合、教學班級集合、課程集合捆綁成一個教學任務計劃單元，教室集合為一個單元，時間集合為一個單元。由此，排課問題就變成在時間和空間資源上合理安排教學任務單元的問題。故可對傳統(tǒng)的排課問題的硬約束條件進行簡化，得：（1）同一個時間點，同一個教學任務單元最多安排在同一個教室上課；（2）同一個教學任務單元中的教學班人數不超過其授課教室的最大容量；（3）同一個教學任務單元中的教學課程的課時數必須等于該門課程的課時要求。

2 時間段編號

為得到較好的數學模型，根據學校的教學時間段，對時間段進行編號，具體如下：將一周分為5個工作日，每天設為5個時間段，分別為上午8：30～10：10為1～2節(jié)課；上午10：30～12：10為3～4節(jié)課；下午2：00～3：40為5～6節(jié)課；下午4：00～5：40為7～8節(jié)課；下午7：00～8：40為9～10節(jié)課。這樣，每周5天，且周五下午不安排課，則5天工作日共有23個時間段。為了方便，特將23個時間段劃分為5種類型，并進行編號，見表1。

表1 時間段編號

3 變量說明

假設某高校屬于院系設置，目前有m個系，n個授課教師。根據院系兩級共同排課的特點，將教室資源劃分到各個系（即每個系都有專用教學教室），且已經對教室進行編號，則變量說明如下：

設教師集合表示為T={T1,T2,…,Ti,…,Tn}（n個教師）；教室集合表示為（其 中Ri=表示第i個系的教室集合，表示第i個系的第|Ri|個教室 ，且對應的教室容量為） ；課程集合表示為C={C1,C2,…,Cq（}q門課程，且與C對應的q門課程的周學時數依次為l1,l2,…,lq）；時間段集合表示為π={1,2,…,23（}23個時間段）；自然班級集合表示為（其中表示第i個系的第j個自然班級，對應的人數為sij）。

4 建立0-1整數規(guī)劃數學模型

一般情況下，在排課工作開始前，院系兩級教務已經制定好教學計劃，根據教學計劃，已將教師和學生分配給課程，因此可利用捆綁式排課的方法，即將教師集合T、教學班級集合S（假設不存在合班上課的情況）、課程集合C捆綁成一個教學任務計劃單元TSC（假設TSC中的教學任務計劃單元已按課程重要程度劃分為專業(yè)核心課程、專業(yè)基礎課程、專業(yè)選修、公共必修課、公共選修課等，且教學任務單元的總數為|TSC|，針對|TSC|個教學任務計劃單元對應的教學班級集合表示為其中表示第i個系的第j個教學班級，對應的人數為sij），教室集合R為一個單元，時間集合π為一個單元。因此，排課的主要問題變成了如何安排時間段和教室，實現某時間段某教學任務單元最多對應一個符合需求的教室，即遵守上述約束條件。設TSC中有N1個教學任務計劃單元包含公共必修課，有N2個教學任務計劃單元包含公共選修課，|TSC|-N1-N2個教學任|TSC|-N1-N2＜i≤|TSC|時，取yijt=0）。

針對包含公共課的N1+N2個教學任務計劃單元而言，同一個時間段，同一個教室至多安排一個務計劃單元中包含mi′個第i個系的教學任務計劃單元。因此，排課的主要問題變成了如何安排時間段和教室，實現某時間段某教學任務單元最多對應一個符合需求的教室，即遵守上述約束條件。為方便建立數學模型，針對包含公共課的N1+N2個教學任務單元而言，引入三維0-1決策變量xijt，當第i個教學任務計劃單元在第t個時間段在第j個教室上課時xijt=1，否則xijt=0（且規(guī)定當N1+N2＜i≤| |TSC時，取xijt=0）。針對不包含公共課的| |TSC-N1-N2個教學任務計劃單元而言，引入三維0-1決策變量yijt，當第i個教學任務計劃單元在第t個時間段在第j個教室上課時yijt=1，否則yijt=0（且規(guī)定當教學任務單元授課，用數學式子表示為

針對不包含公共課的第i個系的mi′個教學任務計劃單元而言，同一個時間段，同一個教室至多安排一個教學任務單元授課，則用數學式子表示為

則針對m個系而言，同一個時間段，同一個教室至多安排一個教學任務單元授課，則用數學式子表示為

要使（1）、（3）式中的教學任務單元及教室資源不發(fā)生沖突，即教學任務單元授課時間不發(fā)生沖突，則必須滿足

每周內每個教學任務計劃單元對應的課程授課時間要等于該門課的周課時，因此，包含公共課的N1+N2個教學任務單元中，每周內每個教學任務計劃單元對應的課程授課時間等于該門課的周課時的數學式子表示為

不包含公共課的第i個系的mi′個教學任務單元中，每周內每個教學任務單元對應的課程授課時間等于該門課的周課時的數學式子表示為

故針對m個系而言，每周內每個教學任務單元對應的課程授課時間等于該門課的周課時的數學式子表示為

針對包含公共課的N1+N2個教學任務單元而言，第i個教學任務單元在第j個教室授課時需滿足該教學班級人數ci不超出教室j的容量rj可用數學式子表示為

針對不包含公共課的m個系而言，第i個教學任務單元在第j個教室上課時需滿足該教學班級人數ci不超出教室j的容量rj可用數學式子表示為

從學校的角度考慮排課問題，在院系兩級共同排課下，既要考慮開課計劃得以實現，又要考慮把課程安排在學生學習效果較好的節(jié)次中，甚至還要考慮減少教學支出等因素。減少教學支出，意味著要充分合理地利用教學資源。

〔4〕中的方法，用Bj′(j′=1′,2′,3′,4′,5′)表示課程的重要程度，也稱為權重，把課程劃分為專業(yè)核心課程、專業(yè)基礎課程、專業(yè)選修、公共必修課、公共選修課。為了體現出重要程度，假設其權重依次賦值為 4、3、0.6、2、0.4。用wt′(t′=1′,2′,3′,4′,5′)表示一天中的5個時間段的課時質量，其中當t′=1′時w1′=1表示第一個時間段（ 即第1、2節(jié)）的教學質量，故當1≤i≤5時有wi=1；當t′=2′時，有w2′=0.8表示第二個時間段（即第3、4節(jié)）的教學質量，故當6≤i≤10時，有wi=0.8；當t′=3′時，有w3′=0.6表示第三個時間段（ 即第5、6節(jié)）的教學質量，故當11≤i≤14時，有wi=0.6；當t′=4′時，有w4′=0.3表示第四個時間段（ 即第7、8節(jié)）的教學質量，故當15 ≤i≤ 18時，有wi=0.3；當t′=5′時，有w5′=0.1表示第五個時間段（ 即第9、10節(jié)）的教學質量，故當19≤i≤23時，有wi=0.1。對第i個教學任務單元分配教室j時，教室利用率為對應的教學班級人數si除以教室j的容量ej，即

設用Bi表示與第i個教學任務單元相對應的課程的權重。以比較重要的課程最大程度地安排在授課效果較好的節(jié)次中且教室資源利用率盡可能地大為目標函數作為學校對排課滿意度的衡量指標，得出三維的0-1整數規(guī)劃模型如下：

5 結束語

排課問題是NP-完全類問題，很難找到多項式時間算法。通過深入分析院系兩級共同排課的特點，將教師、班級、課程捆綁成一個教學任務單元集合，簡化了排課問題的硬約束條件。在建立模型的過程中，引入兩個三維的0-1變量，并將比較重要的課程盡可能地安排在授課效果較好的節(jié)次中且教室資源利用率盡可能地大為目標函數作為學校對排課滿意度的衡量指標，建立基于學校滿意度的0-1整數規(guī)劃數學模型，可為研究院系兩級共同排課問題的學者提供一定的理論參考。如何設計求解該0-1整數規(guī)劃數學模型的算法是今后將要開展的進一步工作。

［參考文獻］

〔1〕 EVEN S，ITAI A，SHAMIR A.On the complexity of time table and multi-commodity flow problems〔J〕.Symposium on Foundations of Computer Science，2008，5（5）：184-193.

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

〔3〕宗薇，趙光甫.高校智能排課系統(tǒng)算法的研究與實現〔J〕.計算機仿真，2011，28（12）：389-392.

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

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

〔6〕葉碧蝦.遺傳算法在排課系統(tǒng)中的優(yōu)化研究〔J〕.吉林師范大學學報（自然科學版），2014，35（2）：185-187.

〔7〕 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 Intelli?gent Computing：Theory and Applications（FICTA）2014.Springer International Publishing，2015：771-780.

〔8〕王璐，楊亞偉.一種改進的遺傳算法在年度排課問題中的應用〔J〕.計算機與數字工程，2016，44（8）：1619-1624.