中小學(xué)輔助排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

1、中小學(xué)輔助排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)賀 榮摘要：編排課表是中小學(xué)教學(xué)管理中一項(xiàng)重要而又復(fù)雜的工作。它通過合理地安排時(shí)間、教師、課程、班級(jí)四大要素之間的關(guān)系，使全校各個(gè)班級(jí)一周內(nèi)的每節(jié)課，都有合適的教師及課程與之對(duì)應(yīng)。針對(duì)我校自身的校務(wù)情況，在研究過當(dāng)前一些優(yōu)秀的排課算法的基礎(chǔ)上，我研究出一套基本可行的排課程序。它可先根據(jù)教務(wù)人員輸入的約束條件進(jìn)行設(shè)置，通過逐步篩選細(xì)化，將特定的課自動(dòng)安排在最合適的時(shí)間段中安排到最優(yōu)級(jí)的班級(jí)中。如果自動(dòng)排課尚有不成功的地方，會(huì)在課表顯示區(qū)將該課程以紅色顯示進(jìn)行警告。通過這種直觀的輔助手段，教務(wù)人員再配合進(jìn)一步手動(dòng)調(diào)整，最終調(diào)整出滿意的課表。關(guān)鍵詞：排課系統(tǒng) 自動(dòng) 手動(dòng)

2、 輔助一、排課系統(tǒng)的開發(fā)背景隨著教育事業(yè)的不斷發(fā)展，學(xué)校對(duì)教師課程安排的復(fù)雜度不斷增加，如何將一個(gè)學(xué)校各個(gè)學(xué)科每天的課程安排與教室資源的分配合理化是擺在每一個(gè)教務(wù)工作人員面前的一個(gè)難題。傳統(tǒng)的人工排課方式不僅工作繁瑣，工作量大，而且還很容易出現(xiàn)錯(cuò)誤。因此，計(jì)算機(jī)軟件技術(shù)應(yīng)用于學(xué)校的課程安排是發(fā)展的必然。充分發(fā)揮計(jì)算機(jī)自身的優(yōu)勢，將大量復(fù)雜的判斷與運(yùn)算交給計(jì)算機(jī)做，是真正意義上的人腦的“減負(fù)”。教師設(shè)置好學(xué)?；厩闆r及排課要求，讓計(jì)算機(jī)自動(dòng)排出課程表，適度調(diào)課后的課表就能滿意地應(yīng)用于新的學(xué)期。早在上世紀(jì)60年代末，Grotlieb.C.C教授就對(duì)課程表問題進(jìn)行了形式化描述1。排課表這樣的時(shí)間表問

3、題(TTP: T ime-Table-P rob lem ) , 是典型的組合優(yōu)化和不確定性的調(diào)度問題 2, 3 , 并且已被證明是NP完全問題，有其自身固有的數(shù)學(xué)模型，即課表問題存在解，并且能找到解4。排課表問題的難度在于:它是一個(gè)多元受限的問題(受限于課程、時(shí)間、班級(jí)、教師、教室排課五要素) , 如果必須滿足所有的約束條件(而這些條件通常是相互矛盾的) , 則極有可能找不到完整解 5 ; 這也是為什么迄今為止還幾乎沒有完全自動(dòng)生成課表系統(tǒng)的軟件應(yīng)用于實(shí)際，因?yàn)槎鄶?shù)的排課效果好的軟件還需后期手動(dòng)輔助排課進(jìn)行完善，而那些完全自動(dòng)生成的排課軟件，通常會(huì)以降低約束條件的滿足程度為代價(jià)（比如不能均勻

4、分布課程、主副科安排時(shí)間段不很合理等）。目前, 解決課表問題的方法有: 模擬手工排課法 6,7 , 圖論方法, 拉格朗日松弛法, 二次分配型法等多種方法 8, 9 。在以往的教學(xué)管理中，課表編排在許多學(xué)校只能通過人工或人工模擬的方式生成。但是，伴隨著各類學(xué)科范圍的不斷擴(kuò)大，各學(xué)科科目逐漸增多，以至于眾多的教師和學(xué)生、龐大的課時(shí)、復(fù)雜的班級(jí)信息令學(xué)校的教務(wù)安排人員無法高效、合理地制定出相應(yīng)的排課計(jì)劃。這就促使我們的教務(wù)安排人員必須采用一些輔助的手段來幫助自己。因此，計(jì)算機(jī)輔助排課成了現(xiàn)代排課的需要，相應(yīng)的排課算法成了人們探討的主要問題。目前常見的排課算法有貪心算法、遺傳算法、回溯算法等10。研究

