1、排課問題分析摘要：本題要求我們對多約束條件的典型組合進行分析，求解，并作最優化處理。基于此種原因，我們先對各個元素間的沖突做預處理，進行約束條件的規劃，再通過matlab軟件將教室、教師、課程和時間間的約束條件統一化，構成R-T-C表（詳見附表），再將各個元素進行優先級的計算，從而根據排課的優化模型，求出最優解。經過對所給的表格，數據的深入分析，我們可以得知，教師明顯缺少，比如課程學時要求有160個課時，然而教師能上的課時僅有116個課時，所以開始排課時，不考慮教師，向教師中安排課程。由于同類課程最好不要放在一起，同時根據老師的需求和教室的開放時間進行分配，經過與我們實際的課表的排課情況的分析

2、，比如隔一天排同一課，課程類別不同的課程不在同一時間上課，我們可以大致的排出一個按教室上課的表，即R-T-C表。通過對R-T-C表的分析，發現有很多課沒老師上和老師沒課上的情況，我們就對其進行相應的，合理的調整。最后發現還是老師要外聘。將外聘14名老師去上相應沒人上的科目，具體情況見附表。最后，我們得到了一張相對優化的，以教室為準的課表（詳見附表），從而解決問題（1）的要求。對于我們課表的安排，發現再沒對晚自習有其他條件約束是不會對所排的課表有所影響。關鍵詞：排課問題 組合規劃 多目標函數 數據量化 優先級 一、 問題重述對于有課程40門，教師共有25名，教室18間的條件下合理的安排課程表，而

3、課程、教師、教室的具體屬性及要求詳見附表（表1，表2，表3）對于課表德編排，題目有如下規則：每周以5天為單位進行編排；每天最多只能編排8節課（上午4節，下午4節），特殊情況下可以編排10節課（晚上2節），每門課程以2節課為單位進行編排，同類課程盡可能不安排在同一時間。 要求所要解決的問題：1. 請你結合實際情況建立數學模型，通過編程計算，給出較為合理的課表編排方案，分析你所給出的方案的合理性。2. 如果不準晚上排課，排課結果是否有所變化，如何變化？3. 對教師聘用，教室配置給出合理化建議。二、問題分析隨著現代教學的改革及各項教育工程的實施，新的教育體制對課表的編排提出了更高的要求。但現實生活中

4、，排課問題屢屢皆是，小學如此，中學如此，大學更是如此，不僅科目多樣，而且教室、老師多變，這使得排課問題往往是很令人費解的。經過分析，排課問題就是的多資源組合問題，問題的求解就是找出各個元素間的對應關系。進而將各個元素間的聯系進一步確定，轉化成一個可以量度其大小的值，從而確定優先級，而我們又將如何確定各元素間的關系，目標函數的確定？根據已有知識可以知道，本題主要分析的是建立一個排課的優化模型。而它是一個在課程類別、教師編號、教師及時間上的一個四維空間模型，在各種約束條件下的組合規劃問題，其實質就是解決各因素間的沖突問題。在模型建立后，我們有根據什么參量得到排課的最優解。三、基本假設模型假設：1、

5、 學校的教師和教室資源及學生班結構在一個學期內不會有的變動2、 所有的教室都在同一個校區，且12節課的教室到34節課的教室的路程不超過10min3、 在一學期內，任課教師身體都非常健康，不存在因病因事缺課的情況4、 各種教學資源（課桌、多媒體、機房電腦）在一學期內都不會發生故障，影響上課5、 在上課期間，老師、學生都不遲到，不影響上課質量6、 當有3個課時時，我們當做2個課時處理，及3節連堂上符號說明：Rn教室編號 n=1,2,3.18Cn課程類別 n=1,2,3.40Tn教師編號 n=1,2,3.25Y外聘外聘教師編號 n=1,2,3.14P（T R C）T老師在R教室上C課X1時間段效率X

