1、畢業設計(論文)課 題 名 稱 課表編排系統設計與實現 畢業設計（論文）原創性聲明和使用授權說明原創性聲明本人鄭重承諾：所呈交的畢業設計（論文），是我個人在指導教師的指導下進行的研究工作及取得的成果。盡我所知，除文中特別加以標注和致謝的地方外，不包含其他人或組織已經發表或公布過的研究成果，也不包含我為獲得 及其它教育機構的學位或學歷而使用過的材料。對本研究提供過幫助和做出過貢獻的個人或集體，均已在文中作了明確的說明并表示了謝意。作 者 簽 名： 日 期： 指導教師簽名： 日期： 使用授權說明本人完全了解 大學關于收集、保存、使用畢業設計（論文）的規定，即：按照學校要求提交畢業設計（論文）的印刷

2、本和電子版本；學校有權保存畢業設計（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務；學校可以采用影印、縮印、數字化或其它復制手段保存論文；在不以贏利為目的前提下，學校可以公布論文的部分或全部內容。作者簽名： 日 期： 學位論文原創性聲明本人鄭重聲明：所呈交的論文是本人在導師的指導下獨立進行研究所取得的研究成果。除了文中特別加以標注引用的內容外，本論文不包含任何其他個人或集體已經發表或撰寫的成果作品。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標明。本人完全意識到本聲明的法律后果由本人承擔。作者簽名： 日期： 年 月 日學位論文版權使用授權書本學位論文作者完全了解學校有關保留、使

3、用學位論文的規定，同意學校保留并向國家有關部門或機構送交論文的復印件和電子版，允許論文被查閱和借閱。本人授權 大學可以將本學位論文的全部或部分內容編入有關數據庫進行檢索，可以采用影印、縮印或掃描等復制手段保存和匯編本學位論文。涉密論文按學校規定處理。作者簽名：日期： 年 月 日導師簽名： 日期： 年 月 日指導教師評閱書指導教師評價：一、撰寫（設計）過程1、學生在論文（設計）過程中的治學態度、工作精神 優 良 中 及格 不及格2、學生掌握專業知識、技能的扎實程度 優 良 中 及格 不及格3、學生綜合運用所學知識和專業技能分析和解決問題的能力 優 良 中 及格 不及格4、研究方法的科學性；技術線

4、路的可行性；設計方案的合理性 優 良 中 及格 不及格5、完成畢業論文（設計）期間的出勤情況 優 良 中 及格 不及格二、論文（設計）質量1、論文（設計）的整體結構是否符合撰寫規范？ 優 良 中 及格 不及格2、是否完成指定的論文（設計）任務（包括裝訂及附件）？ 優 良 中 及格 不及格三、論文（設計）水平1、論文（設計）的理論意義或對解決實際問題的指導意義 優 良 中 及格 不及格2、論文的觀念是否有新意？設計是否有創意？ 優 良 中 及格 不及格3、論文（設計說明書）所體現的整體水平 優 良 中 及格 不及格建議成績： 優 良 中 及格 不及格（在所選等級前的內畫“”）指導教師： （簽名）

5、 單位： （蓋章）年 月 日評閱教師評閱書評閱教師評價：一、論文（設計）質量1、論文（設計）的整體結構是否符合撰寫規范？ 優 良 中 及格 不及格2、是否完成指定的論文（設計）任務（包括裝訂及附件）？ 優 良 中 及格 不及格二、論文（設計）水平1、論文（設計）的理論意義或對解決實際問題的指導意義 優 良 中 及格 不及格2、論文的觀念是否有新意？設計是否有創意？ 優 良 中 及格 不及格3、論文（設計說明書）所體現的整體水平 優 良 中 及格 不及格建議成績： 優 良 中 及格 不及格（在所選等級前的內畫“”）評閱教師： （簽名） 單位： （蓋章）年 月 日教研室（或答辯小組）及教學系意見教