5、并使用一種好的算法不僅可以縮短排課時(shí)間，提高排課效率，更可以讓使用者得心應(yīng)手，提高教學(xué)效果。二、排課系統(tǒng)開發(fā)目的及意義排課問題的實(shí)質(zhì)是為教師、學(xué)生的教學(xué)活動(dòng)合理安排時(shí)間上和空間上的資源，以保證教學(xué)活動(dòng)有秩序有計(jì)劃地進(jìn)行。排課工作在教務(wù)工作中處于十分重要地位。用一個(gè)計(jì)算機(jī)自動(dòng)排課系統(tǒng)來完全代替手工排課，是每個(gè)排課程序開發(fā)者的設(shè)計(jì)初衷，但隨著研究的不斷深入，好多開發(fā)者都會(huì)發(fā)現(xiàn)一個(gè)棘手的問題：由于排課眾多的約束條件和超大的求解規(guī)模，使一個(gè)完全的自動(dòng)排課系統(tǒng)的生成可能性變得很小。因此，在約束多、數(shù)量大的前提下，通過人工干涉達(dá)到合理的排課效果是很重要的。開發(fā)“中小學(xué)輔助排課系統(tǒng)”旨在當(dāng)前中小學(xué)教學(xué)模式下

6、，提高排課效率，優(yōu)化排課結(jié)果，探求算法的改進(jìn)，既能首先使用自動(dòng)排課替代以往的手工排課，又能在后期使用輔助手動(dòng)排課進(jìn)一步調(diào)整細(xì)化，使排課結(jié)果更為理想。本設(shè)計(jì)借鑒當(dāng)前成功的排課經(jīng)驗(yàn)并結(jié)合本校的實(shí)際情況，探究出一種優(yōu)化資源分配的自動(dòng)排課，及后期利用手動(dòng)處理優(yōu)化排課結(jié)果的算法。主要有四個(gè)方面：首先是將教師信息按權(quán)值高低進(jìn)行優(yōu)先級(jí)排序。排課時(shí)總的原則是主科教師及課時(shí)量多的教師優(yōu)先進(jìn)行排課，但為了保證教師的排課均勻，設(shè)置變量turned代表輪流次數(shù)，每位教師排課后turned增加1，然后取下一位教師的排課信息，成功排課后該教師的turned變量也增加1，這樣當(dāng)所有教師排了一遍課程以后，再按教師優(yōu)先級(jí)的排序

7、結(jié)果重新來下一輪次，可以保障教師排課的均勻。第二：得到該教師所帶課程及班級(jí)信息后，將教師課表、班級(jí)課表、約束條件設(shè)置表、星期區(qū)間表進(jìn)行“與”操作，判斷出該節(jié)課是否適合安排課程。這里主要體現(xiàn)在經(jīng)過上述四大條件的“與”操作之后，適合安排該課的課節(jié)是一周里面最優(yōu)的時(shí)間段。第三：為保證排課結(jié)果均勻而預(yù)先設(shè)置好 “星期區(qū)間”。有的課程一周2節(jié)，有的課程一周8節(jié)，如何將這些課程在一周內(nèi)均勻地安排，是中小學(xué)排課中一個(gè)很關(guān)鍵的問題。本文首先設(shè)定好一個(gè)“星期約束”表，將周課時(shí)從1節(jié)到8節(jié)分別進(jìn)行星期區(qū)間的合理設(shè)定，當(dāng)排到某課程特定的課節(jié)時(shí)，可以從區(qū)間表中找到它對(duì)應(yīng)的星期區(qū)間，以達(dá)到排課結(jié)果的均勻；最后：在自動(dòng)排

