排課系統(tǒng)的開發(fā)和實現(xiàn)

1、排課系統(tǒng)的開發(fā)和實現(xiàn)摘要要完成一所大學或者一個學院的課程安排是一件非常復雜的問題，如果用人手工進行安排的話，需要極大的精力和時間。而在排課的時候，需要考慮的范圍，涉及到教師、課程、教室還有班級情況等等。而在現(xiàn)今的大學排課過程中，整個學校需要考慮的教師，課程信息是成百上千，排課問題由此變?yōu)橐粋€異常復雜的組合問題。所以在現(xiàn)實世界的應用中，排課問題的所有排列組合對于人類來說幾乎可以被認為是一個天文數(shù)字。而一個可以被接受的排課方案是一個滿足排課所有制約性要求的方案。在此基礎上，如果有人希望能通過一些啟發(fā)性的設定而得到一個更為優(yōu)化(更為合理，美觀，更為符合人的習慣)的排課方案的話，則這個問題就會變得超乎

2、尋常的困難。所以迄今為止，為了能夠用計算機自動完成排課任務已經(jīng)進行了非常多的嘗試。排課的本質(zhì)問題是將大量的課程安排進有限的上課時間和教室中，與此同時還會涉及到任課老師和學生班級等各種因素互相制約的影響。通常來說，排課中涉及的變量越多，則排課問題就會越復雜。而本課題的排課研究涉及的排課環(huán)境是上海交通大學的網(wǎng)絡學院。網(wǎng)絡學院的排課是排課問題中的一個全新的領域。因為，在網(wǎng)絡學院中，教室有了多媒體，視聽等各種新的屬性，而這在傳統(tǒng)的排課問題中是沒有的。而且，網(wǎng)絡學院的上課時間也更具多樣性。不同的專業(yè)，有的每天上午最多只能排4節(jié)課，而有的專業(yè)卻可以安排5節(jié)課。時間標準的多樣性，教室屬性的多樣性，使得網(wǎng)絡學

3、院的排課問題需要考慮更多的因素，從而給排課提出了更高的要求。本文所做的研究工作先是比較了一下當今比較流行的集中排課算法，如線性算法、遺傳算法、限制邏輯(CLP)編程等等算法各自的優(yōu)缺點和適用性。并且，在此基礎上，本文針對網(wǎng)絡學院排課更為特殊的要求，提出了一個新的算法。最終，基于本文所提出的這個算法，開發(fā)出了一個全新的排課模型，使其不但能適應普通的排課環(huán)境，還能夠很好地滿足網(wǎng)絡學院更為特殊的排課要求。關鍵詞：遠程教育，排課，人工智能，遺傳算法，限制邏輯編程上海交通大學學士論文網(wǎng)絡學院排課系統(tǒng)的實現(xiàn) THECONSTRUCTIONOFTIMETABLESFORSCHOOLCOURSESAbstra

4、ctTheconstructionoftimetablesforuniversitiesorschoolsisanextremelycomplexproblem,whosemanualsolutionrequiresmucheffort.Thesetofallpossiblesolutions,thatisthespaceoftheproblem,isverylarge,atleastintherealworldexamples.Anacceptablesolutionisonewhosatisfiesalltheproblemconstraints.Theproblemgoesevenmor

5、edifficultifsomeonewantstogenerateanoptimumtimetableaccordingtosomeheuristiccriteria.Variousattemptshavebeenmadesofarontheautomaticsolvingofthetimetablingproblembyacomputer.Thecourse-timetablingproblemessentiallyinvolvestheassignmentofweeklylecturestotimeperiodsandlecturerooms.Andgenerallyspeaking,t

6、hemorevariablethetimetablinghas,themorecomplexitis.Becausetherearequitealotofversionsofthetimetablingproblem,differingfromoneschooltothenext,wefocusonconstructingcoursetimetablesatourownlong-learningschool.ThetimetablingforournetworkschoolisabrandnewintheTTParea.Inthisproblem,theclassroomshaveattrib

7、utessuchasMultimedia,Videothatweneverencounteredbefore.Someobstacleslikethatmakethetimetablingforthenetworkschoolamorecomplexproblemandbringalotofnewchallenges.Inthispaper,somepopularTTPalgorithmssuchasLinear,geneticalgorithmshavebeenintroduced.Andaccordingtotheespeciallyhighdemandofthenetworkschool

8、,thepaperbringsanewalgorithmandaccomplishedanewtimetablingsystem.Itnotonlymeetsthedemandofordinarytimetablingproblem,butalsosatisfiesthenetworkschoolsespeciallycomplicatedstandard.Keywords:Distance-Learning,timetabling,ArtificialIntelligence,geneticalgorithms，evolutionaryalgorithms，ConstraintLogicPr

9、ogramming(CLP)目錄TOC o 1-5 h z HYPERLINK l bookmark8 第一章緒論5 HYPERLINK l bookmark10 1.1網(wǎng)絡教育特點和發(fā)展現(xiàn)狀5 HYPERLINK l bookmark12 1.2本課題的研究背景6 HYPERLINK l bookmark14 1.3本課題的研究目標7 HYPERLINK l bookmark16 1.4本課題研究應解決的主要問題7 HYPERLINK l bookmark18 第二章排課問題的理論介紹8 HYPERLINK l bookmark20 2.1排課問題的誕生8 HYPERLINK l bookm

10、ark24 2.2目前排課問題的幾個普遍的算法9 HYPERLINK l bookmark26 2.2.1SimulatedAnnealing9 HYPERLINK l bookmark28 2.2.2ConstraintLogicProgramming11 HYPERLINK l bookmark30 2.2.3GraphicColoringHeuristics11 HYPERLINK l bookmark32 2.2.4GeneticAlgorithms12 HYPERLINK l bookmark34 2.2.5LinearProgramming13 HYPERLINK l bookma