6、研室（或答辯小組）評價：一、答辯過程1、畢業論文（設計）的基本要點和見解的敘述情況 優 良 中 及格 不及格2、對答辯問題的反應、理解、表達情況 優 良 中 及格 不及格3、學生答辯過程中的精神狀態 優 良 中 及格 不及格二、論文（設計）質量1、論文（設計）的整體結構是否符合撰寫規范？ 優 良 中 及格 不及格2、是否完成指定的論文（設計）任務（包括裝訂及附件）？ 優 良 中 及格 不及格三、論文（設計）水平1、論文（設計）的理論意義或對解決實際問題的指導意義 優 良 中 及格 不及格2、論文的觀念是否有新意？設計是否有創意？ 優 良 中 及格 不及格3、論文（設計說明書）所體現的整體水平

7、優 良 中 及格 不及格評定成績： 優 良 中 及格 不及格（在所選等級前的內畫“”）教研室主任（或答辯小組組長）： （簽名）年 月 日教學系意見：系主任： （簽名）年 月 日摘要近年來隨著大學的擴招和規模的擴大，排課問題已成為一個非常棘手的問題，在教室資源有限的前提下課程編排顯得更加繁重，同時課程的編排也更成為教學管理工作的關鍵，在一定程度和深度上影響著學生的培養與教學質量的提高。利用計算機進行自動排課，不但能使教務人員從繁雜的排課任務中解脫出來，提高教務管理工作效率，而且能改善教學管理質量，合理、高效地利用有限的教學資源，使學校的各種教學活動、教學管理及其它相關的工作能夠有序、規范地進行，

8、維持正常的教學秩序，同時對推動教務管理的信息化起到非常重要的作用。 排課問題是一個有約束的、多目標的、難解的組合優化問題，是屬于np-完全問題。研究者提出了多種排課算法，例如模擬退火、列表尋優搜索、約束滿意等算法，而遺傳算法是很有效的求解最優解的算法之一。 遺傳算法通過交叉、變異、選擇三種遺傳算子來實現遺傳和變異的功能,并采用適應度函數保證排課結果趨于最優，對現有教學資源進行科學合理的安排，在實踐中具有一定的應用價值。針對之前研究者未解決的運行時間太長問題，本文提出了一套基于二維編碼的改進的編碼方法和教室位置填充方法，精簡了染色體信息量而大大縮短了系統的運行時間。此外，在系統設計中，運用了基于

9、容器的容器編程技術，實現了不定數據量的便捷處理。關鍵詞 遺傳算法； 排課問題； 適應度函數abstractabstract in recent years, with the university expansion and expansion of the scale.timetabling has become a very difficult problem. limited resources in the classroom context, curriculum has become more onerous. the courses become the key to teach

10、ing management at the same time. it affects students in developing and improving the quality of teaching to some extent. arranging automatically by computer, not only to academic staff from the cumbersome task of freeing arranging, improve efficiency of educational administration, but also to improv

11、e the quality of teaching management. rational and efficient use of limited teaching resources, making variety of teaching activities, teaching management and other related work orderly and standardized manner, keeping the normal teaching order, at the same time promoting the academic management of

12、information technology play a very important role.timetabling problem is a constrained, multi-objective, intractable combinatorial optimization problems, it belongs to np-complete problems. researchers have proposed many other timetabling problem, such as simulated annealing, list of search optimiza

13、tion, constraint satisfaction and so on. but genetic algorithm is very effective algorithm for solving the optimal solution .ga carry out genetic and functional variation through crossover, mutation and selection of three genetic operators. and adopt fitness function ensure arranging results tend to

14、 the best. according to the problem that running time is too long,which the res-earchers didnt resolved well before,this paper puts forward a improved method based on two-dimensional coding and the classroom filled method, simplifying the chromosome information and greatly shortening the syetem oper

15、ation time. in addition, in the system design, we use the programming method of container based on container , realizing the convenient and fast processing of uncertain quantity data. key words curriculum arrangement; genetic algorithm; priority strategy目錄中文摘要 . i英文摘要 . ii1前言 . 12排課問題描述 . 2 2.1 問題需求