8、課無法達(dá)到理想狀態(tài)，即排課產(chǎn)生沖突的時(shí)候，為用戶提供手動(dòng)輔助排課，以達(dá)到進(jìn)一步優(yōu)化排課結(jié)果的效果。沖突檢測主要通過5個(gè)集合來完成，分別為課程A，教師B，班級(jí)C，約束D，時(shí)段E。其中時(shí)段E即為基礎(chǔ)數(shù)據(jù)模塊中“周課節(jié)設(shè)置”后形成的時(shí)間區(qū)間。如一周上課5天，一天6節(jié)課。從課程A中提取一門需要安排的課，按時(shí)段取用規(guī)則從時(shí)段E中提取一個(gè)時(shí)間片，在這個(gè)時(shí)間片進(jìn)行各種沖突檢測，即對(duì)教師B、班級(jí)C和約束D進(jìn)行檢測，一旦沖突，則跳過此次排課結(jié)果，再進(jìn)行其它嘗試。自動(dòng)排課和手動(dòng)調(diào)整均適用此沖突檢測規(guī)則。 三、 排課準(zhǔn)則及排課算法（一）排課系統(tǒng)的準(zhǔn)則一個(gè)排課系統(tǒng)成功與否，主要取決于排課結(jié)果是否符合以下準(zhǔn)則：1是否滿

9、足“約束條件”，也稱為“硬條件”這是判斷一個(gè)排課系統(tǒng)的生成結(jié)果是否成功的標(biāo)志。本文之所以把約束條件稱為“硬條件”，是因?yàn)樗桥耪n系統(tǒng)必須遵循的條件，如果違背了這些條件形成結(jié)果，那么結(jié)果將視為無效。打個(gè)比方：全校的語文組要在每個(gè)周二的上午集體教研，那么之前設(shè)置的約束條件周二的上午不能安排語文課，則是硬性的必先執(zhí)行的約束條件，排課時(shí)必須做到遵守這一點(diǎn)，否則就會(huì)影響教學(xué)安排，違背了排課系統(tǒng)的設(shè)計(jì)初衷。中小學(xué)的排課系統(tǒng)不同于高校，它沒有教室因素這一要求，即每個(gè)班級(jí)固定為某個(gè)教室，其常見的約束條件如下所列：（1）教師不能沖突：一名教師不能同時(shí)帶多個(gè)班的課程，合班課除外；教師先前做好的約定不能被違背，比如

10、張老師要求周一上午第4節(jié)不予安排課。（2） 班級(jí)不能沖突：同一時(shí)間段一個(gè)班級(jí)不能同時(shí)由多位教師上課，如初一1班周一第2節(jié)，同時(shí)由語文張老師和數(shù)學(xué)李老師上課是不合理的；班級(jí)的約束條件不能被違背，如全校周一下午第2節(jié)固定設(shè)置為班會(huì)。2是否滿足“優(yōu)化條件”，也可稱為“軟條件”優(yōu)化條件，又稱軟條件，是在排課過程中可以滿足同時(shí)又可以不完全滿足的約束條件，是在滿足硬約束條件的基礎(chǔ)上能盡量要求滿足的約束條件，軟約束條件可以根據(jù)不同的教學(xué)情況有所差異。有時(shí)可以通過調(diào)節(jié)軟約束條件的滿足程度而改變排課的效果，可以將一定要滿足的軟約束條件轉(zhuǎn)換為“硬約束條件”。常見的優(yōu)化條件如下所列：（1）同一班級(jí)的某門課程，一周內(nèi)

11、上課的時(shí)間盡量均勻分散安排。（2）主科安排在主要時(shí)間段，一般為上午，副科安排在次要時(shí)間段。（3）教師課程安排合理：任課多的教師一周的工作量要合理分布。（4）占用公共資源的的課程如微機(jī)、體育，以及學(xué)時(shí)多的課程優(yōu)先進(jìn)行處理。優(yōu)化條件是判斷一個(gè)排課系統(tǒng)的生成結(jié)果是否成功的標(biāo)志。也就是說，一個(gè)排課程序，如果能實(shí)現(xiàn)所有的“約束條件”，也就是硬條件，那么說它是合格的，但未必代表它就是成功的。只有同時(shí)滿足了“優(yōu)化條件”，也就是軟約束條件，才能說它是一款成功的排課系統(tǒng)。（二）優(yōu)化排課算法的實(shí)現(xiàn)設(shè)計(jì)排課系統(tǒng)算法有一定的復(fù)雜性，因?yàn)樗婕暗浇處?、班?jí) 、時(shí)間、課程四大信息對(duì)象，如果是高校的話，還會(huì)涉及到“教室”第