11、rk36 2.3小結13 HYPERLINK l bookmark38 第三章排課問題的要求13 HYPERLINK l bookmark40 3.1對本排課系統(tǒng)的要求13 HYPERLINK l bookmark42 3.1目標14 HYPERLINK l bookmark44 3.2排課的基本情況14 HYPERLINK l bookmark46 3.2.1教學任務的劃分14 HYPERLINK l bookmark48 3.2.2不同教學任務教學時間的安排14 HYPERLINK l bookmark50 3.2.3排課中按照課程重要性的劃分14 HYPERLINK l bookmark

12、52 3.2.4關于排課時間的概念15 HYPERLINK l bookmark54 3.2.5關于中同一門課程的持續(xù)時間的安排15 HYPERLINK l bookmark56 3.3排課過程中遇到的各種條件和限制15 HYPERLINK l bookmark60 3.3.1排課系統(tǒng)必須滿足的條件(hardconstraints)163.3.2排課系統(tǒng)會盡量爭取滿足的條件(softconstraints)17 HYPERLINK l bookmark62 3.4小結17 HYPERLINK l bookmark64 第四章本課題所做排課系統(tǒng)的實現(xiàn)18 HYPERLINK l bookmark

13、66 4.1本排課系統(tǒng)的排課過程18 HYPERLINK l bookmark68 4.2本排課系統(tǒng)的實現(xiàn)原理19 HYPERLINK l bookmark70 4.2.1開發(fā)工具和前期準備194.2.2排課系統(tǒng)的基本思路和算法19 HYPERLINK l bookmark94 4.3本排課算法的小結26 HYPERLINK l bookmark96 第五章本排課系統(tǒng)的使用介紹27 HYPERLINK l bookmark98 5.1信息的輸入27 HYPERLINK l bookmark100 5.1.1教室信息的輸入27 HYPERLINK l bookmark102 5.1.2班級信息的

14、輸入28 HYPERLINK l bookmark104 5.1.3課程信息的輸入28 HYPERLINK l bookmark106 5.1.4教師信息的輸入29 HYPERLINK l bookmark110 5.2課表的生成30 HYPERLINK l bookmark112 第六章總結和展望31 HYPERLINK l bookmark114 6.1本課題完成的總結31 HYPERLINK l bookmark116 6.2對于排課系統(tǒng)的期望31 HYPERLINK l bookmark118 6.2.1排課系統(tǒng)的架構32 HYPERLINK l bookmark120 6.2.2us

15、ecase技術32 HYPERLINK l bookmark122 6.2.3COM/DCOM標準對象模型32致謝34 HYPERLINK l bookmark126 參考文獻與附錄:35第一章緒論隨著社會科技的不斷發(fā)展，特別近20年來在信息技術上所取得的革命性進步，我們的生活方式也不可避免的不斷地受信息技術影響而改變，其中就包括我們長久以來的學習方式。有著長久歷史的課堂教學模式，由于有著地域（跨地域的不可行性），時間（時間上的不靈活性）以及資源（合格的教師資源和課堂資源的短缺性）已經(jīng)漸漸難以勝任現(xiàn)代社會日益增長的全民學習和終身學習的要求了。而與此同時，信息技術，特別是近年來迅速發(fā)展的互聯(lián)網(wǎng)（

16、INTERNET）為我們帶來了一個全新的教育理念遠程教育。1.1網(wǎng)絡教育特點和發(fā)展現(xiàn)狀網(wǎng)絡教育可以是遠程教育的一種模式。遠程教育是指位于不同地點的教師和學生通過通信的方式來完成教學任務。遠程教育的先驅應該是郵件式的函授教育。通過郵件的函授教育，存在著教育雙方的延時非常嚴重的情況（郵件在兩地來回的時間），可謂不是非常的理想。隨著社會技術的不斷進步，在上個世紀的二，三十年代出現(xiàn)了基于收音機的廣播教育。然后在上世紀的五，六十年代隨著電視的普及，又誕生了電視學校。不過，無論是廣播還是電視，教學中非常重要的交互性（教師和學生之間的及時互動）以及可回溯性（學生在任何時間想要復習一下以前所學的內(nèi)容）都由于技

17、術的原因沒能很好實現(xiàn)。值得慶幸的是，隨著互聯(lián)網(wǎng)的飛速發(fā)展，遠程教育的最新形勢，通過互聯(lián)網(wǎng)Internet或是局域網(wǎng)Intranet的網(wǎng)絡教育迅速興起，并且提供了目前為止作為理想的遠程教育方式。目前的對于網(wǎng)絡教育的研究差不多集中在以下兩個領域：基于Web的遠程教育和實時的遠程教育。在基于Web的方式下，教學內(nèi)容以課間的形式放在Web服務器上，學習者可以在任意時間任意地點獨立地學習，我們稱之為以學生為中心的學習模式。而實時的遠程教學則主要利用視頻會議系統(tǒng)傳輸視頻和音頻，購建一種分布式的教室，在這種環(huán)境下，教師和學生只是在物理位置上不同，我們稱之為面向教師的學習模式。在以上兩個研究領域中，基于Web

18、的教學模式由于對系統(tǒng)配置無特殊要求，在Internet上應用較為容易。而實時的遠程教學模式，由于對傳輸視頻和音頻系統(tǒng)有較高要求，同時還要考慮到主教室和分教室之間互相配合的各種情況，運作較復雜，但是由于交互性更好一點，所以在教學的效果上更甚一籌。所以，在目前的情況下，兩種教學模式互相依存，共同發(fā)展。比如上海交通大學的網(wǎng)絡學院教學模式，現(xiàn)在就以實時的遠程教學模式為主，基于Web的教學模式為輔。1.2本課題的研究背景為了適應這種網(wǎng)絡的教育模式，上海交通大學網(wǎng)絡教育學院開發(fā)了一個非常集成度非常高的電子教務平臺。這個平臺所包括的教務管理內(nèi)容有1、排課2、注冊3、學生基本信息統(tǒng)計4、成績管理5、畢業(yè)資格審

