楊子蘭，李 睿，楊慧娟

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

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

1 問題描述

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

2 時間段編號

為得到較好的數(shù)學(xué)模型，根據(jù)學(xué)校的教學(xué)時間段，對時間段進(jìn)行編號，具體如下：將一周分為5個工作日，每天設(shè)為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種類型，并進(jìn)行編號，見表1。

表1 時間段編號

3 變量說明

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

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

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

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

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

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

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

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

每周內(nèi)每個教學(xué)任務(wù)計(jì)劃單元對應(yīng)的課程授課時間要等于該門課的周課時，因此，包含公共課的N1+N2個教學(xué)任務(wù)單元中，每周內(nèi)每個教學(xué)任務(wù)計(jì)劃單元對應(yīng)的課程授課時間等于該門課的周課時的數(shù)學(xué)式子表示為

不包含公共課的第i個系的mi′個教學(xué)任務(wù)單元中，每周內(nèi)每個教學(xué)任務(wù)單元對應(yīng)的課程授課時間等于該門課的周課時的數(shù)學(xué)式子表示為

故針對m個系而言，每周內(nèi)每個教學(xué)任務(wù)單元對應(yīng)的課程授課時間等于該門課的周課時的數(shù)學(xué)式子表示為

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

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

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

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

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

5 結(jié)束語

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

［參考文獻(xiàn)］

〔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〕林漳希，林堯瑞.人工智能技術(shù)在課表編程中的應(yīng)用〔J〕.清華大學(xué)學(xué)報(bào)（自然版），1984，24（12）：1-8.

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

〔4〕楊彥明，岳翠翠，李其申.軍隊(duì)任職院校排課問題的數(shù)學(xué)建模〔J〕.計(jì)算機(jī)與現(xiàn)代化，2012（11）：14-17.

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

〔6〕葉碧蝦.遺傳算法在排課系統(tǒng)中的優(yōu)化研究〔J〕.吉林師范大學(xué)學(xué)報(bào)（自然科學(xué)版），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ìn)的遺傳算法在年度排課問題中的應(yīng)用〔J〕.計(jì)算機(jī)與數(shù)字工程，2016，44（8）：1619-1624.