12、五個(gè)因素。算法的目標(biāo)是為滿足學(xué)校教學(xué)需求而合理分配資源，其關(guān)鍵核心問題即在于：解決沖突。試想，一個(gè)學(xué)校幾十個(gè)班級(jí)、十幾門課程、百十名教師、幾十個(gè)時(shí)間段將這么多的因素交叉在一起形成一系列完全沒有沖突的課表，絕不可能是隨便一個(gè)簡單的算法能夠?qū)崿F(xiàn)得了的。雖然目前已經(jīng)出現(xiàn)了許多用不同算法設(shè)計(jì)的自動(dòng)排課系統(tǒng)，但它們或多或少存在著不足；或因適用范圍太廣而導(dǎo)致操作復(fù)雜，需要手工錄入的排課信息量太大；或因排課算法不合理導(dǎo)致排課時(shí)間過長，有的甚至導(dǎo)致死機(jī)；還有的排課速度很快，結(jié)果卻差如人意，只是滿足了一定的硬性約束條件，而優(yōu)化條件卻滿足的很少，導(dǎo)致排課效果一般。而且大多數(shù)是針對(duì)大專院校需求開發(fā)設(shè)計(jì)的，很難適用于

13、義務(wù)階段的中小學(xué)校的特殊的教學(xué)安排。因此，本文在分析了當(dāng)前中小學(xué)課程，并了解了一些學(xué)?，F(xiàn)有排課方法后，整理出了一套針對(duì)本校排課使用的的算法，它能比較有效處理各種復(fù)雜的沖突，而且能自動(dòng)呈現(xiàn)排課結(jié)果，之后還可以根據(jù)用戶自己的需求進(jìn)一步手工調(diào)整，該算法基本能滿足中小學(xué)校的排課要求。1構(gòu)造時(shí)間模式庫時(shí)間模式是根據(jù)教務(wù)人員的經(jīng)驗(yàn)， 為各種周學(xué)時(shí)數(shù)不同的課程指定的一種時(shí)間組合方式。例如， 一門課程的周學(xué)時(shí)數(shù)為4， 那么它的時(shí)間組合方式可以有:“11”，“22”“32”，“41”; 表示該課程一周上4次， 分別為周一的第1 節(jié)、周二的第2 節(jié)、周三的第2節(jié)和周四的第1節(jié)，同時(shí)， 為了達(dá)到較好的上課效果， 也

14、要對(duì)這些時(shí)間模式進(jìn)行分級(jí)。如下所示： 時(shí)間模式舉例周一 周二 周三 周四 周五第1節(jié) 11 21 31 41 51第2節(jié) 12 22 32 42 52第6節(jié) 16 26 36 46 56第7節(jié) 17 27 37 47 57其中， 前一位數(shù)字表示星期，將周一至周五用數(shù)字1 5 表示，后一位數(shù)字表示上課節(jié)次，第1-8節(jié)分別用數(shù)字1 8 表示。 例如數(shù)字“42”表示周四的第2 節(jié)，數(shù)字“56”表示周五的第六節(jié)。這樣，對(duì)于每種周學(xué)時(shí)數(shù)，可以將所有合理的時(shí)間組合形式存入模式庫中，以便進(jìn)行時(shí)間處理時(shí)可以用時(shí)間模式庫中的各種模式進(jìn)行匹配。2建立時(shí)間數(shù)組（1）建立班級(jí)教師空閑時(shí)間表為了表示班級(jí)、教師的可排課時(shí)