19、查6、證書制作、發(fā)放7、歸檔其中，排課的部分又細分為、按專業(yè)制定教學培養(yǎng)計劃（全部課程，包括畢業(yè)設計或論文）；、按專業(yè)制定每學期教學執(zhí)行計劃；、按開設的課程聘請（落實）上課教師；、根據(jù)教學執(zhí)行計劃、學生人數(shù)、學生選課地點、教師要求及教室等情況排課；但是，在電子教務系統(tǒng)中，排課的工作目前仍就是由負責排課的教師手工編排。當學院開設的課程越來越多以后，教師的安排，教室的安排和課程的安排，各種制約條件之間的矛盾會越來越難處理。用手工編排，費時費力費心，還難免會有顧此失彼的情況發(fā)生，所以將排課部分由計算機來完成這一工作變的日益重要。而縱觀目前市面上說流行的各種排課系統(tǒng)軟件，不是小學版的，就是中學版的，主

20、要原因是中小學的上課安排規(guī)律性很強，每次上課人數(shù)由一個班級組成，不需要換教室，沒有上下學期課程不同之分，每天上課都為早上4節(jié)，下午2-3節(jié)的固定時間。沒有晚上要上課的要求，白天也不會有課時空著等等情況出現(xiàn)。而大學的排課問題就要復雜很多，而且各個大學的教學情況不同，導致對排課的要求也有很大的不一樣。所以，目前適合大學排課的軟件市面上比較罕見。而網(wǎng)絡教育學院的排課比起普通的大學排課方式，更要麻煩許多。比如，網(wǎng)絡學院的教室就有多媒體教室，視聽教室等等目前普通的大學排課中還沒有遇到的問題。而且，在網(wǎng)絡學院的授課中，有時還會出現(xiàn)教師在主教室上課，而通過連線的方式，另外有一部分同學在分教室上課的情況。至于

21、是否能進行連線上課，除了要考慮教室的容量和學生的數(shù)目，還要考慮所授課程是否適合在不同的教室中連線授課，還要考慮教室的性質(zhì)是否能符合連線上課在技術上的要求。并且在目前網(wǎng)絡學院的教學中，除了普通的本科生教學任務外，還有為了滿足社會需求而開設的工程碩士課程，其課程又要求安排在雙休日和星期一至星期五的晚上，而且其每個課時的長短，每天上課的課時數(shù)又和普通網(wǎng)絡學院的本科生有很大不同。所以由此產(chǎn)生的現(xiàn)實是，市面上無數(shù)種軟件中沒有為網(wǎng)絡學院的排課所開發(fā)的軟件。因此，作為計算機領域的一個經(jīng)典課題，本文的研究課題，“排課系統(tǒng)”，作為網(wǎng)絡教育學院電子教務平臺的一個補充，在這樣的背景環(huán)境下被提了出來。1.3本課題的研

22、究目標排課系統(tǒng)的本質(zhì)目標是合理安排一個學期中所有的時段，模塊，教室還有教師，使之不互相沖突。由于教室，時間，教師等資源的有限供應性(limitedavailable),由此就意味著排課系統(tǒng)必須有一些必須滿足的制約(hardconstraints)，從而才能滿足特定的條件。在滿足以上排課的硬性要求要求，如教室的不沖突，教師的不沖突，課程的不沖突的目標以后，還應該盡一切可能滿足一些不一定必須滿足但最好滿足得要求(softconstraints)比如，將主課盡量的安排在上午等等。最后，在完成上面這些常規(guī)排課的要求上，本課題尚需結合上海交通大學網(wǎng)絡教育學院的實際情況，比如因為要通過網(wǎng)絡上課，對教室有各

23、種性質(zhì)的要求，最后能夠開發(fā)出能夠滿足本校網(wǎng)絡教育排課這一特殊要求的排課程序出來。1.4本課題研究應解決的主要問題排課問題數(shù)學模型的建立。排課問題中各種限制性制約(hardconstraints)條件如何滿足。排課問題中優(yōu)化條件的如何完成。由于排課是一個大規(guī)模排列組合的問題，所有得可能性非常大，所以如何對搜索的規(guī)模進行一定的縮小，也是一個非常重要的問題。第二章排課問題的理論介紹2.1排課問題的誕生最近的30年來，排課(timetabling)受到了越來越大的關注。各種關于排課的文獻，理論，方法也層出不窮，并且這種趨勢仍有繼續(xù)下去的跡象。各種關于排課的方法不斷更新，很大一部分原因是因為近年來學校教

24、學的方式在不斷的改變(比如上海交通大學現(xiàn)在就有了網(wǎng)絡教育學院)，而排課的方法也必須跟著學校教學方式的改變而不斷改變。每一個學年或是學期，大學的教務管理當局都必須設計出一張全新的課程表，而隨著大學教育規(guī)模的擴大和教學模式的復雜化，要排出一張理想的課程表成為了一件非常令人頭疼的任務。其中讓人倍感困惑的就是在排課中有一系列共享資源(比如教室，教師)的課件(modules)引起互相之間的矛盾或說是制約(Constraints)。以上海交通大學網(wǎng)絡學院為例，每一個課件(modules)通常有兩個學時或是三個學時構成。在排課的時候，若干互相制約的條件必須被考慮到。比如，不能有兩門課(course)在同一時

25、間，在同一教室上課?；蛘呓淌业娜萘勘壬线@門課的同學數(shù)量來的小?；蛘撸紤]的更遠一點，除了這些必須滿足的限制性條件外，還會有一些希望滿足的優(yōu)化條件，比如一些比較重要的課程，最好能安排在上午完成。為了便于管理，同一專業(yè)的英語課程最好能安排在同一時間完成。等等。還有就是，在某些的固定時段，某些課程的教師會有進修的任務或是開會的任務等等，不一而足。總之，也就是，在這些時候，這些教師不能上課，或者說，某些班級的某些課程就不能安排在一周中的這些特定時段。由于，排課問題是一個比較經(jīng)典的計算機難題，特別是大學的課程。而我們學校網(wǎng)絡學院，由于授課方式的更為靈活，教學手段和途徑和傳統(tǒng)的授課方式又有所不同，因此，要