6、2教室利用率X3教師滿意度D優化級的量度值W1權衡時間段效率參數W2權衡教室利用率參數W3權衡教師滿意度參數Q安排課程的最優值相關名詞解釋：時間段效率：經上網查詢及對相關資料的查閱，我們得知一天內聽課效率最高的是上午810，下午13，故我們定義上午12的聽課效率為3，其余見附表。教室利用率：為充分利用教室資源，我們定義：教室利用率=，四、問題的分析及模型的建立問題分析（1）從數學角度上講，本題主要分析建立一個排課模型，而它是一個在課程類別、教師編號、教師及時間上的一個四維空間模型，在各種約束條件下的組合規劃問題，其實質就是解決各因素間的沖突問題。在此為了簡化處理，先從課程類別、教室編號入手，建

7、立一個關于C-R的關系表，再采用化零為整的思路建立我們的目標函數優化模型，最后，我們根據各因素對排課模型的優先度，求解出排課模型的最優解。在對問題初始化分析時，我們發現課程類別、教室編號、教師、上課時間存在這么一個對關系：1） 11的對應關系2） 1n的對應關系3） nn的對應關系進而，我們再對它們之間的屬性分析，根據它們間的聯系求出一種相對合理的排課方案，最后，對方案的合理性進行分析。模型的建立經過分析，我們需將所有課程盡量合理的安排在一個星期內。首先我們將一個星期劃分為五天，記作1、2、3、4、5，將一天分為四個部分，記作1、2、3、4，進而，我們將得到一個54的矩陣。其中，j=1、2、3

8、、4、5分別表示星期一、星期二、星期三、星期四、星期五；i=1、2、3、4分別表示12節課、34節課、56節課、78節課。即有：我們記作P（T R C）是一個TRC維的數列矩陣，表示T老師在R教室上C課，我們定義P（T R C）=1時，即老師、教室、課程三者都相互符合是記作1 而P（T R C）=0時，即老師、教室、課程三者中有一項不符合記作0規定：A(TR)表示T老師到R教室上了一次課是，即2個節 B(TR)表示T老師到R教室上總課時約束條件：1） 每一個時間段都不能多于一個老師在一個教室上課，此時應滿足的條件是： nN （N=1、2、325）2） 每位老師在每一天不能同時對同一個班上上兩次

9、課，3） 某位老師在某一間教室上課時，安排的課就該在這間教室排完，此時應滿足的條件是： 當一位老師連續兩天對同一個班上兩次課以上的次數越少、課程安排在聽課效率高的時間段次數越多和老師與老師之間的沖突（滿意度）次數越少，此時定義：Q=同時有滿足以上的約束條件，Q將取到最優值，即此時安排的課表最優化排課的預處理1) 同一教師在同一時間內不能安排兩門課同一教室在同一時間內不能安排兩門課同一時間內安排的課時總數不能大于教室的課時總數所提供的教室屬性安排課程的所需教室屬性一致2) 優化級的計算：考慮到課表的安排是為了按時保量的完成教學任務，而其影響因素有眾多，這里我們主要考慮一下三種：1） 時間段效率2

10、） 教室利用率3） 教師滿意度所以我們對課表的安排原則將依據優先級的大小進行排課。先對以上三個因素進行量化處理可得到：時間段效率：上午12上午34下午12下午343021教室利用率：10.80.60.80.40.60.20.43210教師滿意度：很滿意滿意一般不滿意3210我們定義優先級的函數表達式為： D= W1X1+X2+ W3X3其中W1 W2 W3表示相應參數，可根據實際情況進行調整的通過上式，我們可以很容易得知上課的時間段效率、教室利用率、教師滿意度越大，D值就越大即優先級越大，就優先排課；反之，D值越小，優先級就越小，就相對后排課。通過模型得到的T-R-C表（見附表），再根據優先級

11、的排課，我們可得到一個相對優化的課表:R3教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C12-T9上午3-4C18-T24C18-T24下午1-2C6-T6下午3-4這里就不一一羅列，其余詳見附表。模型的評價與改進優點： 到了一種排課的方法，即將課程表按課時數撤分，再按沒門課程的優先順序依次放入課表中。在考慮其他因素（某課程只能安排在固定的某時間段上課，教師只在固定時間段安排課程）的情況下，本模型便于進一步發展、完善（只需改變最優解的參數加相應限制就可解決）。比起目前最相對合理的遺產法簡單易懂很多。缺點：有很多待改進之處，該算法的優先級只是根據經驗常識來進行優先級安排課程，具有一