15、間，分別為他們建立一維數(shù)組，因?yàn)橹行W(xué)班級(jí)固定，所以不考慮教室的可排課時(shí)間，例如：某位教師的初始可排課時(shí)間數(shù)組為(1111111111111111111111111111 1111111)。其中共有五組數(shù)據(jù)，分別表示一周中的五天； 而一組數(shù)據(jù)共有7 個(gè)字符，分別表示一天中的七個(gè)時(shí)間單元，初始置為1時(shí)，表示該教師一周中的每一時(shí)間段均為空閑無課時(shí)間。當(dāng)為某位教師分配時(shí)間后，相應(yīng)的那位字符就置為0，例如，某位教師的可排課時(shí)間數(shù)組為( 0101111 1011101 0011111 11011110110111) ，則表示這位教師在周一的第1 、3節(jié)， 周二的2、6 節(jié)， 周三的1、2 節(jié)， 周四的第

16、3 節(jié)， 周五的第1、4節(jié)已經(jīng)安排了課程， 如果要再安排課程的話， 就應(yīng)該在值為1的時(shí)間單元中篩選。對(duì)于班級(jí)也可以進(jìn)行同樣的處理，分別標(biāo)出班級(jí)可排課時(shí)間。例如， 某班級(jí)的可排課時(shí)間數(shù)組為( 0001111 1011101 0011111 11011110111101) ， 則表示這個(gè)班級(jí)在周一的第1 、2、3節(jié)， 周二的2、6 節(jié)， 周三的1、2 節(jié)， 周四的第3 節(jié)， 周五的第1、6節(jié)已經(jīng)安排了課程， 如果要再安排課程的話， 就應(yīng)該在非0 的時(shí)間單元中篩選。將教師可排時(shí)間與班級(jí)可排時(shí)間作“&”與操作之后，即可以得出教師班級(jí)空閑時(shí)間表。例如將上述兩數(shù)組進(jìn)行與操作之后，可以得到如下數(shù)組：( 00

17、01111 1011101 0011111 11011110110101)，即再安排課時(shí)，該班級(jí)的周一第123節(jié)課、周二的第2、6節(jié)課、周三的1、2節(jié)課、周四的第3節(jié)課、周五的1、4、6節(jié)課均已有安排，需要在其它的時(shí)間段進(jìn)行選擇和安排。（2）建立星期區(qū)間表為了實(shí)現(xiàn)排課的均勻，本文將星期按區(qū)間進(jìn)行分配，舉個(gè)例子，如果當(dāng)前處理的課是一周2節(jié)的音樂課，并且當(dāng)前排的是本周的第2次音樂課，則要從數(shù)據(jù)庫中找到對(duì)應(yīng)的course_count=2、turned=1時(shí)對(duì)應(yīng)的星期約束條件數(shù)組（1111111 1111111 1111000 0000000 0000000）來進(jìn)行排課，這其實(shí)是教務(wù)工作人員前臺(tái)進(jìn)行約

18、束設(shè)置后，在后臺(tái)的一種對(duì)應(yīng)體現(xiàn)，即本次排課只能從一周的上半周中進(jìn)行選擇，這樣就可以進(jìn)一步優(yōu)化排課范圍。同樣，如果現(xiàn)在要排音樂課的第2次課程時(shí)，將從數(shù)據(jù)庫中找到對(duì)應(yīng)字段的值course_count=2、turned=2來進(jìn)行排課。此時(shí)，對(duì)應(yīng)的數(shù)組（0000000 0000000 0001111 1111111 1111111），直接從下半周中進(jìn)行篩選，不必浪費(fèi)時(shí)間安排到不合理的時(shí)間段，過后再進(jìn)行檢查和修正。（3）建立約束條件區(qū)間表中小學(xué)排課有一個(gè)最大的特點(diǎn)就在于主副科課程的安排，語文、數(shù)學(xué)、英語作為主科一般安排在上午較好的時(shí)間段，音、體、美等副科安排在上午后面的時(shí)間段或下午。是否能合理地安排好主