26、做這樣一個排課的系統(tǒng)就更為困難。所以，迄今為止，絕大多數(shù)的課程表都由人手工完成，除了比較費時費力以外，還比較有可能出現(xiàn)一些前后互相矛盾的地方。為此，就算排課問題是一個比較困難的問題，針對我們學校網(wǎng)絡學院特殊情況的排課系統(tǒng)還是有開發(fā)的必要。通常來說，一張課程表的完成可以分為獨立的兩個步驟教學資源的分配，如上課時間，教室，課程等等信息的配置。具體來講，就是那個班級要上哪些課程，每個班級的人數(shù)，每門課具體的教師的安排，以及這些教師什么時候有空等。結合到網(wǎng)絡學院的特殊情況，還必須考慮到上課的教室有沒有一些特殊要求，是否允許幾個教室之間連線上課等等。一個可以接受的課程表的設計實現(xiàn)和完成，所謂可以接受的課

27、程表就是必須滿足先前定義各種限制性的條件，而且要比較好的滿足各種非強制性的期望條件(優(yōu)化條件)的課程表。目前為止來說，由計算機能做的只能是第二個部分的工作，而第一部分的工作通常要排課的老師輸入或決定。而且就長遠來說，第一部分的工作計算機估計永遠無法完全的由人來完成。2.2目前排課問題的幾個普遍的算法作為計算機領域的一個比較經(jīng)典的問題，排課算法的研究在國內(nèi)仍然不是非常普遍。有關排課算法的相關資料，國內(nèi)的材料十分的鮮見。雖然，市面上排課的軟件不少，但大多數(shù)卻是為中，小學開發(fā)的，難度也相對較低。不過，在國際上，有關排課算法的文章相對就較多，而且雖然迄今為止，沒有所謂最完美，或者說是最佳的排課算法，但

28、由于所做的研究相當多，所以已經(jīng)有了較為成熟和理想的排課算法。以下，就是目前為止，較為常見的幾種排課的算法或也可以稱之為技術。2.2.1SimulatedAnnealing這個算法名字SimulatedAnnealing1420的中文直譯應該是“模擬淬火”算法，不過我沒有看到過相關的中文資料，所以決定還是保留其英文的原名比較好。SimulatedAnnealing(SA)算法被廣泛應用于處理各種不同組合優(yōu)化問題，特別是在學校的排課計劃中。其基本的算法描述如下圖所示。上海交通大學學士論文網(wǎng)絡學院排課系統(tǒng)的實現(xiàn)1 Generate亂niiiiLi亂1sch.ed.uleSettheinitidbes

29、tscheduletf*=#.ConrpiitiEcostof:Com卩ultiiniLi亂1temperaLureT(j.5-SettheLem卩血亂1/01巳丫=Tq.6.Whiletfloperilriffri包notsaLisIiecLdo:(亂)RepeatMarkovduiiu昆唧山(M)Limes:Select亂rajidomneighborLothecurrenLschedule,(J匚A)-Set4(C)=C(J)-gIf(A(C)0downhillmove):Set=.J_CC0uphillmove):Choose亂randomnumberrtniilbrmlyfrom0,

30、1.LCr曠乂6圧thenseta=s.(b)Rjeduoe(orupdate)temperatureT.7-RjetumtheschecLulett*.Figure2.1:TheSimulatedAnnealingAlgorithmSA算法相對其他的一些全局優(yōu)化技術有優(yōu)點也有缺點。優(yōu)點之一是非常容易實現(xiàn),幾乎可以應用到任意一個組合優(yōu)化問題中去，能為大多數(shù)問題提供解決方案，并能與專家系統(tǒng)等啟發(fā)式方法相結合解決一系列復雜的問題。所以SA是一個比較可靠的技術，不過它的確仍有缺點。為了得到一個好的結果，升級的過程以及各種可調(diào)節(jié)變量的選取變的非常重要。而且，SA技術比較消耗時間，運行的時候速度比較慢。

31、最顯而易見的將排課問題(TimetablingProblem)映射到SimulatedAnnealingAlgorithm的構造如下state是一個包含如下集合的課表:oP:教師的集合oC:班級的集合oS:學生的集合oR:教室的集合oI:時間段的集合.cost或是E(P，C，S，R，I)定義如下：oE(P):是分配超過定額冷勺課同一位教師所引發(fā)沖突的代價，在計劃外增加一門或若干門課在教師的計劃中所引起的沖突oE(C):是將若干門課程安排在同一時間上課引發(fā)得不可避免沖突的成本oE(S):是將不屬于某些學生專業(yè)的課程安排的這些學生課表中去所引發(fā)的矛盾的成本oE(R):是將教室分配給不合適(指容量上

32、)班級而引起沖突的成本oE(I):是課時分配過多或過少所引起沖突的成本3.swap(move)是以下一個或多個班級在集合C中班級和班級叼再考慮到時間liRiRj段和I以及教室和所做的置換。一般來講，每一個步驟就是指這樣的一次班級的swapping。Figure2.2：Mapping2.2.2ConstraintLogicProgrammingConstraintLogicProgramming(CLP)217是由LogicProgramming(LP)結合限制系統(tǒng)中的限制操作而成。從而產(chǎn)生的一種新的語言結合了LP的優(yōu)點(declarativesemantics,non-determinism,

33、relationalform)與限制解決算法(constraint-solvingalgorithms)的高效率。由此，這一語言的優(yōu)勢保障用戶無需關心搜索的技術，限制的聲明是明白無誤的而且容易修改和擴展。在限制邏輯編程的范例中，有關限制滿足的問題可以被寫成一個Horn子句的形式，也就是各種限制性的條件被包含進子句中。而當程序運行的時候，各種限制相應產(chǎn)生被傳遞到限制解決機制中去。而這一機制應用“域獨立”(DomainIndependence)限制滿足技術，比如線性程序或者布爾判斷等來找到一個可行的解決方案。所以，這種方法仍舊是基于搜索的，不過可以有效的減少搜索范圍。限制邏輯編程非常適合排課問題。

