學(xué)生建模報(bào)告：排課問(wèn)題

1、排課問(wèn)題組員：王小猛 20031090069鄧威 20031090081夏小亮 20031090067排課問(wèn)題模型摘要本文建立了一個(gè)對(duì)課程編排的綜合優(yōu)化模型。 它可以解決在眾多限制條件下的學(xué)校 排課問(wèn)題。該模型是一個(gè)在滿足眾多限制條件下對(duì)教室座位的利用率以及時(shí)間資源利用 率綜合考慮的多目標(biāo)優(yōu)化模型。通過(guò)對(duì)各個(gè)目標(biāo)進(jìn)行加權(quán)處理，將多目標(biāo)轉(zhuǎn)化成單目標(biāo) 進(jìn)行處理，根據(jù)不同實(shí)際情況，賦予不同的權(quán)值而得到不同結(jié)果。該模型的主要優(yōu)點(diǎn)在于： 通過(guò)考慮教室的利用率使得一個(gè)班級(jí)的所有課程和課次 盡量被安排在同一個(gè)教室（即那個(gè)容量與該班級(jí)人數(shù)最為接近的教室，因?yàn)榇藭r(shí)它的教 室利用率最高），這樣就使得同一個(gè)班級(jí)的同

2、一門課程的不同課次盡量被安排在同一個(gè) 教室，這就滿足了題目中的“同一門課的多次授課盡可能在同一教室”的要求；同時(shí)也 使得同一個(gè)班級(jí)的不同課程盡量被安排在同一個(gè)教室，這樣就滿足了題目中“將課間的 學(xué)生流動(dòng)降到最低限度”的要求；通過(guò)在模型的限制條件中加入同一班級(jí)的相臨兩次 授課時(shí)間間隔的限制，使得通過(guò)該模型制定出來(lái)的排課方案滿足題目中的“相鄰兩次授 課的間隔盡可能均勻”的要求。本文中的模型不僅使其規(guī)定的目標(biāo) （教室的座位利用率和時(shí)間的利用率） 達(dá)到最大， 還可以根據(jù)目標(biāo)的不同側(cè)重點(diǎn)進(jìn)行權(quán)值修正以適合不同情況下的排課模型。 而且本文中 所用到的方法還可推廣到其他領(lǐng)域的應(yīng)用中。關(guān)鍵詞:單雙周上課”：?jiǎn)?/p>

3、周和雙周上課的課時(shí)不同 ,其平均課時(shí)為題目中所要求的課時(shí)。 班級(jí)課程”：代表所給數(shù)據(jù)文件中的一個(gè)向量，包含學(xué)生班代碼，人數(shù)，計(jì)劃要 開(kāi)課程，周用時(shí)，多媒體需求，任課教師等信息。一 問(wèn)題重述學(xué)校的教師和教室資源及學(xué)生班結(jié)構(gòu)在一個(gè)學(xué)期內(nèi)不會(huì)有大的變動(dòng)。 既定的教學(xué)計(jì) 劃必須執(zhí)行。所編排的課程表起碼應(yīng)無(wú)任何沖突，最好能夠?qū)μ岣呓虒W(xué)質(zhì)量發(fā)揮重要作 用，即選擇“最優(yōu)”的排課方案。如：充分滿足各課程對(duì)教學(xué)條件的要求；相鄰兩次授 課的間隔盡可能均勻；占用的教室個(gè)數(shù)盡可能少，以空出更多的教室供學(xué)生自習(xí)或發(fā)揮 其它利于教學(xué)的作用；同一門課的多次授課盡可能在同一教室；將課間的學(xué)生流動(dòng)降到 最低限度等等。教學(xué)計(jì)劃中

4、的課程在周課時(shí)數(shù)、授課班的規(guī)模及所需教學(xué)設(shè)施等方面有各自的要 求；各教室的座位數(shù)、教學(xué)設(shè)施規(guī)格有一定差異；有些課程允許幾個(gè)班的學(xué)生合為一個(gè) 大班聽(tīng)課，有些課程則要求將一個(gè)大班分成幾個(gè)小班；有些教師在一個(gè)學(xué)期內(nèi)一人擔(dān)任 著多門課程的教學(xué)工作，如此等等。二 模型假設(shè)1）假設(shè)多媒體教室里的多媒體沒(méi)有損壞。2）假設(shè)教室在一個(gè)學(xué)期當(dāng)中沒(méi)有其他的安排。3）假設(shè)教室的座位沒(méi)有損壞。4）假設(shè)班級(jí)的人數(shù)不再改變。5）假設(shè)教師對(duì)上課時(shí)間段沒(méi)有偏好。6）假設(shè)教室資源足夠。三 符號(hào)說(shuō)明1）： Cijk表示 i 班在星期 j 第 k 時(shí)段是否可排課標(biāo)志，可排課時(shí) Cijk =0，不可排課時(shí) Cijk =1；（2）：dm

