排課算法研究

1、分支定界算法在中學(xué)排課問(wèn)題中的應(yīng)用摘要：在本文中我們主要研究了帶約束有教案的中學(xué)排課程表問(wèn)題。首先我們得到了有關(guān)該問(wèn)題的中學(xué)課程表必須滿足的幾個(gè)條件，因?yàn)樵撆耪n程表問(wèn)題是一個(gè)NP難解的問(wèn)題，因此該問(wèn)題沒(méi)有多項(xiàng)式時(shí)間算法，通過(guò)分析，我們提出了一個(gè)求解該問(wèn)題的分支定界算法，數(shù)值證明這是一個(gè)有效的算法。關(guān)鍵詞：課程表問(wèn)題；NP難解問(wèn)題；分支定界算法Abstract : In this paper we focus on the time-table problem for middle schools with constraints on tearchers teaching-plans. We

2、first give some necessary conditions for fcasible fime-tables of the problem, because this problem is NP-head, which means that there does not exist an algorithm that solves this problem in polynomial-time. We propose a branch-and-bound algorithm. Our experiment result shows that the proposed algori

3、thm is both efficient and effective for this problem.Key words: Time-table, NP-problem, branch-and-bound method.一個(gè)學(xué)校的教與學(xué)的安排是由學(xué)校的規(guī)模及一定的要求來(lái)決定，一個(gè)學(xué)校有自己的教學(xué)方向這在一定程度上決定了這個(gè)學(xué)校的教師分配及所教科目在一個(gè)學(xué)期內(nèi)的課時(shí)數(shù)分配。為了適當(dāng)安排好學(xué)校的教學(xué)進(jìn)度，就必須要安排好教師的講課、學(xué)生的授課和教室、體育場(chǎng)地等等的合理使用，以免出現(xiàn)沖突和不合理的安排。所以，合理的課表安排是學(xué)校工作的重要組成部分。事實(shí)證明，課表的安排問(wèn)題是一個(gè)NP完全問(wèn)題，只能根

4、據(jù)各個(gè)學(xué)校的特點(diǎn)來(lái)安排適當(dāng)?shù)恼n程表，我們發(fā)現(xiàn)，對(duì)于高中學(xué)校來(lái)說(shuō)，很多時(shí)候，授課教師往往要考慮到對(duì)幾個(gè)班他要同時(shí)上課，這就要求每個(gè)班的進(jìn)度必須一致，所以在老師備課寫(xiě)教案的時(shí)候就要考慮到這個(gè)問(wèn)題，本文也正是從老師的教案入手，采用分支定界算法來(lái)解決課表的安排問(wèn)題。我們來(lái)分析一下排課程表問(wèn)題。我們可以把課程表問(wèn)題看成在滿足下列一系列條件的可行域中，尋找一個(gè)可行點(diǎn)的問(wèn)題。而排課條件基本上可以很自然地歸結(jié)為以下幾條：1、 教師的教案問(wèn)題（指一天教案）2、 每門(mén)課在一周內(nèi)的均衡分配3、 每門(mén)課在一周內(nèi)的上下午的均衡分配4、 每個(gè)教師的同一門(mén)課所有班的同等對(duì)待5、 集中排課6、 其他排課條件（條件1）在分析之

5、后，我們發(fā)現(xiàn)，其實(shí)對(duì)于排課問(wèn)題最簡(jiǎn)單的方法是采用原始枚舉法進(jìn)行求解。這實(shí)際上是對(duì)一棵龐大的樹(shù)進(jìn)行搜索（這棵樹(shù)的根就是排課的起點(diǎn)），因此這樣做非常費(fèi)時(shí)。下面我們給出基于分支定界思想的算法。實(shí)際在枚舉的過(guò)程中，將產(chǎn)生大量的分支是無(wú)可行點(diǎn)的分支。比如在排了一些課后，教師的教案問(wèn)題不滿足，主課不滿足要求，副科排不了了等等。當(dāng)不滿足要求時(shí)，以下的所有分支都無(wú)可行點(diǎn)，所以可以大膽地把它們?nèi)サ簟Ｒ蚨捎梅种Фń绶▉?lái)剪支。怎樣定界？采用一種判別原則，也即在排課程表時(shí)，定義一種抽象的界，使得在排到某個(gè)課時(shí)，它是否超過(guò)了這個(gè)界，如果超過(guò)了這個(gè)界，就把它剪掉。同樣，可以注意到，當(dāng)先排某些課時(shí)將使得可行點(diǎn)很難找到，因