34、因為它允許所有的公式將限制明示化。雖然，這個方法的表現(xiàn)會由于排課中的一些小改動而受到極大影響。不過經(jīng)改動多的排課公式仍能很好的滿足各種邏輯條件。而且由于排課問題本質(zhì)上是一個大規(guī)模的組合問題，所以有一個極為龐大的搜索范圍。因此，通過用CLP語言解決這個問題，可以將搜索的范圍壓縮到一個較小的基礎上并能很好的控制住搜索的時間。2.2.3GraphicColoringHeuristicsGraphicColoringHeuristics5這個算法的基本思想是這樣的，假設有S1-S10這是十名學生，他們所選的課程分變?yōu)閑l-e6中的若干門，如表2.1所示。StudentLectureS1el,e2,e3

35、,e6S2el,e2,e3,e5S3el,e2,e3,e5S4el,e2,e5S5e4S6e4,e5S7e2,e4S8e2,e4,e6S9e3,e4,e6S10e3,e4,e6Table2.1：ExampleofStudent-LectureData則我們可將他們之間的這種關系映射到下圖所示的關系中去。由于，學生S1會選擇el,e2,e3和e6這四門課，所以將ele2,ele3,ele6,e2e3,e2e6,e3e6連起。凡是，同一線段的兩端的兩門課程就不能在同一時間開設。Figure2.3：Graphcoloringforasimpletimetablingproblem不過，這個算法的用途

36、比較廣泛，但有一個比較大的缺點，就是特殊應用的限制(application-specificconstraints)不能很好的整合到這一方法中去。2.2.4GeneticAlgorithms遺傳算法GeneticAlgorithms或稱為進化算法EvolutionaryAlgorithms810引起了越來越多的關注。有關遺傳算法在排課領域中的應用最早出現(xiàn)于1990左右，由Colorni53提出，并隨之迅猛發(fā)展。在1997年8月舉行的國際自動排課會議(PATAT97)上，將近1/4的報告中或多或少的有進化算法的技術。而此前1995舉行的會議上，更有近1/3的報告是基于遺傳算法。這些數(shù)字表示進化算

37、法已經(jīng)成為一個用來處理一系列較大范圍的排課問題的成熟和成功的方法。遺傳算法的理論受啟發(fā)于達爾文的進化論理論。在遺傳算法中，一系列的解決方案(solutions)對于一個特定問題(chromosomes)的表現(xiàn)(performance)被評估(evaluated)和被排序(ordered)，然后選出其中表現(xiàn)較好的解決方案作為雙親(parents)，然后在將這些parents進行適當?shù)淖儺惒僮?mutation)或是將兩個parents進行交叉組合的操作(crossoveroperation)，由此由這些parents方案產(chǎn)生一個或多個子方案(children).然后這些新產(chǎn)生的方案再次被評估，周

38、而復始，直到有滿足條件的方案產(chǎn)生。2.2.5LinearProgrammingLinearProgramming21是對排課問題進行線性求解，通常并不能得到最佳的解。本文的課題的研究，雖然主體上仍舊是基于線性求解的基礎之上，但是在求解的時候，有優(yōu)先級方面的設置和一些改動，所以可以在線性求解的基礎上得到一個較佳的可接受的排課方案。2.3小結排課問題發(fā)展到現(xiàn)在的程度，仍舊沒有所謂做理想，最完美的排課方案。各種常見的排課方案，都各有優(yōu)點和缺點。用一種排課方案，不可能做到非常好地解決所有的排課問題。但是，一個特定的排課環(huán)境，有可能可以找到一個較理想的排課方案。而且，關于排課問題的研究，仍舊在不斷深入的

39、研究中。我們現(xiàn)在已經(jīng)可以用計算機自動排出一張可以接受得課表了，相信隨著我們的努力，我們將來排出的課表一定會越來越人性化。第三章排課問題的要求3.1對本排課系統(tǒng)的要求本課題誕生的原因是因為上海交通大學的網(wǎng)絡教育學院需要一套適合網(wǎng)絡學院多樣化教學任務的排課系統(tǒng)，而排課問題又是計算機領域中一個叫經(jīng)典的問題，正是因為有這樣一個契機，所以本文的研究課題就放在了排課問題得研究上，更確切的說，是網(wǎng)絡學院的排課問題的研究上。3.1目標本排課系統(tǒng)的目標是能夠根據(jù)網(wǎng)絡學院的教學執(zhí)行計劃、學生人數(shù)、學生選課地點、教師要求及教室等情況由計算機智能地排出符合要求的課程表。在排課過程中，本排課方案必須滿足所有的限制性條件

40、（hardconstraints）,也就是不會有沖突的情況出現(xiàn)，同時還會盡最大的努力完成盡可能多的優(yōu)化性條件（softconstraints）。3.2排課的基本情況3.2.1教學任務的劃分按照網(wǎng)絡學院的授課對象的不同，需要安排的課表有為網(wǎng)絡學院全日制本科學生所開的課程，有為專升本的學生所開的課程，還有為工程碩士所開的課程。而按照這些所開課程的不同，在教學時間的安排上可以分為全日制和業(yè)余制兩種。其中網(wǎng)絡學院的本科學生上課時間屬于全日制，而專升本的同學，以及工程碩士的同學的上課時間屬于業(yè)余制。3.2.2不同教學任務教學時間的安排全日制的教學任務安排在周一至周五的白天業(yè)余制的教學任務則安排在周一至周

