高校綜合課表編排的研究

1種類型的課表排課方法20世紀(jì)60年代末，一些外國(guó)開始研究課表的排列。1962年,Gotlieb曾提出了一個(gè)課表問題的數(shù)學(xué)模型,之后人們對(duì)課表問題的算法、解的存在性等問題做了很多深入探討。但是大多數(shù)文獻(xiàn)所用的數(shù)學(xué)模型都是Gotlieb的數(shù)學(xué)模型的簡(jiǎn)化或補(bǔ)充,而至今還沒有一個(gè)可行的算法來解決課表問題。40年來人們對(duì)課表問題的計(jì)算機(jī)解法做了許多嘗試。其中課表編排的整數(shù)規(guī)劃模型將問題歸結(jié)為求一組0-1變量的解,但是其計(jì)算量非常大。解決0-1線性優(yōu)化問題的分支一定界技術(shù)卻只適用也規(guī)模較小的課表編排,Mihoc和Balas將課表公式化為一個(gè)優(yōu)化問題,Krawczk則提出一種線性編程的方法。Junginger將課表問題簡(jiǎn)化為三維運(yùn)輸問題,而Tripathy則把課表問題視作整數(shù)線性編程問題并提出了課表的數(shù)學(xué)模型[1,2,3,4,5,6,7,8,9,10]。此外,有些文獻(xiàn)試圖從圖論的角度來求解排課表的問題,但是圖的染色問題也是NP完全問題,只有在極為簡(jiǎn)單的情況下才可以將課表編排轉(zhuǎn)化為二部圖匹配問題,這樣的數(shù)學(xué)模型與實(shí)際相差太遠(yuǎn),所以對(duì)于大多數(shù)學(xué)校的課表編排問題來說沒有實(shí)用價(jià)值。目前,解決課表的方法有:模擬手工排課法,圖論方法,拉格朗日法,二次分配法等多種方法。由于課表約束復(fù)雜,用數(shù)學(xué)方法進(jìn)行描述時(shí)往往導(dǎo)致問題規(guī)模劇烈增大,這已經(jīng)成為應(yīng)用數(shù)學(xué)編程解決課表問題的巨大障礙。從實(shí)際使用的情況來看,國(guó)內(nèi)外研制開發(fā)的這些軟件系統(tǒng)在實(shí)用性上仍不盡如人意。一方面是作為一個(gè)復(fù)雜的系統(tǒng),排課要面面具到是一件困難的事;另一方面每個(gè)學(xué)校由于其各自的特殊性,自動(dòng)排課軟件很難普遍實(shí)用,特別是在調(diào)度的過程中一個(gè)很小的變動(dòng),要引起全部課程的大調(diào)整,這意味著全校課程大變動(dòng),在實(shí)際的應(yīng)用中這是很難實(shí)現(xiàn)的事情。2在課堂上，數(shù)學(xué)模型2.1課前與教室的沖突對(duì)于排課過程中安排的任一門課程必須和所有已排課程沒有沖突;但是每門課程都和任課教師、上課時(shí)間、上課教室和課頭密切相關(guān),不可避免的會(huì)出現(xiàn)排課沖突,而且這些沖突非常復(fù)雜。比如排課過程中會(huì)出現(xiàn)同一個(gè)教師在同一個(gè)時(shí)間在相同的教師給不同的班級(jí)上課,這顯然是不合理的,出現(xiàn)了沖突,在排課的過程中必須要避免,所以對(duì)于綜合性大學(xué)的統(tǒng)一課表編排工作一直是一個(gè)棘手的問題。2.2課程的教學(xué)構(gòu)成定義1.給定一個(gè)四維空間V(Teacher,Time,Classroom,class),稱之為:課表空間。四維分別代表了:教師:全校所有課程的任課教師;時(shí)間:上課的時(shí)間段,例如:每天分為1-2、3-4、5-6、7-8、9-10,共五個(gè)時(shí)間段,每周就會(huì)有25個(gè)時(shí)間段;教室:全校所有的可用教室,包括不同屬性的教室;課頭:所有的課頭數(shù)量。課頭是指:一個(gè)教學(xué)班級(jí)在一周內(nèi)上的一次具體的課程。定義2.在課表V中存在著四維向量l(Tr,Tm,R,C),且l∈V,那么稱l為:課。2.3課表空間中的沖突區(qū)域由課表編排的指導(dǎo)思想可以看出,沖突條件的判斷成為算法的一個(gè)關(guān)鍵因素,下表窮舉出了li(Tr,Tm,R,C)與lj(Tr,Tm,R,C)在排課過程中的所有關(guān)系情況:產(chǎn)生沖突的狀態(tài)為:即滿足表1中沖突情況為1的那六種狀況的函數(shù),根據(jù)對(duì)式(1)的分析;課li(tr,tm,r,c)在課表空間中由此而產(chǎn)生的沖突區(qū)域有三個(gè)分別是:那么這課所占的總的區(qū)域?yàn)?從表面上看在排課過程中排一個(gè)課只占用課表空間中的一個(gè)具體的點(diǎn),而實(shí)際上是占用了一個(gè)很大的區(qū)域S(Tr,Tm,R,C)。在排下一個(gè)課的時(shí)候要將課表空間中的這個(gè)區(qū)域去掉,不然在這里排課肯定會(huì)產(chǎn)生沖突;顯而易見這四個(gè)區(qū)域都是獨(dú)立不相交的。任意兩無沖突的課li(tri,tmi,ri,ci)與li(trj,tmj,rj,cj)所占的區(qū)域Si,Sj,i≠j,假設(shè):對(duì)于點(diǎn)(tr′,t′m,r′,c′)∈Sj無外乎落在Si的四個(gè)區(qū)域Sa、Sb、Sc、Sd中的一個(gè),但不管落在哪里都說明這兩個(gè)課是沖突的,與前提條件矛盾。也就是說不存在滿足(3)這樣條件的點(diǎn)。即Si∧Sj=φ,那么就有Sj?V-Si(4)2.4課表空間v根據(jù)式(2)和(4)可以設(shè)計(jì)出課表編排算法,設(shè)初始狀態(tài)為在課表空間V,所有課集合為U;算法時(shí)間主要消耗在區(qū)域S(Tr,Tm,R,C)的搜尋上,復(fù)雜度為:(Tr+R)C2+TrRC,其復(fù)雜度對(duì)于算法的實(shí)現(xiàn)而言是完全可以接受的。3模型應(yīng)用3.1課堂教學(xué)與教師之間的關(guān)系對(duì)于給定一個(gè)課表空間V(Tr,Tm,R,C),定義各維的參量V(y,t,x,c)根據(jù)式(3)一個(gè)已排好的課表存在以下教室與教師之間的關(guān)系:也就是已排課表的體積肯定會(huì)小于或等于課表總空間。對(duì)上式簡(jiǎn)化可得:3.2教室與教室的關(guān)系針對(duì)與本校的實(shí)際情況,課頭數(shù)量為2700,每周有25個(gè)上課時(shí)間段,教師的數(shù)量為600,有200間教室,由式(5)可以得到下面圖2教室與教室的關(guān)系曲線,同理可以得到圖3、圖4的關(guān)系曲線圖。根據(jù)上圖在本校目前的教學(xué)任務(wù)條件下,比較理想的資源配置情況是完成現(xiàn)有的2700個(gè)課頭的教學(xué)任務(wù),600名專職教師需要140間教室,在實(shí)際運(yùn)行中是很難達(dá)到的,那么放寬條件在目前的情況下,結(jié)合以往手工排課的經(jīng)驗(yàn),160間教室是可以達(dá)到目標(biāo)的。這樣為學(xué)校的教學(xué)管理提供了決策的理論依據(jù)。4優(yōu)化的標(biāo)準(zhǔn)與模型按上述算法得到的課表V是一個(gè)有效的和可行的課表,但它是不是一個(gè)合理的課表呢?每個(gè)教師和學(xué)生都希望相對(duì)有規(guī)律和合理的課表,打個(gè)比方像英語(yǔ)課安排在每周周一的一、二節(jié)與周四的一、二節(jié),這個(gè)安排大家都會(huì)滿意,但如果把四節(jié)英語(yǔ)課都安排在每周周一的一到四節(jié),或者每周上課的時(shí)間地點(diǎn)都不相同,肯定沒有教師和學(xué)生會(huì)對(duì)這個(gè)課表滿意。再者對(duì)于一個(gè)問題的優(yōu)化必須有優(yōu)化的標(biāo)準(zhǔn),而課表優(yōu)化是以教師和學(xué)生的滿意度作為指標(biāo)的,沒有一個(gè)客觀的標(biāo)準(zhǔn),所以對(duì)于已排課表V的優(yōu)化無法得到一個(gè)最優(yōu)結(jié)果,只能給出比較滿意的課表。一般采取的辦法是將課頭按優(yōu)先級(jí)的順序排序,然后再按這個(gè)順序去排課;優(yōu)先級(jí)的規(guī)定各個(gè)學(xué)校處理的方式不同,可以按照各自的要求予以定義。在排課的過程中還有許多細(xì)節(jié)問題需要考慮到,比如:不同教室(比如語(yǔ)音教室、多媒體教室等)應(yīng)該按教室的屬性分別進(jìn)行排課;合班課與分班課的問題,可以把合班的班級(jí)看成是一個(gè)教學(xué)班,而把分班的班級(jí)看成是多個(gè)班級(jí)而已,這個(gè)問題比較好解決;而有些排課過程中的實(shí)際問題解決起來就比較麻煩,許多綜合性高校有多個(gè)校區(qū),而且這些校區(qū)相距比較遠(yuǎn),那么就不能安排教師或?qū)W生在1-2節(jié)課時(shí)在一個(gè)校區(qū)上課,而3-4節(jié)課卻要趕到另一個(gè)校區(qū)去上課,這顯然是不合理的,在排課的過程中就必須考慮到教室間的物