5、jk 表示m教師在星期j第k時(shí)段是否可排課標(biāo)志，可排課時(shí)dmjk=0,不能排課時(shí) dmjk =1；3）：enjk表示n教室在星期j第k時(shí)段是否可排課標(biāo)志，可排課時(shí) &jk =0, 不能排課時(shí) enjk =1；4）：bk表示在第 k 時(shí)間段上課時(shí)的效果值效率；5）；Ni表示 i 班的人數(shù)；6）：rj表示 j 教室座位數(shù)；7） :vj表示 j 教室有沒(méi)有多媒體的標(biāo)志，如果有vj =1；若沒(méi)有 vj =0；8）：Xih表示 i 班 h 課程是否需要多媒體的標(biāo)志，需要 X ih ，不需要是X ih=0；(9):右表示i班j課程不同課次之間的間隔(天數(shù))四 問(wèn)題分析通過(guò)對(duì)各種數(shù)據(jù)的分析，我們發(fā)現(xiàn)最主要的

6、矛盾是：一是需要多媒體的課程與有多 媒體教室之間的矛盾；二是班級(jí)的學(xué)生數(shù)量與教室的座位數(shù)之間的矛盾。因此對(duì)需要多 媒體的課程安排在座位數(shù)大于學(xué)生班人數(shù)的多媒體教室。 座位數(shù)和多媒體兩個(gè)條件是必 須同時(shí)滿足的。在此模型中我們主要考慮教室資源和時(shí)間資源的利用率， 使這兩類資源的利用率達(dá) 到最大。教室資源的利用率主要是指座位的利用率即上課的人數(shù)與該教室的座位的比值， 比 值越大則利用率越高。時(shí)間資源利用率是指每個(gè)時(shí)段學(xué)生上課的效率和教師上課的效 率，關(guān)于這一點(diǎn)通過(guò)對(duì)學(xué)生和教師的調(diào)查和學(xué)校的實(shí)際情況我們發(fā)現(xiàn)上午的學(xué)生學(xué)習(xí)效 率以及教師授課的效率都比較高，而下午上課的效率則比較低。由于在晚上學(xué)生要求自

7、習(xí)以及教師可能有備課的需要，因此在晚上我們不排課。所以在排課時(shí)我們盡量將課程 排在上午。對(duì)于此問(wèn)題的解決我們可以對(duì)每一個(gè)上課時(shí)間段賦予權(quán)值。安排在每個(gè)時(shí)間 段的課時(shí)與對(duì)應(yīng)的權(quán)值的乘積達(dá)到最大，即表示時(shí)間利用率達(dá)到最大。因此該模型是一個(gè)雙目標(biāo)模型，通過(guò)實(shí)際情況的側(cè)重點(diǎn)我們對(duì)這兩類目標(biāo)賦予權(quán)值可將其轉(zhuǎn)化為單目標(biāo) 模型。這樣可以降低解模的困難。對(duì)于時(shí)間段的劃分我們可將其 6個(gè)時(shí)間段上午：12節(jié)，34節(jié)。下午：56節(jié)， 78節(jié)。晚上910節(jié)。對(duì)于不排課的時(shí)間段，如：晚上910節(jié)，下午78節(jié)，我們將其權(quán)值定為0。上面的時(shí)間段我們安排的都是兩課時(shí)為一時(shí)間段。而我們所用的方法是安排一個(gè)星期內(nèi)的課程，因此對(duì)于

8、題目中出現(xiàn)的 3課時(shí)和5課時(shí)課程，我們首先將其處理為4課時(shí) 和6課時(shí)，這樣可以很好地將這些課程安排在我們所規(guī)定的時(shí)間段內(nèi)。再用模型中的方 法將這些課程排定。另外為了將課程盡量安排均勻，我們將同一個(gè)班的同一門課程之間 的間隔加以限制，使其間隔不小于兩天。五模型建立根據(jù)上面的問(wèn)題分析我們建立以下的優(yōu)化模型，模型中的a、a2是根據(jù)實(shí)際情況的時(shí)間利用率與資源利用率的權(quán)值。max(aibk + a2 Ni rn)總資源利用率達(dá)到最大Cijk =0 d mjk = 0enjk 0i班在星期j第k時(shí)段可排課 m教師在星期j第k時(shí)段可排課 n教室在星期j第k時(shí)段可排課S t :=N i=rnXih=2i班的人