41、五的晚上，以及周六和周日的全天（白天，晚上）全日制的上課時間為上午4節(jié)（最多）周一至周五下午4節(jié)（最多）周一至周五業(yè)余制的上課時間為上午5節(jié)（最多）周六和周日下午6節(jié)（最多）周六和周日晚上4節(jié)（最多）全周3.2.3排課中按照課程重要性的劃分按照課程的重要性劃分，可將全日制的課程劃分為主干課和非主干課之分，并且除此情況外，在重要性上無任何其他的劃分標準。同樣，業(yè)余制的課程也存在主干課和非主干課的區(qū)別，并且除此情況外，在重要性上無任何其他的劃分標準。3.2.4關于排課時間的概念因為每學期開學的時間（指日歷時間,年月日）無法確定。同時，在學期過程中的節(jié)假日換課或停課等情況，也非排課系統(tǒng)事先所能掌控，

42、所以在本排課系統(tǒng)中涉及的時間只有周數(shù)，第幾周之類的概念，以及某一周中第幾天的概念（周一到周七），沒有年月日的概念，所以本排課系統(tǒng)是一個基于周概念（weekly）的排課系統(tǒng)。與此類似的情況是，在排課中預先設定上課的小時和分鐘的概念，也不是非常的合理。因為，我們無法保證每天上午，下午還有晚上開始上課的時間，或是每節(jié)課的長短，甚至課間的休息時間在將來一定不會變化。所以，如果將小時和分鐘排進排課系統(tǒng)的算法中，難免在將來會造成某種程度上的困惑。另外的一個原因是，全日制和業(yè)余制的上課時間，無論是課時長短，還是課間休息的時間都完全不一樣。如果，在排課的核心算法思想中，將小時和分鐘的單位寫入，將無法同時處理全

43、日制和業(yè)余制這兩種不同的情況。所以，在本排課系統(tǒng)中每天的課程安排，只有課時的概念，單位是“節(jié)”，而沒有小時和分鐘的概念。在課表安排出來以后，小時和分鐘這類的時間概念可有排課老師對應上課的節(jié)數(shù)靈活的添置上去。3.2.5關于中同一門課程的持續(xù)時間的安排根據(jù)網(wǎng)絡學院排課教師的多年排課經(jīng)驗和要求，每門課的持續(xù)上課時間以2節(jié)課或者是3節(jié)課構成比較合理，極端情況才允許下可能有4節(jié)課，但不可能存在只上1節(jié)課或者連續(xù)上課超過4節(jié)課的情況出現(xiàn)。3.3排課過程中遇到的各種條件和限制排課中必須滿足的條件也就是排課中的限制性條件（hardconstraints）,如果不能完全滿足這些條件的話，這會引起各種各樣的沖突（

44、conflicts）,比如同一時間，會出現(xiàn)一個教師要在兩個不同的地點（教室）上課的情況，或者同一時間，同一個教室被安排給多個不同的班級上不同的課程。很明顯，以上的這些沖突在我們目前認知的三維空間是無法完成的，這樣排出來的課表也就是沒有意義或價值的同時，排課的時候還會有一些不是一定需要滿足，但是應該盡一切可能完成的條件（softconstraints）,。比如說，要把主干課程安排在上午上課。雖然，違反這一條件不會引起物理意義上的沖突，可以按照這樣的課表上課。但是，這樣排出的課表不會受到同學和老師的歡迎，是一張非常不科學的課表，所以也是沒有什么價值或意義的。在本課題的研究中，所遇到的必須滿足的條件

45、(hardconstraints)以及盡量滿足的條件(softconstraints)如下。3.3.1排課系統(tǒng)必須滿足的條件(hardconstraints)以下的條件是一些排課系統(tǒng)默認的，不需要排課教師人工協(xié)助設置的，理所當然應該必須滿足的條件。每個班級每個學期所指定要完成的課目都必須要被安排，也就是不能出現(xiàn)漏排一門課這類的情況。每個班級每個學期所要完成的課目只是被要求完成的課目，也就是不能出現(xiàn)多排一門課這類的情況。每門課程教學所需的課時數(shù)必須要被滿足，也就是每個班級每周的上課課時*上課的周數(shù)=每門課程的教學課時數(shù)。其中要注意的是，國慶假期等放假，停課情況不在排課系統(tǒng)的考慮范圍之內(nèi)。同一時間

46、教師的安排不能有沖突，也就是同一個教師不能同一時間在兩個地點(教室)上課，也不可以在同一時間，同一地點，教授兩門不同的課程。同一時間教室的安排不能有沖突，也就是同一時間同一教室，不能安排兩批不同的班級學不同的課程。全日制的教學任務能且只能安排在周一至周五的白天，這里的白天是指上午的4節(jié)課和下午的4節(jié)課。業(yè)余制的教學任務能且只能安排在周一至周五的晚上(4節(jié)課)，以及周六和周日全天(上午的4節(jié)課和下午的4節(jié)課)。以下的條件由排課的老師人工協(xié)助給出，可以認為是排課中各種所需的條件變量。每學期課程課時的安排每學期每門課程的課時有可能會是36學時，48學時或者72學時等等，這些信息需要排課的老師給出。同

47、時，每門課程的開始時間，第幾周開始，(因為并不是所有的課程都是第一周開始，由的課程會在期中開始)，這些信息均需要由排課的老師給出。哪些課程是主干課，哪些課程不是主干課,這些信息同樣由排課老師給出，因為計算機無法通過課程的名字就知道哪些課程更為主干。任課老師與課程之間的聯(lián)系，也即哪門課由哪位老師上，甚至同一專業(yè)，同一年級，相同的課程，如英語課，某個班級的英語課由某位老師上課，都由排課的老師指定，不存在任意的情況。某些任課老師因為要進修，開會的關系，有些時間不能來上課，也即由這些任教某些課程只能安排在一周的一些指定時段中，以上信息也需要由排課的老師給出。某些課程必須在有特定功能的教室上課，如多媒體