19、副科，是一個(gè)中小學(xué)排課軟件是否成功的重要體現(xiàn)，此處通過建立區(qū)間表的方法來體現(xiàn)該約束條件。在自動(dòng)排課之前，教務(wù)人員就會(huì)將每門課程的約束條件輸入到程序中，在前臺(tái)，用不同的顏色來為用戶表示約束條件的設(shè)置，而在后臺(tái)，對(duì)應(yīng)了不同的數(shù)值來代表該條件。比如主科可以設(shè)置每天上午前3節(jié)為適合，后臺(tái)將對(duì)應(yīng)的權(quán)值“0”寫入數(shù)據(jù)庫約束表T_COURSE_WHERE，前臺(tái)課程控件對(duì)應(yīng)字體顯示為紅色（clRed），代表這些課節(jié)適合安排主科。下午第2節(jié)及以后時(shí)間段不適合安排主科，后臺(tái)將對(duì)應(yīng)的權(quán)值“2”寫入數(shù)據(jù)庫約束表T_COURSE_WHERE，前臺(tái)課程控件對(duì)應(yīng)字體選用藍(lán)色（clBlue）進(jìn)行設(shè)置。課程約束條件設(shè)置示意圖如

20、圖1所示。說明：實(shí)際操作中，課表中的課程用紅色代表適合，粉色代表正常，藍(lán)色代表不適合。周一周二周三周四周五上午1234下午123適合（0）正常（1）不適合（2）適合（0）正常（1）不適合（2）語文約束周一周二周三周四周五上午1234下午123適合（0）正常（1）不適合（2）音樂約束圖1 課程約束條件設(shè)置示意圖還以音樂課為例，音樂課屬于副科，其最好的安排時(shí)間段為每天上午最后一節(jié)和下午，所以其對(duì)應(yīng)的約束條件區(qū)間為（0001111 0001111 0001111 0001111 0001111）。在拿到一門課程時(shí)，首先從庫里找到這4張區(qū)間表，其中班級(jí)和教師空閑表合成后成為一張班級(jí)教師空閑表，然后將班

21、級(jí)教師空閑時(shí)間表、星期區(qū)間表、約束條件區(qū)間表相與之后，即可得到排課可用時(shí)間表。排課可用時(shí)間表的生成示意圖如圖2所示。00111001011111111011111111111111111111001110011100111001100011000110000000000000000000111101111111111111100111001011111111011111111111111111&排課可用時(shí)間表教師班級(jí)空閑時(shí)間表約束條件表星期區(qū)間表圖2 排課可用時(shí)間表的生成示意圖排課可用時(shí)間表與課程表的直觀對(duì)應(yīng)關(guān)系如圖3所示。說明：表格中的 部分代表該時(shí)段已安排課程。 周一周二周三周四周五上午1

22、234下午12300000000000000001000010001100011000排課可用時(shí)間表按時(shí)間空閑排課圖3 排課可用時(shí)間表直觀圖3建立tmies-week區(qū)間。（這里將課程數(shù)course_count簡稱為times。）排課結(jié)果是否均勻是體現(xiàn)一個(gè)排課系統(tǒng)是否成功的重要指標(biāo)，本文將不同的周課時(shí)數(shù)在五天內(nèi)的分布進(jìn)行了合理的安排，排課時(shí)，根據(jù)某門課程對(duì)應(yīng)的times和turned兩個(gè)參數(shù)尋找到對(duì)應(yīng)的數(shù)據(jù)進(jìn)行排課均勻的優(yōu)化操作。實(shí)際操作中，可以根據(jù)排課人員自己的實(shí)際要求來詳細(xì)設(shè)定。參見圖4 times-week區(qū)間圖。星期times周一周二周三周四周五81、2、34、5、67、8712、3、

23、45、6、761、2、34、5651234541234312321211圖4 times-week區(qū)間圖舉兩個(gè)例子予以說明：周課時(shí)為5節(jié)的課程，為保證排課的均勻，安排課程時(shí)定為一天一節(jié)。如times=5,turned=2時(shí)，表示周課時(shí)數(shù)為5，輪流次數(shù)為2，其排課區(qū)間為周二的全天，即（0000000 1111111 0000000 0000000 0000000）。周課時(shí)為8節(jié)的課程，將第1、2、3節(jié)放到周一、周二中進(jìn)行安排；第4、5、6節(jié)放到周三、四中安排；第7、8節(jié)放到周五中安排。如times=8，turned=4時(shí)，表示周課時(shí)數(shù)為8，輪流次數(shù)為4，就只能在周三、四中進(jìn)行安插，其對(duì)應(yīng)的區(qū)間為