9、數(shù)不大于n教室的座位數(shù)需要多媒體的課程上課時(shí)必須有多媒體同一個(gè)班的同一門課程之間的可隔大于兩天六模型求解在預(yù)處理模型中，我們是將班級(jí)一課程逐一地安排在適當(dāng)?shù)奈恢谩Ｋ詫?duì)課程安排的順序不同得到的結(jié)果也就不同，所以為了得到理想的結(jié)果，我們首先需要對(duì)班級(jí)一課程進(jìn)行排序，排序的理想結(jié)果是先安排的班級(jí)一課程對(duì)后面的班級(jí)一課程沒(méi)有影響。 我們采用以下排序規(guī)則：（一）:將所有的班級(jí)一課程按照是否有多媒體進(jìn)行分類，需要多媒體的分為第 一類，不需要多媒體的分為第二類；（二）:將上述兩類按照班級(jí)人數(shù)從大到小進(jìn)行排序； 按照上述順序逐一對(duì)排課。最后我們還必須對(duì)所排列的班級(jí)一課程進(jìn)行重新的排列。 標(biāo)準(zhǔn)如下：（一）:對(duì)

10、于3課時(shí)的課程，若這些課程全部都排在上午，我們則安排單雙周上課, 即單周上2課時(shí)，雙周上4課時(shí)；或單周上4課時(shí)，雙周上2課時(shí)。（二）: 3課時(shí)的課程若有排在下午的，我們則安排下午 3節(jié)連上。（三）：對(duì)于5課時(shí)的課程，則可認(rèn)為是3+2模式。（四）：這樣單課時(shí)都可以得到處理。舉例：班級(jí)-課程:院系課程人數(shù)多媒體教師課時(shí)課程代號(hào)數(shù)學(xué)系數(shù)學(xué)分析120不需要王教授51物理系普通物理80不需要李教授42生科系生物60需要王教授43計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)90需要程教授34則排課的優(yōu)先級(jí)為：4, 3, 1, 2;假如現(xiàn)在只有7501 7502 7503 7504 教室能排課教室座位數(shù)是否有多媒體7501125無(wú)750

11、280有750390無(wú)750470有4, 3課程只能在7502和7504教室選擇，先排4課程（先一周內(nèi)排2次，后再優(yōu) 化處理），用模型求解；得出他在排的位置和時(shí)間；當(dāng) 4課程排定后，則3課程（一周 類排2次）就不能與4課程排在同一教室和同一時(shí)間上。以此類推。若兩個(gè)課程的教師 相同如（1, 3課程），貝他們就不能排在同一時(shí)間上。七模型的進(jìn)一步討論由于我們用的是對(duì)班級(jí)一個(gè)個(gè)地逐步排入教室的方法。這樣有可能會(huì)使有些資源的 利用率不會(huì)達(dá)到最大，如多媒體教室的有效使用率、教室的使用率。有可能使多媒體教 室在有些時(shí)間段會(huì)空閑，而沒(méi)有減少對(duì)多媒體的使用。同時(shí)也會(huì)使每一個(gè)教室會(huì)排上課 程，而不會(huì)出現(xiàn)全星期或全

12、天都空余的教室供其它的目的所使用，如此等等。因此，我們可對(duì)這所有的因素都排列出來(lái)，按照它們實(shí)際的側(cè)重點(diǎn)逐個(gè)進(jìn)行加權(quán)， 以他們組成的函數(shù)作為目標(biāo)，可求出他們最優(yōu)的配置。出現(xiàn)這些問(wèn)題的原因主要是我們對(duì)這些問(wèn)題側(cè)重點(diǎn)的看法不同，我們?cè)诳紤]這些問(wèn)題時(shí)主要是建立在授課效率這一方面。本模型沒(méi)有考慮教師對(duì)上課時(shí)段的要求， 實(shí)際中教師可能由于各種原因在某個(gè)特定 的時(shí)段不能安排上課。對(duì)于這個(gè)問(wèn)題我們可對(duì)模型中教師進(jìn)行限制或者加權(quán)，可達(dá)到目 的。八模型評(píng)價(jià)本模型是一個(gè)綜合優(yōu)化模型。它可以解決在眾多限制因素以及有限資源等條件限制 下的學(xué)校排課問(wèn)題。該模型采用對(duì)班級(jí)一一課程逐個(gè)地逐步排入教室的方法。易利用類C語(yǔ)言的軟

13、件編寫程序求解，解決了大規(guī)模的非線性優(yōu)化模型難以求解的問(wèn)題，實(shí)現(xiàn)了對(duì)問(wèn)題的求解。特別是在多媒體的資源、座位數(shù)限制、教師資源、教室資源等方面，我們都有很好 的分配方案。對(duì)于其他的限制條件，我們也能使其達(dá)到最大限度的滿足。該模型是在滿 足上述眾多限制下的對(duì)教室座位的利用率以及時(shí)間資源利用率的一個(gè)多目標(biāo)優(yōu)化模型， 還可以根據(jù)不同實(shí)際情況，如這兩類目標(biāo)的側(cè)重點(diǎn)的不同等，而對(duì)它們進(jìn)行加權(quán)，最后 得出最優(yōu)的排課方案。在求解此模型時(shí)，我們首先抓住主要矛盾：教室是否有多媒體與課程是否需要多媒 體之間的矛盾，班級(jí)的人數(shù)與教室座位數(shù)之間的矛盾。然后再考慮其他的眾多限制。首先有多媒體的教室比較少，限制條件最多，所以