16、分析 . 2 2.2 數據需求分析 2.2.1時間問題 2.2.2 教師和課程問題 2.2.3教室的問題 2.3功能需求分析 2.3.1院管理模塊 2.3.2自動排課模塊 2.4排課過程的約束條件3自動排課系統的設計. 2 3.1遺傳算法的思想 3.2構建基因編碼和染色體 3.2.1混合式編碼 3.2.2染色體的表示 3.2.3 初始化種群4數據庫問題 .3 4.1 數據庫設計 4.1.1 概念模型設計 4.1.2 邏輯模型設計 4.1.3 數據庫的物理設計 4.2 期望結果 4.2.1構造適應度函數 4.3功能模塊的設計 4.3.1 登錄模塊 4.3.2主界面模塊 4.3.3學院管理模塊 4

17、.3.4查詢模塊 4.3.5 排課模塊5沖突問題解決. 46 結果評估 . 57結束語 . 6致敬詞 . 7參考文獻 . 8附錄 . 81 前言 隨著高校招生逐年擴張，大學課程向著廣度和深度發展，高校的教師、教室等一些資源越發顯得緊張，不管是在時間還是效率方面，用人工排課已不能夠解決現有的問題。排課是高校日常教學工作和其他活動的基礎，是教師和學生正常科學工作學習的依據。所以計算法自動排課已成為一個重要的研究課題1。國內學者在自動排課系統方面曾做過一些研究，如用到到退火算法、回溯算法、遺傳算法，但運行結果尚有待改進的地方，排課效果不盡人意5。我們認為，問題不盡在數學建模上，還與問題的處理方式有關

18、。將遺傳算法應用于排課問題中，首先，初始化課表種群，其次，檢測初試種群中的沖突，然后，對種群做選擇，雜交，突變操作，一直迭代到具體指定的代數，最后就會得到較優解。文1中提到編碼時染色體上基因片存儲信息大小為11字節，而本文的編碼方式一個基因片只用了6字節，輕裝運行，經試驗得出，速度更快。還有,文1介紹把教室與時間等信息共同處理的思路，這可能會產生空間上的沖突，而本文提出將教室分離出以單獨處理，就完全解決了空間上的沖突問題。本文根據高校開課的具體情況，采用優化的編碼方案，滿足排課過程中的一些硬性和軟性約束因素，利用遺傳算法對課表進行了優化，從而得到了最終的無沖突、更人性的排課方案。2 排課問題描

19、述2.1 問題需求分析 排課工作是一項十分繁重而復雜的工作，就以一般高校而言，它涉及到幾千多門課程進行合理的組織安排，而所使用的教室資源卻在學生規模每年都在增加的趨勢下越發顯得緊張了。排課的整個過程中充滿了矛盾運動，其中包括上課班級、所開課程、任課教師、上課時間、上課地點這5個方面在排列組合中發生的沖突和矛盾現象。課程門類多、班級多、教師少、教室少、教師連續上課的要求、班級連續上課的時間合理安排是排課時發生沖突和矛盾的主要因素，而班級多、教室少則是矛盾的重要方面。課程表則是解決這些矛盾的舞臺，是提高教學管理水平、組織師生進行有序教學的規范之一，對有效地提高教育教學質量有重要作用。如果課程表編排

20、得不合理、不科學，將影響課堂教學的效率和教學的整體效果。要想編排好學校的課程表，需要綜合考慮學校的教師、教室、學生、班級、時間等多方面因素，反復調整，避免沖突。 一張正確的課表應至少滿足以下硬約束條件：3 (1) 一個教師或者一個班級或者一個教室在同一時間段內只能安排一門課程； (2) 分配的教室可容納人數應該大于學生數。 除了上述的硬性約束，還有些軟約束，這些軟約束有助于使得課表更加合理，更加人性化。這些軟約束條件可能是4： (1) 盡量在早上安排必修課，而下午安排選修課，晚上盡量不排課； (2) 盡可能滿足個別教師的特殊上課時間要求； (3) 一門課盡量分散在一個星期中，即某天上完某一門課