24、（0000000 0000000 1111111 1111111 0000000）。在整個(gè)自動(dòng)排課過程中，算法的主要思想是：首先將教師按所教課程的級(jí)別及課時(shí)數(shù)設(shè)定優(yōu)先級(jí)，以保證主科教師及課時(shí)量大的教師能夠得到優(yōu)先排課的權(quán)利；之后，在時(shí)間分配時(shí)，總是在尚未分配的時(shí)間單元中選擇上課效果最好的單元。具體處理過程如下：（1）設(shè)定優(yōu)先級(jí)以教師為主線，按照優(yōu)先級(jí)進(jìn)行排序。 *按主副科級(jí)別rank：語數(shù)英：3 政物化：2 其它：1 *按周課時(shí)數(shù)： times 級(jí)別計(jì)算：piror=rank*3+times（2）查詢可用時(shí)間單元的步驟第1 步：初始化所有教師和所有班級(jí)的最大可安排時(shí)間數(shù)組為( 1111111

25、1111111 1111111 1111111 1111111)。第2 步： 從數(shù)據(jù)庫中找出該教師所帶課程對(duì)應(yīng)的星期區(qū)間表，即time-week區(qū)間。第3步：查找該課程所對(duì)應(yīng)的約束條件表。第4 步：將前3步得到的4個(gè)區(qū)間表進(jìn)行“與”操作，得到該教師所帶課程可以安排的時(shí)間單元。第5 步：依次處理教師時(shí)間數(shù)組和相關(guān)班級(jí)時(shí)間數(shù)組，將已成功安排的課對(duì)應(yīng)的位置置為0，保存到各個(gè)對(duì)應(yīng)的數(shù)據(jù)表中。4進(jìn)行沖突檢測排課過程中的沖突是要根據(jù)實(shí)際情況進(jìn)行消除的，一張不符合教務(wù)需求的課表是無效的課表。沖突檢測分以下幾種情況：(1)某特定的時(shí)間段的某門課程，對(duì)應(yīng)教師是否已經(jīng)排課；(2)某特定的時(shí)間段，班級(jí)中是否已經(jīng)排課

26、；(3)課程安排是否與約束條件相符合；(4)某課程的周課時(shí)數(shù)是否已經(jīng)全部安排完畢；自動(dòng)排課中，要全部使用上述4點(diǎn)沖突檢測方法，最終結(jié)果是否沖突要以前臺(tái)課程顯示的不同顏色來表示，例如：中小學(xué)語文課是主科，要求排課時(shí)最好排在上午的比較好的時(shí)間段中，可以通過“課程約束”模塊，對(duì)本課對(duì)應(yīng)課節(jié)分別設(shè)置“適合”、“正?！薄ⅰ安贿m合”來做約束（將對(duì)應(yīng)的值0、1、2分別保存到T_COURSE_WHERE表的F_COURSE_TYPE字段中，而0、1、2又對(duì)應(yīng)不同的顏色值。如果主科被安排在下午第2節(jié)，則視為與約束條件不符合，約束結(jié)果為“不適合”，對(duì)應(yīng)值為2，調(diào)取相應(yīng)的顏色模塊返回前臺(tái)進(jìn)行顯示，用戶根據(jù)顏色就可以

27、判斷自動(dòng)排課結(jié)果是否正常。手動(dòng)排課中，只使用到第1種和第4種沖突檢測方法。當(dāng)用戶手動(dòng)進(jìn)行課程安排的時(shí)候，首先判斷該課程一周的課時(shí)數(shù)是否已經(jīng)排滿，如果排滿則彈出對(duì)話框進(jìn)行警告，并禁止本次手動(dòng)安排。其次還應(yīng)判斷該課程對(duì)應(yīng)的授課教師，是否該時(shí)段在別的班級(jí)有課，如果有則彈出對(duì)話框進(jìn)行警告，并禁止本次手動(dòng)排課。5手動(dòng)輔助處理計(jì)算機(jī)自動(dòng)排課也需要進(jìn)行手動(dòng)排課的輔助，以便可以使得能夠根據(jù)自己的具體要求對(duì)排課算法中的一些參數(shù)進(jìn)行設(shè)置和修正，并對(duì)計(jì)算機(jī)排出的課表進(jìn)行調(diào)整，本算法所設(shè)計(jì)的人工干預(yù)過程有：時(shí)間模式庫的設(shè)置，約束條件的設(shè)置，自動(dòng)排課后的結(jié)果調(diào)整，通過這些方法為用戶呈現(xiàn)滿意的課程表。手動(dòng)輔助處理的具體內(nèi)