48、教室，視聽教室，機房等。每門課程所需教室功能的信息由排課老師給出。默認情況下，任何課程都需要在多媒體教室完成。一同上課的班級由排課老師給定。教室的容量不能小于上課的學生數(shù)。特別需要注意的是，對于非主干課程，可以在多個多媒體教室聯(lián)網(wǎng)上課。而主干課程必須在同一個教室完成。而如果上的是選修課的話，因為上選修課的人數(shù)和可能選修這門課程的班級相加的人數(shù)不一定相同，所以排課的老師還需要給出實際選上這門課的同學的人數(shù)。幾個班級合并上課的問題。幾個不同的班級，由同一個教師上的相同課程，這幾個班級是否可以或必須合并在一起上(即同一時間，同一地點)的問題，由排課老師做出決定。由于業(yè)余制有校外的教室，當主教室排課時

49、間與校外教室使用有沖突的時候，能靈活的改變主教室的排課時間。(也就是能告知修改過的課程表是否有沖突)3.3.2排課系統(tǒng)會盡量爭取滿足的條件(softconstraints)主干課盡量安排在上午完成。同一專業(yè)的英語課盡量安排在同一時間位置一起上，如同一專業(yè)有4個班級，則最好前兩節(jié)課1，2班并上，后兩節(jié)課3，4班并上。同一門課程在一周中的相隔時間希望至少相隔兩天。盡量優(yōu)先使用網(wǎng)絡學院的教室?！按髮W英語”課盡量安排在視聽教室上。體育課盡量安排在3，4節(jié)課上。周三的下午盡量不排課。3.4小結以上的各種限制性條件，不論是必須完成的限制性條件(hardconstraints)，還是應盡量爭取滿足的條件(s

50、oftconstraints)，都是在與網(wǎng)絡學院的排課教師多次反復的磋商后得到的結果。而需要排課老師協(xié)助完成的那些條件變量，則是在開發(fā)這個排課系統(tǒng)中不斷遇到問題的解決。比如，本來“幾個班級合并上課的問題。幾個不同的班級，由同一個教師上的相同課程，這幾個班級是否可以或必須合并在一起上(即同一時間，同一地點)的問題，由排課老師做出決定?！边@一點我并沒有想到，但是在開發(fā)的時候，就發(fā)現(xiàn)做不下去了，因為在這種兩可的情況下，會讓計算機很難“做人”的，所以這個問題只能交由排課的老師完成。而且，在上面的所有條件中，可以看出，所謂的必須完成的限制性條件(hardconstraints)是絕大多數(shù)排課系統(tǒng)都要完成

51、的。而在應盡量爭取滿足的條件(softconstraints)部分，則每個學校和學院的差別就很大了。第四章本課題所做排課系統(tǒng)的實現(xiàn)4.1本排課系統(tǒng)的排課過程如圖4.1所示，排課的時候首先由排課老師從教務處取得詳細的課程設置，包括所有專業(yè)的課程目錄，課時數(shù)，課程開始的時間，那些是主干課，哪些不是，每周上課的次數(shù)，對該課程的具體要求等等，以及可以用來上課的教室的信息。然后，排課老師向任課的老師發(fā)出請求時間表，也就是詢問任課老師什么時候可以來上課，什么時候沒空不能來上課。最后，如果有選修課的話，排課的老師還要統(tǒng)計每門選修課的實際人數(shù)。等以上準備工作都完成以后，排課的老師則將以上的規(guī)則整理，輸入排課系

52、統(tǒng)。同時，加上各種排課規(guī)則優(yōu)先順序和一部分限制性條件。交由排課系統(tǒng)來嘗試排課。由于，資源的有限性和限制性條件的作用，交由排課系統(tǒng)的信息有可能存在互相矛盾的地方，也就是沒有辦法排出一張課表。如果遇到這種情況，則需要排課的老師與任課的老師相互協(xié)商，或是在各門課程中相互協(xié)商，以避開矛盾或沖突。如果，最后協(xié)商無效，則只能由排課老師強制調(diào)節(jié)沖突，也就是取消或削弱一些原來強制完成的限制性條件。有的問題協(xié)商也不一定能解決，比如資源的明顯不夠。比如，教師人數(shù)的不夠，還有就是教室數(shù)量的不足，大小不夠等問題。遇到這些問題，只能由排課的老師向學校再去申請新的教學資源，例如，要求增加更多的老師和教室等等。否則的話，排

53、課系統(tǒng)肯定是無能為力的。等所有的條件可以滿足后，排課系統(tǒng)自動排列出符合所有限制性條件(hardconstrains)和最大可能滿足優(yōu)化條件(softconstraints)的課程表。然后，再進行打印，就可以得到網(wǎng)絡學院新學期的所有班級的課表了。4.2本排課系統(tǒng)的實現(xiàn)原理4.2.1開發(fā)工具和前期準備本課題所做排課系統(tǒng)的核心開發(fā)是用標準C語言完成的。界面的完成是用到了微軟的MFC。用C語言做核心的原因一個是因為排課系統(tǒng)是一個NP復雜度的問題，對時間的開銷很大。C語言的效率較高，可以有一個較快的速度。另外一個比較重要的原因是，開發(fā)排課系統(tǒng)前，由于缺少相關的資料，我并沒有百分百的信心可以做出一個排課系