21、后，要隔一天以上再上這門課，以使教師有充足的時間備課和批改作業，而學生也有足夠的時間復習消化； (4) 一個教師的課不能排滿一整天； (5) 學生課表中的上課時間不能過分集中，應避免一天課程很滿而另一天卻一整天沒課的情況。這些軟約束條件各院校有所不同，在我們的研究中，旨在我們定義的約束范圍內給出一個遺傳算法的解決方法，并對其進行優化操作。圖1排課流程圖2.2 數據需求分析排課涉及的相關數據主要包括:時間、班級、課程、教室（空間）、教師等5個要素。開始算法設計的基礎是對這些數據之間的問題的透徹分析和適當的處理。2.2.1時間問題在本文中考慮的是周課表，通過對全國部分高校做的調查，綜合分析了其中大

22、部分高校的教學特點，我們在此做出了一個較大眾化的且較合理的時間劃分模式。設定周一至周五，共五天上課，一天有十節課，上課方式都為一大節包括2個相鄰的小節，不能在上、下午之間跨時段。把每天用于上課的時間劃分為5個時間片，根據學院開課的實際情況，一般每學時是45分鐘，為1小節課，每2小節課合為一大節課，故把每2小節課時間定為一個時間片，一天劃分為5個時間片: (1)上午1, 2節課8:10-9:50; (2)上午3, 4節課10:10-11:50; (3)下午5, 6節課2: 30-4:10; (4)下午7, 8節課4:20-5:50; (5)晚上9, 10節課7:30-9:10; 這樣，每周5天涉

23、及25個時間片。用tl, t2,.,t25表示，其中ti, t2, t3, t4, t5為星期一的5個時間片，依次類推。則排課問題類似于填充55的周時間片安排表。 表2-1周時間片分布表table2-1 the management table of the week time slip 周一周二周三周四周五t1t6t11t16t21t2t7t12t17t22t3t8t13t18t23t4t9t14t19t24t5t10t15t20t25根據時間片編號，可進一步轉化為125的表格。全校有n個教學班級，則周課表為:以25個時間片為列，形成一維的時間序列，每個班級為行組成的一個二維數據表。我們在此

24、系統的排課都是按一個大節開設的，符合按25個時間片劃分的設計，但確有少量的課程的周學時數為單數，如“3學時”或“5學時”，在此仍按“4學時”或“6學時”進行編排，雖然這會浪費一小節課程。2.2.2 教師和課程問題每個課程都有自己的編號、名稱以及開課學院。每個課程都要有授課教師。每門課程都有指定的教室類型。如普通教室、語音室、操場、實驗室或機房等等。每門課程都有授課計劃，包括起始周和截止周以及周學時安排。在處理課程與教師時要注意以下幾個問題:(1)“授一班多門課”問題:同一教師可以只上一門課，也可上多門課，如果同一教師在同一個班級教授多門課程，那么把課程和教師作同一變量考慮就會引起課程的混亂，此

25、問題須分情況解決，我們將在系統設計中，學院安排開課任務時解決此問題。 (2)“一師多班”沖突問題:一位教師可能只給一個班講課，也可能同時給多個班級講課，也就是說同一教師可以在多個班出現，這樣可能會出現同一時間，同一教師在多個班級上課的沖突，在編排課程表時此類沖突必須解決。(3)“多學時”問題:對于有些課程既可能只上一次，既2學時課程，而有些課程可能上多次，如4學時、6學時等，多學時的課程如何處理也是在編排課程表時必須解決的問題。(4)“固定課”問題:有的教師因為某些原因需要安排特定的教學時一段，如教室受到其他課程的影響，或者某學院部門領導，因工作性質關系，須指定安排上課時間為“星期五的第5、6