6、為有各種排課條件。所以將適當(dāng)調(diào)整這些課程的序列，使在枚舉過(guò)程中盡早地出現(xiàn)可行點(diǎn)。我們將在下面給予具體的說(shuō)明。1、 分支的方法不妨設(shè)每個(gè)班第i門(mén)課有l(wèi)i個(gè)課時(shí)。首先對(duì)這n個(gè)班的所有l(wèi)門(mén)課按課程進(jìn)行適當(dāng)?shù)呐判颍ǜ鶕?jù)每個(gè)學(xué)校的情況而定）。然后再對(duì)每門(mén)課程按教師進(jìn)行排序。這樣就得到了一個(gè)教案序列J=（J1，J2，Ji）,其中Ji表示第i門(mén)課。而Ji=（Ji1,Ji2,.jiti）表示第i門(mén)課共有ti個(gè)教師來(lái)教這n個(gè)班。排課時(shí)就按照這個(gè)序列進(jìn)行?，F(xiàn)在開(kāi)始排課。先排第一門(mén)課的第一個(gè)教師所教的第一個(gè)班，也就是樹(shù)的根。這個(gè)課（n1,l11）的所有排法就是它的所有分支。當(dāng)排定一個(gè)課后（也就是選定一個(gè)分支），不妨

7、設(shè)排在一個(gè)位置（d,t），再排此教師的下一個(gè)班的這門(mén)課，當(dāng)排完了此教師的此門(mén)課的所有班，再排此教師的此門(mén)課的第二輪教案。當(dāng)排完了此教師的所有課程后，再排下一個(gè)教師的此門(mén)課的班，排完了這門(mén)課后，再排下一門(mén)課。如此建立了一課樹(shù)，這棵樹(shù)總共有S=n層（如果有可行解的話）。我們的目的是要找到一種搜索方法F，使得F盡可能快的走到這棵樹(shù)的第S層。在這棵樹(shù)上可以看到會(huì)有大量的分支將達(dá)不到S層。為了剪掉那些不能到達(dá)S層的分支，我們要定義一個(gè)界B，當(dāng)搜索方法F搜索到一個(gè)分支T=（Ji,Jit,nijk,d,t）（即第i門(mén)課，第j個(gè)教師，第k個(gè)班，在位置（d,t），簡(jiǎn)記為d,t）時(shí)，已發(fā)現(xiàn)它的界已超過(guò)了界B，就往

8、回走，當(dāng)實(shí)時(shí)搜索到位置d,t時(shí)，已得到了一些有關(guān)這個(gè)搜索方法F在此位置的一些信息M，利用這些信息M決定F將撤回到哪一層，而不是只回撤一層，這樣就大大地減少了需要搜索的分支，以提高速度。2、 定界的方法從上面的分析可以對(duì)分支定界法的界做一定義如下：（1） 界A1，A2，A3，A4，A5的定義：對(duì)排課程表中的限制條件分別用A1，A2，A3，A4，A5來(lái)表示。我們不妨把它們作為排課過(guò)程中的一些界。如果不滿足它們就表示超出了這些界。此時(shí)的這個(gè)分支將無(wú)可行解。（2） 界A6的定義：設(shè)課表是w·v,w是一周中上課天數(shù)，v是一天中上課節(jié)數(shù)，對(duì)于每個(gè)班都有兩個(gè)拆分：第一拆分和第二拆分。而且必須滿足：

9、第一拆分第二拆分這就是界A6。（3） 界A7的定義：界A7就是：在一個(gè)年級(jí)中，一周中未被使用的空的重復(fù)數(shù)必須小于等于可利用此空的剩余教案的教案數(shù)。（4） 界A8的定義：界A8就是：整個(gè)年級(jí)剩余空的重復(fù)數(shù)和整個(gè)年級(jí)剩余教案數(shù)序的關(guān)系。（5） 界A9的定義：當(dāng)已判斷出在位置d,t已無(wú)可行解時(shí)，利用信息M（它主要包括：1、由哪些界導(dǎo)致此課排不下，2、此課需要什么類型的位置包括哪一天和上下午的的位置），將判斷出位置d,t的上一層是否與在排課有關(guān)，如果無(wú)關(guān)則再往上，一步一步往上走，直到發(fā)現(xiàn)與在排課有關(guān)為止（在實(shí)際人工調(diào)課時(shí)也是如此）。3、 分支定界算法描述從上面的討論和分析，對(duì)求解排課問(wèn)題可行解的搜索采

10、用分支定界法，對(duì)每一個(gè)教案逐一進(jìn)行比配，其搜索過(guò)程如下：從樹(shù)的分支開(kāi)始（選擇了一個(gè)教案），首先判斷此教案所涉及到的班級(jí)中空的情況，即首先考慮禁止點(diǎn)的問(wèn)題。再計(jì)算此教案每個(gè)班的第一拆分和第二拆分，判斷它們是否滿足多連堂排課情況，再判斷界A7和A8的情況，當(dāng)這些班的那些空同時(shí)滿足了教案的要求、周均衡性分配和天均衡性分配的條件，再判斷是否要求和能否滿足集中排課條件。當(dāng)這些界都滿足了，則進(jìn)行排課。如果排此教案成功，則接著排下一個(gè)教案。如果排課沒(méi)有成功（包括已判斷出此時(shí)已超過(guò)某個(gè)或某些界Ai或者沒(méi)有判斷出超過(guò)某個(gè)界，但無(wú)法排下此教案），則根據(jù)這些信息，判斷并計(jì)算出此時(shí)應(yīng)該回撤到哪一層。這時(shí)對(duì)最后一個(gè)已排