28、容如下：（1）一周上幾天，一天幾節(jié)課，用戶可以根據(jù)自己的需求來設(shè)置時(shí)間模式庫；（2）語文適合安排在哪個(gè)時(shí)間段，體育適合安排在哪個(gè)時(shí)間段，用戶可以自行設(shè)定相應(yīng)的約束條件；（3）自動(dòng)排課后，針對(duì)沖突的或排課結(jié)果不理想的課程，系統(tǒng)提供手動(dòng)排課。排課時(shí)系統(tǒng)會(huì)將課程以不同顏色進(jìn)行顯示，方便用戶對(duì)安排不合理的課程及時(shí)更改，同時(shí)系統(tǒng)會(huì)給用戶列出該課程對(duì)應(yīng)的周課時(shí)數(shù)及已排次數(shù)，提高用戶手動(dòng)排課的效率。四、 程序的實(shí)現(xiàn)（一）基礎(chǔ)數(shù)據(jù)設(shè)置該模塊的運(yùn)行窗口，如圖5所示。圖5 基礎(chǔ)數(shù)據(jù)設(shè)置窗體（二）班級(jí)課程設(shè)置這是設(shè)置某一班級(jí)具體開設(shè)哪些課程、每門課程的周課節(jié)數(shù)是多少的模塊。班級(jí)課程設(shè)置窗口如圖6所示。圖6 班級(jí)課程

29、設(shè)置窗體（三）教師課程設(shè)置該模塊可以設(shè)置每位教師任哪個(gè)班級(jí)的哪一門課。將教師、班級(jí)、課程多種排課條件進(jìn)行關(guān)聯(lián)。教師課程設(shè)置窗口如圖7所示。圖7 教師課程設(shè)置窗體（四）課程約束設(shè)置該模塊主要實(shí)現(xiàn)對(duì)課程約束條件的設(shè)定。中小學(xué)排課系統(tǒng)中，通常要把主科排在上午的時(shí)段，一些副科排在下午的時(shí)段，或者因?yàn)榻萄谢顒?dòng)等原因，需要對(duì)課程進(jìn)行合理的分配與安排。該模塊的設(shè)定可以對(duì)排課的優(yōu)先順序產(chǎn)生影響，也可以使最終的排課結(jié)果以對(duì)應(yīng)顏色顯示，使用戶能夠了解排課結(jié)果，并適當(dāng)進(jìn)行下一步修改。如圖8所示。圖8 課程約束設(shè)置窗體(五)自動(dòng)排課算法模塊該模塊的運(yùn)行窗體，如圖9所示。圖9 自動(dòng)排課運(yùn)行窗體（六） 手動(dòng)排課運(yùn)行模塊該模塊的運(yùn)行窗體，如圖10所示。圖10手動(dòng)排課運(yùn)行窗體五、結(jié)束語該設(shè)計(jì)是本人在分析目前大量成功的排課系統(tǒng)基礎(chǔ)之上，結(jié)合自己在學(xué)校幫助教務(wù)主任排課的經(jīng)驗(yàn)，通過研究與比較各算法領(lǐng)域中成功而科學(xué)的理論思想而探索出的一套排課算法。該系統(tǒng)能夠首先進(jìn)行自動(dòng)排課，而且之后可以利用顏色與權(quán)值相結(jié)合的簡單易實(shí)現(xiàn)的方法，引導(dǎo)用戶方便快捷地手工進(jìn)行調(diào)整，直到排出滿意的課表。但本系統(tǒng)也有許多不完善之處，比如在設(shè)置約束條件的時(shí)候，不能夠使用拖曳實(shí)現(xiàn)，只能用右鍵單擊的方法做，不夠人性化，使用起來不太方便。另外本設(shè)計(jì)只能對(duì)課程進(jìn)行約束條