26、節”，這樣的要求在編排課程表時必須滿足，即“固定時段”問題。(5)“特殊課”問題：像體育課，要跟硬件設施有關，故要妥善處理。2.2.3教室的問題如今的大學都有很多的教學樓，校園面積也很大，宿舍與教學樓，教學樓與教學樓之間的距離可能會比較大，如果安排不佳的話，會導致學生上課時要跑動很遠距離，浪費不必要的時間。本文在地理位置上是學校統一規劃，進而綜合解決位置問題，學校要規劃好各個學院的學生在哪些教學樓里就近上課，而這樣做的目的就是為了減少學生和教師的走動范圍。至于如何去確定一個教室，例如5-0122，就表示5教學樓，1樓22號教室。每個教室在同一時間內只能接納一門課程的授課，并且教室容量應該大于等

27、于上課的人數。當上課的人數遠遠小于教室容量時，這種情況也往往不合適的。2.3功能需求分析根據業務分析和數據分析，可得出排課系統主要完成以下幾個功能:2.3.1院管理模塊這一模塊首先是每個學院從教學計劃中安排自己學院的開課任務書，具體就是對本學院課程和教師的安排。這一模塊由學院排課工作人員來設置，如設置學年學期就是設置即將排課的學年學期，合并本學院的兩個班級組成一個新班一塊上一門公共課，設置一門課程則為上課周數、每周上課節次、有哪位老師講授等等信息; 這個模塊很好的解決了每個學院不同的特殊情況，以教師為重點，學院可以隨意調整。另一個功能，學院在這塊可以查詢本學院的課表，還有學院內班級的課表。還有

28、對已排好的課程做一些調整操作。2.3.2自動排課模塊 這一模塊主要完成課程上課時間、上課地點的安排。它的實現運用了遺傳算法中的選擇、交叉、變異等操作，對算法得出的結果中最好的一個個體保留，就是要求的結果，雖然不是最完美符合的，但是它的適應度值已經完全可以符合學校教學所要求的了。然后，對這個（班級，教師，課程，時間）記錄做變換，讓位置表去填充它，當然是按條件填充，就可以完成整個排課的大部分工作了，從而得到課表。此圖描述了功能模塊圖，如圖2示：圖2 功能模塊圖chart 2 the function model chart 2.4排課過程的約束條件 排課是將教師與學生在時間和空間上根據不同的約束條

29、件進行排列組合，在此同時也要安排課程，以使教學正常進行。在本文約束條件主要為避免沖突，所謂沖突，它所包含的內容很廣泛，幾乎發生在所有兩個或多個排課涉及因素之間。避免沖突也是排課問題中要解決的核心問題。只有在滿足全部約束條件和避免所有沖突的基礎上，才能保證整個教學計劃合理正常進行。而對教師、教室、學生及時間等幾部分資源進行最優化組合配置，才能保證充分發揮各資源的優勢和提高教學質量。在本文中，我們把排課過程中的約束條件分為三類:基本硬約束、硬約束和軟約束。其中基本硬約束是指教師、學生和教室在時空概念上發生了不可能發生的事情，既是時間，空間，人之間的矛盾，它是排課過程中最基本的約束條件，也是眾多排課

30、模型中都要涉及的約束條件；硬約束是根據學校的實際情況，排課時必須遵循的原則，否則將會導致排課結果無意義，所以要因地制宜；軟約束是指排課過程中滿足更佳但不滿足又無妨的約束條件，這些條件的目的就是使課表更加人性化，每個排課都是要突出解決軟約束這個問題的，違背這些約束就與實際情況相悖。所以，可知在三類約束條件之中，前兩者是衡量排課方案是否切實可行的基本標準，軟約束是衡量排課方案是否人性化的標準，通常判別一個排課方案的優劣標準有多個。可以把排課過程常見的約束條件分類羅列如下表2-2所示，這些約束條件也比較符合排課過程的實際情況。表2-2 約束表table 2-2 constraint table基本硬