54、統(tǒng)。在這樣的情況下，我希望能夠先用較熟悉的C語言做出一個實驗的版本出來，主要是先看一看我的想法和算法是否正確。否則的話，關鍵問題錯誤，其他的問題就根本談不上了。4.2.2排課系統(tǒng)的基本思路和算法排課的幾個核心函數(shù)Input函數(shù)Comp函數(shù)Ready函數(shù)Calc函數(shù)Add函數(shù)Del函數(shù)排課的流程和各函數(shù)的作用排課的第一步，是由排課的老師在視窗界面中輸入排課的所需的各項信息。包括有教室的信息，教師的信息，課程的信息，班級的信息，還有各種優(yōu)化性條件。等排課所需的所有信息輸入完畢后，界面的處理函數(shù)將以上信息打包成規(guī)范化的形式，寫入輸入文件lecture.in。Input函數(shù)

55、的介紹Input函數(shù)將處理是lecture.in的信息。在Input函數(shù)中，要處理的事情主要有三件。首先是要生成一個教師的表格和一個教室的表格。這些表格用來紀錄在一周中的時間內(nèi)，教師或是教室在哪些時候有空。Input函數(shù)根據(jù)輸入的信息，需要將老師不能上課的時間以及上海交通大學學士論文網(wǎng)絡學院排課系統(tǒng)的實現(xiàn)2 教室不能開放的時間填出來。Input中做的第二件事是“減數(shù)分裂”。所謂的“減數(shù)分裂”是這樣的，某些課程在一周的時間中，要上兩次或是三次。這樣的直接排課的話，會比較麻煩。通過減數(shù)分裂，將這些課拆成完全相同性質(zhì)的兩門課或是三門課（術語應該是Item）。這樣在減數(shù)分裂以后，在排課的時候，所有的“

56、課程”都是一周只上一次，相對來說考慮起來就比較容易的。Input中做的另外一件比較重要的事情是周數(shù)的合并。其實做不做周數(shù)的合并，并不會影響算法的正確與否。做周數(shù)合并只是為了提高算法的運行效率。因為，在周數(shù)合并之前，比如說，一個學期有18周，則在排課的時候需要考慮這18周的情況。如果一個教室第一周是有空的，那么它第二周是否有空哪，第三周又如何哪？以此類推，要考慮總共18周的情況。可是，如果這18周的情況完全相同的話，我們就可以將這18周合并起來，就當成一周的情況來考慮。這樣，算法執(zhí)行的速度可以至少提高18倍。當然周數(shù)的合并也是有一定條件的。如圖4.3所示的課程甲和課程乙的情況，課程甲的時間跨度就

57、可以從第1周到第9周壓縮為“1周”考慮，而課程乙的時間跨度就可以從第10周到第18周壓縮為第“2周”。因為可以證明，當一門課程結束的時候，另一門課程還沒有開始，則這兩門課程無論怎么安排，教室的安排或是教師的安排，都不會影響到另外一門課。諜程甲屮.課程乙2101敵時間軸屮Figure4.3:周數(shù)合并的情況一而如圖4.4的情況，課程甲和課程乙有一段沖突的時間。則課程甲和課程乙在周數(shù)上就無法合并了。因為，課程甲在第一周的時候，某個時候某個教室空著，并不代表在第十周這個時候這個教室仍舊空著。因為課程乙有可能在第十周的這個時候會用這個教室。所以，到第十周的時候，一個很嚴重的沖突就發(fā)生了，兩門課程在同一時

58、間用了同一個教室。這是不能允許的錯誤。所以，很顯然，在這種情況下，課程甲和課程乙的周數(shù)都無法壓縮或說是將周數(shù)合并。二匚課程甲屮課程乙屮21血1禺時間軸aFigure4.4:周數(shù)合并的情況二另外一種情況是像上圖所示，課程甲的長度整個跨過課程乙。則這個時候仍舊可以進行周數(shù)的合并。因為在課程乙雖然先結束，但對課程甲不造成任何影響。所以，我們可以假設課程乙的長度和課程甲相當。然后，進行周數(shù)的壓縮。當然，在課程乙實際結束后，課程乙曾經(jīng)占用的資源會釋放出來，但幸運的是，多出來的資源不會造成任何的沖突。諜程甲d諜程乙d210+J爛時間軸小Figure4.5:周數(shù)合并的情況三在Input函數(shù)即將完成的時候，最

59、后調(diào)用了qsort函數(shù)。qsort函數(shù)是C語言的標準排序函數(shù)，排序的標準由Comp函數(shù)參數(shù)決定。所以，Comp函數(shù)的內(nèi)容其實是本排課系統(tǒng)的默認優(yōu)先集的設定。在Comp函數(shù)中，總共有5個判斷函數(shù)。第一個判斷函數(shù)的作用是將主干課排在前面。因為，在課程輸入的時候，每門課程都有一定的屬性，像主干課，非主干課，英語課，非英語課，等等。所以，這一標準就是將課程中有主干課屬性的放在前面，當都是主干課在比較時，就將有英語課屬性的放在前面等等。第二個判斷函數(shù)的作用是將課時多的課程放在前面。所謂課時多的課，就是每次上課要連續(xù)上3節(jié)或是4節(jié)的課程，因為我發(fā)現(xiàn)這樣的課程往往比較難排。所以，有必要將他們提到比較前面一點

60、，先進行安排。第三個判斷函數(shù)的作用，是將選擇這門課班級人數(shù)多的排在前面。因為，上課的人多，意味著相應的教室要比較大，這也是一個相對來說較苛刻的條件，所以有必要先將他們安排好。第三，第四個函數(shù)做的事情是這樣的。因為，我們先前將一周內(nèi)要上幾次的課程都拆分開來了，認為他們是幾門不同的“課程”。但是，很明顯，他們的課程屬性完全一樣，也就是他們的優(yōu)先級應該完全一樣。在這種情況下，我希望在排序的時候，這些有原來一門課分裂出來的課程都能在隊列中緊鄰的排列。這樣我就有必要判斷哪些“課程”是由原先同一門課程分裂出來的，哪些不是。所以我要做以下兩個判斷。一課程的名稱是否一樣。二上課的班級是否一樣。如果，以上兩點完