12、定的非科學性，如果能根據一定的科學知識，對課程的優先級進行科學的評定，科學的地算出其優先級系數，再確定其優先級，會具有更好的合理性。再解題過程中限制條件多，數據量大，過程相對較繁瑣。模型推廣本模型有編程優化的模塊，但排課表是人為因素較多，也是為了滿足課程的安排過程中更人性化。因此本模型適用于中小規模的排課，其主要限制因素是程序完善度不高，如要進行推廣，則必須增加程序的模塊，使其更完善，相信改進完善后，即可更科學的實現大規模大排參考文獻：1 數學建模（上冊），成都電子機械高等專科學校，二零一零年三月2 數學建模資料最優化模型.pdf 2010.73 回溯法 2010.74 貪婪法 2010.75

13、 一天的最有聽課效率時間段 2010.7附表：表1：教師屬性：教師編號能勝任課程類別周最大課時數對教室類別要求上課時間要求盡可能不同天上課的教師T011，84多媒體教室或機房上午T4T0214普通教室下午T0316普通教室上午T0424多媒體教室上午T1T0524普通教室下午T0626普通教室無T0734普通教室上午T083，83普通教室或機房下午T0934普通教室上午T11,T18T1036多媒體教室上午T1148普通教室下午T9,T1244普通教室無T1346多媒體教室下午T1452普通教室上午T155，83普通教室或機房下午T23T1654普通教室上午T1764普通教室下午T1866普通

14、教室無T9T1964多媒體教室下午T2074普通教室上午T2176普通教室下午T2276多媒體教室上午T233，84普通教室或機房無T15T244，86普通教室或機房上午T256，84普通教室或機房下午表2：課程屬性及要求：課程編號課程類別周課時數對教室座位最大要求數對教室類別要求時間要求C011450多媒體教室上午C021430普通教室下午C031640普通教室下午C041425多媒體教室上午C051360普通教室下午C0624100普通教室下午C072450多媒體教室上午C082230普通教室上午C092440普通教室下午C102325多媒體教室上午C113660普通教室上午C123480

15、普通教室上午C133650多媒體教室下午C143230普通教室下午C153340普通教室下午C164425多媒體教室上午C174460普通教室下午C184690普通教室上午C194450多媒體教室上午C204250普通教室上午C215430普通教室上午C225440多媒體教室下午C235325普通教室上午C245660普通教室下午C2554100多媒體教室上午C266350多媒體教室下午C276430普通教室下午C286440普通教室下午C296450多媒體教室上午C306430普通教室下午C317640普通教室上午C327425多媒體教室下午C337360普通教室無C347480多媒體教室上

16、午C357450普通教室下午C368630機房無C378440機房上午C388225機房上午C398460機房下午C408450機房無表3：教室屬性：教室編號最大座位數教室類別R01100多媒體教室R02100普通教室R03100普通教室R0450多媒體教室R0550普通教室R0650普通教室R0750普通教室R0860普通教室R0960普通教室R1060多媒體教室R1160普通教室R1260機房R1340機房R1440機房R1540機房R1640多媒體教室R1750普通教室R1840普通教室表4：T-R-C表課程老師教室容量C1T1R(10)50/60C2T2R(18)30/40C3T3R(

17、18)40/40C4C5C6T6R(2)R(3)100/100C7T4R(4)50/50C8T6R(18)30/40C9T5R(18)40/40C10C11C12T7R(2)R(3)80/100C13T10R(4)R(16)50/50C14T8R(18)40/40C15T9R(18)40/40C16T13R(16)30/40C17T11R(8)R(9)R(11)60/60C18T24R(2)R(3)90/100C19T11R(5)R(6)R(7)R(17)50/50C20T12R(5)R(6)R(7)R(17)50/50C21T16R(18)30/40C22C23C24C25C26T19R(4

18、)50/50C27T18R(18)40/40C28T17R(18)40/40C29C30C31C32C33T20R(8)R(9)R(11)60/60C34T22R(1)80/100C35T21R(5)R(6)R(7)R(17)50/50C36C37C38T15R(13)R(14)R(15)25/40C39T25R(12)60/60C40T23R(12)60/60表5：各教室課程安排：R1教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C34-T22C34-T22C25上午3-4C25下午1-2下午3-4R2教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C18-T24上午3