31、約束b1同一時間，同一班級不能上兩門不同的課程b2同一時間，同一個教師不能上兩門不同的課程b3同一個時間，同一個教室不能上兩門不同的課程硬約束h1課程的學時在每周要均勻化h2滿足每門課的特定教學資源h3教室足夠大，能夠容納學生h4某些課程要特定安排，如某些教師的課程要固定h5教師學生上課不能用于在路途上的奔波h6體育課盡量安排在下午軟約束s1課程的分布要做到離散化s2一周有些時段處于最佳利于學習時間s3盡量不讓老師連著上課s4班級相鄰上課地點盡量近些3 自動排課系統的設計3.1遺傳算法的思想在本課題中，遺傳算法解決的問題只是求出班級+課程+教師+時間的記錄集，得到比較優的一個解，然后再去按條件

32、用教室去填充這個記錄集，就形成了可行可用的課表。這塊的設計在整個系統是最重要的，效率的高低，課表的優劣都由本模塊確定。整個系統的流程分為以下幾個主要的過程:(1)初始種群的產生:首先基因的編碼，根據制定的編碼方案，對每條染色體進行初始化，其次一條條染色體組成一個個體，既是形成一個二維表（可稱為課表，但是適應度值不高）。(1)沖突檢測和消除:初始化種群后，先對其進行各類沖突的檢測，如存在沖突則消除它，而且在每次產生下一代后都要進行沖突檢測。(2)計算出每個個體的適應度函數值，以進行優勝劣汰。(3)遺傳操作:包括選擇算子、交叉算子和變異算子，產生子代，逐漸優化。(4)迭代第四步，直到進化停止，就是

33、generation=終止代數n。(5)班級+課程+教師+時間的記錄集的產生。圖3 遺傳算法流程圖3.2構建基因編碼和染色體實施遺傳算法的第1步，就是把與求解目標相關的實際參數進行基因編碼，這是算法的關鍵與難點。3.2.1混合式編碼構造合適的基因結構是遺傳算法能否順利實現的關鍵，設定混合式的教師編碼作為本系統遺傳算法的“基因”。二進制基因構成規則為:是否固定*教師編號號*課程編號*課程性質分別對應的寬為1+15+16+16共6b。下面我們給了很清晰的解釋：圖4 編碼結構圖下面我們對每個字段給予解釋：a.是否固定有些教師的課程是固定在某個時間段的，所以在排課過程中，判斷第一位就可以得知可否移動此

34、基因片。這也反應了排課要人性化，畢竟有些教師有特殊的要求，例如，年齡、事物等等。b.教師編號我們給了15bit去表示教師，15bit能表示215個數，足矣滿足任何一所高校的教師編號，所以，在數據庫里，教師表里教師編號的數據項要為短整型。c.課程編號唯一確定一門課程，216個數，也足以表示一個學校的課程。d.課程性質 為了解決“特定資源”沖突問題，可在教師編碼中加上2b表示該教師所教授的課程的性質。每一門課程都有其各自不同的特點，比如上機課需要在機房上課，英語口語需要在語音室上課，體育課需要在操場上課，為此我們規定：把16bits分開，前后8bits各有不同的意思； 圖5比特信息圖在此我們把課程

35、分為專業必修課，專選科，公共課，上機實驗課，專業實驗課，體育課，英語語音課，前三個屬于理論課，不在此分配教室。區分：計算機專業的實驗課是和非計算機專業的上節實驗課不同的，他們有自己的實驗室，屬于專業實驗課。前8位編碼不同時表示不同的意思：表3-1 編碼課程關聯表table 3-1 the relational table of coding and course編碼值表示課程類10000000專業必修課11000000專業選修課11100000公共課11110000上機實驗課11111000專業實驗課11111100體育課11111110語音課后8位編碼表示當此教師固定在這個時間片上課時，所在