14、將這些課程優(yōu)先考慮，把這些課 程作為第一批進(jìn)行排課，將不需要多媒體的課程作為第二批排課。其次，我們將班級(jí)的 人數(shù)按照又大到小進(jìn)行排序，再按照此順序逐步安排課程，這樣就很好地解決了這兩個(gè) 主要矛盾。在安排課程時(shí)我們是按照每一個(gè)課程的資源利用率達(dá)到最大， 以此為標(biāo)準(zhǔn)來(lái)安排每 一課程，在排課時(shí)就是要使座位的利用率以及時(shí)間的利用率達(dá)到最大，時(shí)間的利用率與 排課的順序無(wú)關(guān)，而只是教室的座位利用率與班級(jí)排課的順序有關(guān)。而我們是按照上課 人數(shù)由大到小的順序進(jìn)行排課的。 故每一次都是使上課的人數(shù)與教室的座位數(shù)的差達(dá)到 最小，因此人數(shù)大的班級(jí)不會(huì)對(duì)人數(shù)小的班級(jí)產(chǎn)生影響； 因此每一次排課都會(huì)達(dá)到最優(yōu)， 任何兩門課

15、程之間不會(huì)產(chǎn)生任何的影響。所以總體達(dá)到最優(yōu)。在計(jì)算機(jī)給班級(jí)安排課程它總是找教室座位數(shù)與班級(jí)人數(shù)最接近的哪一個(gè)教室， 而 教室的順序是一定的，在其他條件滿足的情況下，計(jì)算機(jī)都會(huì)先尋找同一個(gè)教室，當(dāng)條 件不滿足時(shí)計(jì)算機(jī)再尋找其他的教室， 這樣就滿足了同一班級(jí)的同一門課程盡量安排在 同一教室的條件，而且同一班級(jí)的不同課程也盡量會(huì)安排在同一教室，這樣也會(huì)使課間 的流動(dòng)性達(dá)到最小。本模型不僅可以使規(guī)定的目標(biāo)（教室的座位利用率和時(shí)間的利用率）達(dá)到最大。還 可滿足題目中眾多的限制因素。而且還可推廣大其他領(lǐng)域的應(yīng)用。附錄（ 1）：程序#includeiostream#includetime.h#include

16、string#includetime.h#includefstream#include cstdlib#include vectorusing namespace std;typedef struct yizimastring banji;string kecheng;int xingqi;int shiduan ;int jiaoshi ;string teacher;struct yizima *next;code,*linklist;float fuction(int classroomcon272,int i,int j,int k,int m,int n,int stnumber )

17、 float sum1;if(k=0) sum1=0.8;if(k=1) sum1=0.5;if(k=2) sum1=0.3; float sum2;sum2=(float)stnumber/classroomconi1;float sum=sum1+sum2;return sum;int classtime(string classname,int j,int k,linklist H) linklist p; p=H-next;int flag=0; while(p!=NULL) if(p-banji=classname&p-xingqi=j&p-shiduan=k) flag=1;p=p

18、-next; return flag;int teachertime(string jiaoshi ,int j,int k,linklist H) linklist p;p=H-next;int flag=0; while(p!=NULL) if(p-teacher=jiaoshi&p-xingqi=j&p-shiduan=k) flag=1;p=p-next; return flag;int jiange (string classname,string subject,int j,linklist H) linklist p;p=H-next;int m;int flag=0;while

19、(p!=NULL)if(p-banji=classname&p-kecheng=subject) m=p-xingqi-j; if(m!=-1&m!=1&m=0) flag=1;p=p-next;return flag;void main()ifstream infile;float fuction(int classroomcon272,int i,int j,int k,int m,int n,int stnumber ); linklist H,r,p;int m=0;float sumall=0;int a,b,c;int flag;float sum,sum1;H=new code;

20、H-next=NULL;p=H;string classname;int stnumber;string subject;int subjectnumber;string duomiti;string jiaoshi;問(wèn)題 2 的數(shù)據(jù) .txt);int xingqi;int shiduan;int classroom;int classroomuse2753=0;int classroomcon272=0,80,0,80,0,50,0,25,0,25,0,80,0,120,0,50,1,260, 0,120,0,25,0,50,0,50,0,120,0,50,1,272,0,25,0,80,0,80,1,120,1,120, 0,50,1,120,0,50,1,270,0,80,0,80;for(int e=0;eclassname; infilestnumber; infilesubject; infilesubjectnumber;infileduomiti;infilejiaoshi;if(du