19、-4C12-T9下午1-2C6-T6下午3-4R3教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C12-T9上午3-4C18-T24C18-T24下午1-2C6-T6下午3-4R4教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C13-T10C19-T11C13-T10上午3-4C19-T11下午1-2C26-T19下午3-4R5教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C21-T16C35-T21上午3-4C35-T21C21-T16下午1-2C30C17-T12C30下午3-4R6教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C31-T21

20、上午3-4下午1-2C28-T17C9-T5C9-T5下午3-4C28-T17R7教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C8-T6上午3-4下午1-2C20-T12C27-T17下午3-4C27-T17C3-T3R8教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C31上午3-4C31下午1-2C5C33-T20下午3-4R9教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C11C11C11上午3-4下午1-2C24下午3-4C24C24R10教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C1-T1C29C29C7-T4上午3-4C7-T4C

21、1-T1下午1-2下午3-4R11教室一周內課程安排星期一星期二星期三星期四星期五上午1-2上午3-4下午1-2C17-T11下午3-4C17-T11R12教室一周內課程安排星期一星期二星期三星期四星期五上午1-2上午3-4下午1-2C40-T23C39-T25下午3-4C39-T25C40-T23R13教室一周內課程安排星期一星期二星期三星期四星期五上午1-2上午3-4下午1-2C28-T18下午3-4C36C28-T18R14教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C37上午3-4C37下午1-2C36C36下午3-4R15教室一周內課程安排星期一星期二星期三星期四星期五

22、上午1-2C38-T24上午3-4下午1-2下午3-4R16教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C10C16-T13C4上午3-4C4C16-T13下午1-2C22下午3-4C32C22C32R17教室一周內課程安排星期一星期二星期三星期四星期五上午1-2上午3-4下午1-2C15-T9C14-T08C2-T2下午3-4R18教室一周內課程安排星期一星期二星期三星期四星期五上午1-2C23上午3-4C8-T6下午1-2C3-T3下午3-4C2-T2C3-T3C14-T8表6：外聘教師課程安排表：外聘教師課程課時教室時間YT1C254R1二34，五12YT2C304R5二5

23、6，五56YT3C314R8一12，三34YT4C53R8二123YT5C116R9一12，三12，五12YT6C244R9一56，三78，五78YT7C294R10二12，四12YT8C366R14一56，三78，五56YT9C103R16一123YT10C44R16二34，五12YT11C224R16一56，四78YT12C324R16二78，五78YT13C233R18三123YT14C374R14二12，四34程序附錄：clear;C=1 2 2 1 11 2 1 2 -11 3 1 2 -11 2 1 1 11 2 3 2 -12 2 4 2 -12 2 2 1 12 1 1 2 1

24、2 2 1 2 -12 2 1 1 13 3 3 2 13 2 4 2 13 3 2 1 -13 1 1 2 -13 2 1 2 -14 2 1 1 14 2 3 2 -14 3 4 2 14 2 2 1 14 1 2 2 15 2 1 2 15 2 1 1 -15 2 1 2 15 3 3 2 -15 2 4 1 16 2 2 1 -16 2 1 2 -16 2 1 2 -16 2 2 1 16 2 1 2 -17 3 1 2 17 2 1 1 -17 2 3 2 07 2 4 1 17 2 2 2 -18 3 1 3 08 2 1 3 18 1 1 3 18 2 3 3 -18 2 2 3

25、 0;T=1 8 4 4 1 4 01 0 4 2 -1 0 01 0 6 2 1 0 02 0 4 1 1 1 02 0 4 2 -1 0 02 0 6 2 0 0 03 0 4 2 1 0 03 8 3 5 -1 0 03 0 4 2 1 11 183 0 6 1 1 0 04 0 8 2 -1 9 04 0 4 2 0 0 04 0 6 1 -1 0 05 0 2 2 1 0 05 8 3 5 -1 23 05 0 4 2 1 0 06 0 4 2 -1 0 06 0 6 2 0 9 06 0 4 1 -1 0 07 0 4 2 1 0 07 0 6 2 -1 0 07 0 6 1 1