36、的時間片值。3.2.2染色體的表示對于每一門課程既可能只上一次(規定2學時課占用一個時間片)，也可能上多次，如4學時、6學時等。上2學時課時，該教師編碼只能出現1次，上4學時課時該教師編碼出現2次，依次類推。在大多數，每周上6學時的課程不會太多，大多數時4學時和2學時； 通過以上把課程與教師等同的處理后，原課表的五要素(班級、教室、課程、時間、教師)轉化為四要素(班級、課程、時間）和班級。功能室(實驗室機房、語音室等)已經在編碼時分配好，而理論課的那些，要等到后面再去分配。為了更好地闡述排課遺傳算法，定義排課遺傳算法名詞：a.“基因”混合型的教師編碼，即ti-t25時間片中的值；b.“染色體”

37、班級名稱與tl-t25中的“基因”組成的串；c.“個體”由bjs（班級數）個染色體組合而成的二維數據表，即對應于一張課表。其中bjs為參與課表編排的班級總數；d.“種群”由zqs個個體構成。其中zqs為種群大小。3.2.3 初始化種群每一個“染色體”都是班級的一個課表，是開課任務書中的一個班級所有記錄組成的，形成的是班級+教室+課程+時間一條記錄。 對每一個課程表可以形成一個二維數組kcb (25,bjs)，每一列就表示一個班級的課表。首先把固定教學時間的教師編碼填入該行中，然后使用隨機函數產生一個125的數，將該班的其它教師編碼填入其中。如產生的隨機數對應的時間片中己有數據，則重新產生，直到

38、將所有教師編碼無重復地填入該行中。這樣就有了一條染色體(一個初始的班課程表)。如此循環bjs次，產生了與班級數目對等的染色體數目。于是，一個初始個體便產生了。按種群規模的大小zqs，產生一定數量的個體，每個個體都存放到一個按序編號的表中，由這些個體組成初始種群。很明顯，由上述方式產生的個體通常含有大量的沖突。另外，在初始化種群時，基于容器的容器使其更加簡捷。對于數據庫中教學樓，教室，班級等一些數量都未知的數據進行存儲，運用數組顯然不能解決，會出現很多的冗余，浪費內存，并且處理繁瑣。關聯容器的使用方法如圖6所示：圖6容器結構圖完成種群初始化后，個體的數據結構如下圖示：圖7 個體結構圖4 數據庫問

39、題4.1 數據庫設計 數據庫設計是建立系統數據庫及其應用系統的重要環節，系統的各個部分能否緊密地結合在一起以及如何結合，關鍵在數據庫，只有對數據庫進行合理的邏輯設計和有效的物理設計才能開發出完善而高效的排課系統。本文的數據庫設計及其實現如下：4.1.1 概念模型設計 因為概念結構是面向現實世界的，用戶容易理解，能夠參加設計討論，提出意見，在將分析結果抽象為邏輯數據庫時可以降低設計的難度。這會將數據庫的概念結構轉換為邏輯結構方法簡單，易于實現。對于排課問題要進行的分析主要有:教學計劃、各學院教學任務、教室基礎數據、時間模式、開課任務、及各種課表等數據。這些關系用e-r圖表示如圖8，9，10:圖8

40、 院管理e-r圖圖9 校管理e-r圖圖10 總e-r圖4.1.2 邏輯模型設計 在邏輯模型設計中，并不是劃分數據的粒度越小越精確就會越好，而是要符合設計現狀要求和系統實現便捷，也就是說，范式越高也不一定越好。具體來說創建了以下各表:表 4-1 用戶表:usertable 4-1 user table:user編號數據項數據項別名數據類型數據項含義1用戶名username char(12)唯一2密碼passwdchar(20)3學院academychar(20)學院名，如果空的話就是代表教務處表4-2 教學計劃表:teachplantable 4-2 teaching plan table:te

41、achplan編號數據項數據項別名數據類型數據項含義1班級classchar(15)主屬性2班級編號cnochar(10)主屬性3課程coursechar(15)4課程編號coursenosmallint(2)主屬性5學院academychar(15)6人數pnoint7課程屬性courseatrrchar(15)8周節數pitchnumsmallint(2)9周數weeksumsmallint(2)10開課學期semesterchar(15)表4-3 教室表：classroomtable 4-3 classroom table：classroom編號數據項數據項別名數據類型數據項含義1教學樓

42、tbuildingchar(10)主屬性2門號housenochar(10)主屬性3容納人數containsumint4教室屬性houseatrrchar(10)表4-4語音課體育課上機課位置表：y_t_stable 4-4 the place table：y_t_s編號數據項數據項別名數據類型數據項含義1類別categorychar(1)區別三類教室2教室名roomnamechar(15)3教室編號roomidsmallint4班級classchar(15)加上班級就可以確定班級上課的位置范圍5學院academychar(15)表 4-5 理論課教室表：llkaddresstable 4-5

43、 the classroom table of theory course：llkaddress編號數據項數據項別名數據類型數據項含義1學院academychar(20)2班級classchar(15)3教學樓tbuildingchar(10)表4-6 學院表：academytable 4-6 academy table：academy編號數據項數據項別名數據類型數據項含義1學院academychar(20)2學院編號academyidchar(10)主鍵表4-7 專業實驗課位置表：zysyroomtable 4-7 the lab classroom place：zysyroom編號數據項數

44、據項別名數據類型數據項含義1學院academychar(20)2教室名roomnamechar(15)3教室編號roomidsmallint4班級classchar(15)5容納人數containsumsmallint表4-8 位置表：addresstable 4-8 place table：address編號數據項數據項別名數據類型數據項含義1學院academychar(15)唯一2教學樓tbuidingchar(10)3班級classchar(15)表4-9 教師_課程表t_ctable 4-7 teacher and course table編號數據項數據項別名數據類型數據項含義1教師名

45、tnamechar(10)2教師編號tnosmallint主屬性3課程coursechar(15)4課程編號coursenosmallint主屬性表4-10 教師表：teachertable 4-10 teacher table：teacher編號數據項數據項別名數據類型數據項含義1教師名tnamechar(10)2教師編號tnosmallint唯一3學院academychar(15)4年齡tagesmallint正整數5職稱titlechar(10)表 4-11開課任務表：classtasktable 4-11 the plan table：classtask編號數據項數據項別名數據類型數據

46、項含義1開課學期semesterchar(15)主屬性2學院academychar(15)3班級classchar(15)主屬性4教師名tnamechar(10)5教師編號tnosmallint主屬性6課程編號coursenosmallint7人數pnosmallint8課程coursesmallint9課程屬性courseatrrchar(15)10周數weeksumsmallint11上課次數timessmallint12是否固定issettledchar(1)為0則不固定13固定時間位置timepitchsmallint表4-12 課表：coursetabletable 4-11 cou

47、rse table：coursetable編號數據項數據項別名數據類型數據項含義1開課學期semesterchar(15)主屬性2學院academychar(15)3班級classchar(15)主屬性4教師名tnamechar(10)5教師編號tnosmallint(2)主屬性6課程coursechar(15)7地點addresschar(20)主屬性8周數weeksumsmallint(2)9時間timechar(15)主屬性4.1.3 數據庫的物理設計數據庫的物理設計這一環節也是很重要的，它要綜合考慮存取時間、存儲空間利用率和維護代價三方面的因素。消除冗余數據雖然能提高空間的利用率，但同

48、時也會提高檢索的代價，因此，這三方面必須權衡，選擇一個折中方案。4.2 期望結果4.2.1構造適應度函數為了能夠獲得切實可行的課程表，應以盡量符合排課的經驗常識為目標。而這個要求是一個模糊的不確定問題。因此，為了評判一個課程表的優劣度，必須量化計算課程表的適應度值。適應度值實際上反映了排課人員對課表理想化編排的一種期望。因此，如何把這些“期望”轉化為具體的“值”，是使排課系統得以智能化的關鍵所在。以下共列出了相關期望值定義的5個表:表4-14、表4-15、表4-16、表4-16，其中的數字分別取值于0-10，是對影響期望值的各因素進行的賦值，這些取值經過了系統模塊的反復測試和調整。(1) 期望值a.專業必修課的期望值表 如表4-13所示表4-13 專業必修課的期望值table 4-13 fitness of professional compulsory course時間片1、6、11、16、212、7、12、17、223、8、13、18、234、9、14、19、245、10、15、20、25期望值108420b.公共課和專選課的期望值 如表4-14所示表4-14 公共課和選修課的期望值table