楊烽正臺灣大學：工業工程學研究所林宗政Lin, Chung-ChengChung-ChengLin2007-11-262018-06-292007-11-262018-06-292005http://ntur.lib.ntu.edu.tw//handle/246246/51189本文提出一個以遺傳演算法為基的研究所入學考試時間表及考場排程法。針對目前大多以人工方式分兩階段排程的研究所入學考試問題，提出一套混合編碼遺傳演算排程法以期能排出更接近全域最佳解的結果。該排程法包含兩種不同的遺傳演算編碼染色體。數值型編碼的染色體可在不違反考科互斥限制的情況下排定各考科堂次，排序型編碼的染色體則排出最能節省成本的考場分配結果。另外相較於一般考試時間表排程問題，研究所入學考試問題的成本主要落在考場使用數量及監考人員雇用數量。本研究並根據所提出的方法實作一套求解系統，以近年來台、政大的研究所入學考試資料作為範例驗證其可行性。實證結果也顯示本研究所提出的排程法可以有效地縮減監考堂次的成本，並提供介面可清楚地展示排程後的結果。This thesis proposed a genetic algorithm based timetable scheduling method for Graduate Institute Entrance Examination Timetabling Problem (GIEETP). GIEETP used to be scheduled manually in a 2-phase procedure. In order to approach the global optimum, this research presents a combined-coded genetic algorithm (GA) based scheduling method. This method includes two different types of chromosome encoding, real-valued encoding and permutation encoding. The first chromosome allocates timeslots for all subjects and avoids the mutual-exclusive constraints within subjects. The second chromosome arranges sequence for room allocation. In contrast to other exam timetabling problems, GIEETP emphasizes on the cost of total rooms used and the invigilators hired. The scheduling method is implemented in a software system, and real GIEETP data in recent years is taken as example to facilitate result comparisons. Results show that our method in general can obtain a solution more efficiently.摘要 i Abstract ii 目錄 iii 圖目錄 v 表目錄 vi 名詞彙整 vii 符號列表 viii 第1章 緒論 1 1.1　研究背景與動機 1 1.2　研究目的 2 第2章 文獻探討 4 2.1 遺傳演算法簡介 4 2.2 遺傳演算法基本架構 5 2.3 數值型編碼方式的介紹 7 2.3.1 混合交配法 7 2.3.2 隨機均勻突變 8 2.4 排序型編碼方式的介紹 9 2.4.1 PMX交配法 9 2.4.2 嵌入突變法 11 第3章 研究所入學考試問題的遺傳演算模式 12 3.1 研究所入學考試問題介紹 13 3.2 GIEETP問題模式定義 15 3.3　GIEETP的遺傳演算編碼 17 3.3.1　數值型編碼基因串 18 3.3.2　排序型編碼基因串 19 3.4　GIEETP的遺傳演算流程 19 第4章 實例驗證與結果分析 53 4.1 GIEESS排程系統介紹 53 4.2 範例資料說明 58 4.3 實例驗證結果分析 59 第5章 結論與未來研究建議 61 5.1 結論 61 5.2 未來研究建議 61 參考文獻 63 附錄A 台大92年研究所入學考試資料 65 附錄B 台大94年研究所入學考試資料 72 附錄C 政大94年研究所入學考試資料 79975812 bytesapplication/pdfen-US時間表排程遺傳演算法數值型遺傳演算編碼排序型遺傳演算編碼timetable schedulinggenetic algorithmreal-valued encodingpermutation encodingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/51189/1/ntu-94-R90546015-1.pdf