11、成功的教案搜索下一種排法。如此循環(huán)，直到排課成功或者第一個(gè)教案已無(wú)法排出下一種可能為止。這樣可以得到一個(gè)分支定界算法如下：1、 開(kāi)始排課；2、 選擇一個(gè)教案；3、 如果所有教案都已被選擇，即都已被排成，轉(zhuǎn)到排課成功4、 對(duì)此教案進(jìn)行排課；5、 排一種此教案的課表；6、 找到了一種排法T；7、 如果滿足界A1，A2，A3，A4，A5，A6，A7和A8則；8、 如果滿足排課條件（條件1），則轉(zhuǎn)到：選擇一個(gè)教案9、 否則轉(zhuǎn)到：排一種此教案的課表10、 否則轉(zhuǎn)到：排一種此教案的課表11、 沒(méi)有找到下一種排法，如果此教案是第一個(gè)，則無(wú)解，轉(zhuǎn)到結(jié)束 否則根據(jù)界A9判斷將往上走到哪一層，并轉(zhuǎn)到 排一種此教案

12、的課表12、 此教案排課成功，則轉(zhuǎn)到選擇一個(gè)教案13、 排課成功14、 結(jié)束4、 分支定界算法的具體計(jì)算結(jié)果對(duì)7個(gè)班、12門(mén)課、27個(gè)教師，滿足條件（條件1）中的幾個(gè)條件的三種情形：星期一星期二星期三星期四星期五第一節(jié)第二節(jié)高二（6）高二（6）第三節(jié)高二（2）第四節(jié)高二（1）高二（6）第五節(jié)高二（1）高二（1）高二（2）高二（1）第六節(jié)高二（6）高二（2）高二（2）第七節(jié)表9 王老師的語(yǔ)文授課表星期一星期二星期三星期四星期五第一節(jié)高二（1）第二節(jié)高二（2）高二（6）第三節(jié)高二（6）高二（1）高二（2）第四節(jié)第五節(jié)高二（1）高二（2）高二（6）第六節(jié)高二（2）第七節(jié)高二（6）高二（1）表10星期

13、一星期二星期三星期四星期五第一節(jié)第二節(jié)高二（2）高二（6）第三節(jié)高二（1）高二（6）高二（2）高二（1）第四節(jié)高二（1）第五節(jié)高二（6）高二（2）第六節(jié)高二（6）第七節(jié)高二（2）高二（1）表11第一種情形：只有條件（條件1）中的條件2和條件6時(shí)計(jì)算得到如表9的課表（只對(duì)楊老師的化學(xué)課進(jìn)行比較）。第二種情形：滿足條件（條件1）中的條件1、2、3、4和6五個(gè)條件時(shí)計(jì)算得到如表10的課表。第三種情形：當(dāng)滿足（條件1）、并且在集中排課條件中的n=2時(shí)計(jì)算得到如表11的課表從上面可以看出，當(dāng)條件加強(qiáng)時(shí)，排出來(lái)的課表也將更加滿足實(shí)際的使用的要求。5、 課程表的調(diào)整當(dāng)已排好的課程表中某個(gè)或某些教師的課程，由

14、于某種原因不能上課或者需要調(diào)整，也就是在已排好的位置被設(shè)成了禁止點(diǎn)。希望得到一個(gè)新的課程表，這是一類新的問(wèn)題。它要求被調(diào)整的課程表上作最少的修改（調(diào)課）。它也是一個(gè)最優(yōu)化的問(wèn)題。也可以用分支定界法求解，只是界的定義要作適當(dāng)?shù)淖兓?。從上可以看到，?duì)中學(xué)課程表問(wèn)題要解決的幾個(gè)主要問(wèn)題是：教案問(wèn)題（包括一天的教案）、教師教課的集中排課問(wèn)題、同一班級(jí)不同科目的周均衡問(wèn)題、同一年級(jí)同一科目的周均衡問(wèn)題。但最關(guān)鍵的問(wèn)題是對(duì)教師的合理安排，因?yàn)樵谖覈?guó)通常學(xué)生的授課時(shí)間沒(méi)有什么限制。而教師常常有這樣和那樣的限制（要求）。另外，我國(guó)的教學(xué)對(duì)一些科目比較重視，而對(duì)另外一些科目要求要低一些，這也產(chǎn)生了一些限制。參考文獻(xiàn)：1、D.J.A. Welsh and M.B.Powell(1976).”An upper bound for the chromatic number of a graph znd its application to time-tabling problems”, Computer J,10,85-872、M.R.Garey and D.S.Johnson, Computers and Intractability:A Gui