26、0 03 8 4 5 0 15 04 8 6 5 1 0 06 8 4 5 -1 0 0;R=4 14 24 22 12 22 22 23 23 23 13 23 31 31 31 31 12 21 2；%Rt為教室與老師的關系Rt=zeros(25,18);for i=1:18 for m=1:25 for n=1:40 if R(i,1)=C(n,3) i1=C(n,1); if T(m,1)=i1|T(m,2)=i1 i4=T(m,4); switch (i4) case 1 if R(i,2)=1 Rt(m,i)=1; end case 2 if R(i,2)=2 Rt(m,i)=1;

27、 end case 3 if R(i,2)=3 Rt(m,i)=1; end case 4 if R(i,2)=1|R(i,2)=3 Rt(m,i)=1; end case 5 if R(i,2)=2|R(i,2)=3 Rt(m,i)=1; end end end end end endendRt;%Rc為教室與課程的關系Rc=zeros(18,40);for i=1:18 for n=1:40 if R(i,1)=C(n,3)&R(i,2)=C(n,4) Rc(i,n)=1; end endendRc;%Tcfor m=1:25 for n=1:40 if T(m,1)=C(n,1)|T(m

28、,2)=C(n,1) if T(m,3)=2*C(n,2) q=T(m,4); t=T(m,5); switch q case 1 if C(n,4)=1 switch t case 1 if C(n,5)=1 Tc(m,n)=1; end case -1 if C(n,5)=-1 Tc(m,n)=1; end case 0 if C(n,5)=1|C(n,5)=-1|C(n,5)=0 Tc(m,n)=1; end end end case 2 if C(n,4)=2 switch t case 1 if C(n,5)=1 Tc(m,n)=1; end case -1 if C(n,5)=-1

29、 Tc(m,n)=1; end case 0 if C(n,5)=1|C(n,5)=-1|C(n,5)=0 Tc(m,n)=1; end end end case 3 if C(n,4)=3 switch t case 1 if C(n,5)=1 Tc(m,n)=1; end case -1 if C(n,5)=-1 Tc(m,n)=1; end case 0 if C(n,5)=1|C(n,5)=-1|C(n,5)=0 Tc(m,n)=1; end end end case 4 if C(n,4)=1|C(n,4)=3 switch t case 1 if C(n,5)=1 Tc(m,n)=

30、1; end case -1 if C(n,5)=-1 Tc(m,n)=1; end case 0 if C(n,5)=1|C(n,5)=-1|C(n,5)=0 Tc(m,n)=1; end end end case 5 if C(n,4)=2|C(n,4)=3 switch t case 1 if C(n,5)=1 Tc(m,n)=1; end case -1 if C(n,5)=-1 Tc(m,n)=1; end case 0 if C(n,5)=1|C(n,5)=-1|C(n,5)=0 Tc(m,n)=1; end end end end end end endendTc;%在完全滿足的

31、情況下 課程選擇最優化的老師%Ct說明行代表課程，列代表能上該課的老師編號%if有相同編號的老師 那針對該門課程進行求最優值，將值最大的老師放入相應課程中Ct=1 0 0;2 0 0;0 0 0;1 0 0;2 0 0;5 6 0;4 0 0;6 0 0;5 6 0;4 0 0;0 0 0;7 9 23;0 0 0;8 23 0;23 0 0;0 0 0;11 12 0;24 0 0;0 0 0;12 24 0;16 0 0;0 0 0;16 0 0;0 0 0;0 0 0;19 0 0;17 18 25;17 18 25;0 0 0;17 18 25;0 0 0;0 0 0;0 0 0;22 0 0;21 0 0;0 0 0;1 23 24;1 23 24;23 25 0;23 0 0;%具體實現Ct1=zeros(40,1);%用于存放最終值%先判斷只有一個老師上課的課程for n=1:40 for nn=n+1:40 if length(Ct(Ct(n,:)=0)=1 if nn=n for u=1:3 if Ct(n,1)=Ct(nn,u) %判斷老師編號相同 u1=Ct(n,1);%獲取老師編號 a1=n;%獲取課程號 a2=nn;%獲取課程號 b1=T(u1,3)-2*