https://scholars.lib.ntu.edu.tw/handle/123456789/81893
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor | 楊烽正 | en |
dc.contributor | 臺灣大學:工業工程學研究所 | zh_TW |
dc.contributor.author | 林宗政 | zh |
dc.contributor.author | Lin, Chung-Cheng | en |
dc.creator | 林宗政 | zh |
dc.creator | Lin, Chung-Cheng | en |
dc.date | 2005 | en |
dc.date.accessioned | 2007-11-26T01:04:54Z | - |
dc.date.accessioned | 2018-06-29T00:33:23Z | - |
dc.date.available | 2007-11-26T01:04:54Z | - |
dc.date.available | 2018-06-29T00:33:23Z | - |
dc.date.issued | 2005 | - |
dc.identifier | zh-TW | en |
dc.identifier.uri | http://ntur.lib.ntu.edu.tw//handle/246246/51189 | - |
dc.description.abstract | 本文提出一個以遺傳演算法為基的研究所入學考試時間表及考場排程法。針對目前大多以人工方式分兩階段排程的研究所入學考試問題,提出一套混合編碼遺傳演算排程法以期能排出更接近全域最佳解的結果。該排程法包含兩種不同的遺傳演算編碼染色體。數值型編碼的染色體可在不違反考科互斥限制的情況下排定各考科堂次,排序型編碼的染色體則排出最能節省成本的考場分配結果。另外相較於一般考試時間表排程問題,研究所入學考試問題的成本主要落在考場使用數量及監考人員雇用數量。本研究並根據所提出的方法實作一套求解系統,以近年來台、政大的研究所入學考試資料作為範例驗證其可行性。實證結果也顯示本研究所提出的排程法可以有效地縮減監考堂次的成本,並提供介面可清楚地展示排程後的結果。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.tableofcontents | 摘要 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年研究所入學考試資料 79 | zh_TW |
dc.format.extent | 975812 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.language | zh-TW | en |
dc.language.iso | en_US | - |
dc.subject | 時間表排程 | en |
dc.subject | 遺傳演算法 | en |
dc.subject | 數值型遺傳演算編碼 | en |
dc.subject | 排序型遺傳演算編碼 | en |
dc.subject | timetable scheduling | en |
dc.subject | genetic algorithm | en |
dc.subject | real-valued encoding | en |
dc.subject | permutation encoding | en |
dc.title | 遺傳演算為基的研究所入學考試時間表及考場排程法 | zh |
dc.title | A Genetic Algorithm Based Timetable Scheduling Method for Graduate Institute Entrance Examination Timetabling Problem | en |
dc.type | thesis | en |
dc.identifier.uri.fulltext | http://ntur.lib.ntu.edu.tw/bitstream/246246/51189/1/ntu-94-R90546015-1.pdf | - |
dc.relation.reference | 1. Brailsford, S. C., Potts, C. N., and Smith, B. M., 1999, “Constraint Satisfaction Problems: Algorithms and Applications”, European Journal of Operational Research 119, 557-581. 2. Deris, S., Omatu, S., and Ohta, H., 2000, “Timetable Planning Using the Constraint-based Reasoning”, Computers & Operations Research 27, 819-840 3. Deris, S., Omatu, S., Ohta, H., and Saad, P., 1999, “Incorporating Constraint Propagation in Genetic Algorithm for University Timetable Planning”, Engineering Applications of Artificial Intelligence 12, 241-253. 4. Gen, M. and Cheng, R., 2000, “Genetic Algorithms & Engineering Optimization”, John Wiley & Sons, Inc. 5. Goltz, H. and Matzke, D., 1999, “University Timetabling Using Constraint Logic Programming”, Practical Aspects of Declarative Languages, p.320-334. 6. Gupta, J. N. D., 2002, “An excursion in scheduling theory: an overview of scheduling research in the twentieth century”, Production Planning and Control, Volume 13, Number 2, pp.105-116. 7. Michalewics, Z., 1996, “Evolutionary Computation: Practical Issues”, Proceedings of the Third IEEE Conference on Evolutionary Computation, IEEE Press, Nagoya, Japan, 30-39. 8. Michalewics, Z., 1996, “Genetic Algorithms + Data Structure = Evolutionary Programs”, 3rd ed., Springer-Verlag, New York. 9. Michalewics, Z., Dasgupta, D., Le Riche, R. G., and Schoenauer, 1996, “Evolutionary Algorithms for Industry Engineering problems”, International Journal of Computers and Industry Engineering, vol. 30, no. 4. 10. Paechter, B., Rankin, R. C., Cumming, A., and Fogarty, T. C., 1998, “Timetabling the Classes of an Entire University with an Evolutionary Algorithm”, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature (PPSNV), LNCS 1498, pp.865-874. 11. Paechter, B., Rankin, R. C., and Cumming, A., 1997, “Improving a Lecture Timetabling System for University-Wide Use”, Practice and Theory of Automated Timetabling II (PATAT), pp.156-168. 12. Randy, L. H. and Sue E. H., 1998, “Practical Genetic Algorithms”, John Wiley & Sons, Canada. 13. Schaerf A., 1999, “A Survey of Automated Timetabling”, Artificial Intelligence Review, v.13 n.2, pp.87-127. 14. 劉昌憲,2002,「蟻拓物件分群尋優法及系統開發礎架」,碩士論文,國立台灣大學工業工程學研究所。 | zh_TW |
item.languageiso639-1 | en_US | - |
item.fulltext | with fulltext | - |
item.grantfulltext | open | - |
item.openairetype | thesis | - |
item.openairecristype | http://purl.org/coar/resource_type/c_46ec | - |
item.cerifentitytype | Publications | - |
顯示於: | 工業工程學研究所 |
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
ntu-94-R90546015-1.pdf | 23.53 kB | Adobe PDF | 檢視/開啟 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。