臺灣博碩士論文加值系統

排課問題是一個NP-Complete的問題，一直都沒有很好的解決方法。但是此問題又是毎一個學校在毎個學期都會碰到的一個必要行政作業，其問題的條件限制包括課程、教師、教室、班級、以及設備等複雜因素。很不容易將其轉換成電腦可以解決的程式系統。本論文提出一種改良後的基因演算法運算機制來解決此限制條件非常複雜的排課問題。我們改良後的運算機制可以自然地將排課問題在課程、教師、教室、班級以及設備等複雜的限制條件下融入基因演算法中有效地求解。為了提高此系統的執行效率，我們進而將此基因演算法運算機制導入可以做並行處理的基因代理人計算的概念，並提出兩種基因代理人運算模式：Message Queue、Collection。經過效率執行評估後，我們發現多執行緒和多處理程序下的基因演算法程式確實可以提高本系統的執行效率。

Course Scheduling Problem is an NP-Complete Problem, however, it is also a necessary administration task for every school in every semester. The constraints of a Course Scheduling Problem include complicated parameters such as courses, teachers, classrooms, classes and facilities in a school. It is very difficult to develop an efficient computer system to solve this kind of problem. This paper proposes a modified genetic algorithm to solve the Course Scheduling Problem, which can adapt these complicated parameters very easily and solve the problem efficiently. In order to improve the execution performance of the system, we also introduce genetic agent computing concept into our computing mechanism, which can provide concurrency computation through distributed system. We propose two genetic agent computing models: Message Queue and Collection. We find that the multi-thread and multi-process versions of genetic agent computing indeed can improve the execution performance of our system.

附表目錄............................................... ii
附圖目錄.............................................. iii
第一章 緒論............................................ 1
第一節 研究背景........................................ 1
第二節 文獻探討........................................ 1
第三節 研究目標........................................ 5
第二章 基本定義與問題描述................................7
第一節 基因演算法.......................................7
第二節 排課問題....................................... 11
第三節 排課問題融入基因演算法..........................12
第四節 改良的基因演算法................................16
第三章 基因演算求解排課問題............................21
第一節 如何以基因演算法求解排課問題....................21
第二節 單一族群和多族群下的基因演算法..................35
第四章 系統的架構與分析................................45
第一節 系統架構....................................... 45
第二節 排課作業的運作方式..............................61
第五章 系統評估與分析..................................75
第一節 系統的執行效能..................................75
第二節 系統執行的滿意度................................82
第六章 結論與未來發展方向..............................89
第一節 結論............................................89
第二節 未來發展方向與應用..............................90
參考文獻............................................... 91
附錄一：DTD格式及XML範例............................... 95
附錄二：輸入數據資料...................................111
附錄三：系統畫面...................................... 123

[1] 唐學明,"軍事學校電腦排課問題之探討",復興崗學報59期，1996。
[2] 劉明淵,"電腦在排課作業上的應用-問題的性質與幾個系統的作法", 資訊與教育雜誌 1993.4。
[3] 包冬意,賴永進,吳智輝, "大專院校排課自動化之研究",大葉學報2（1）： p.135-144,1993。
[4] 盧坤勇, "電腦化排課系統指派法則探討", 聯合學報12期.
p107- 116 。民國83.11。
[5] 邱孟佑,廖鴻圖,"植基於Intranet上之電腦輔助排課系統",德明學報12期,頁1-13, ,民86.3。
[6] H.Shimodaira,"A New Genetic Algorithm Using Large Mutation Rates and Population-Elitist Selection(GALME)", Proceesings of the 8th International Conference on Tools with Artificial Intelligence(ICTAI''96).
[7] K.D.Jong,"Genetic Algorithms: A 30 Year Perspective", Festschrift Conference in Honor of John H. Holland, 15-18 May, 1999. http://www.pscs.umich.edu//jhhfest/schedule-closed.html.
[8] N.Chaiyaratans and A.M.S.Zalzala, "Recent Developments in Evolutionary and Genetic Algorithm:Theory and Applications", Genetic Algorithms in Engineering Systems: Innovations and Applications,2-4 September 1997, Conference Publication No.446, @IEEE,1997.
[9] H.R.Bethesda, "Cooperative Model for Genetic Operators to Improve GAs", IEEE International Conference on Intelligence, Information and Systems Nov. 1-3, 1999.
[10] M.Schwehm, "Parallel Population Models for Genetic Algorithms", Copyright © 1997-2001 NEC Research Institute. http://citeseer.nj.nec.com/schwehm96parallel.html.
[11] T.Mastsumura, M.Nakamura, J.Okech ,"Effects of Chromosome Migration on a Parallel and Distributes Genetic Algorithm", Proceedings of the 1997 International symposium on Parallel Architectures, Algorithm, and Network, 1997. (I-SPAN ''97).
[12] K.Kojima, W.Kawamata, H.Matsuo and M.Ishigame , "Network Based Genetic Algorithm", Proceedings of the Seventh International Conference on Parallel and Distributed Systems: Workshops (ICPADS''00 Workshops) Copyright (c) 2000 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.
[13] N.Barnier, P.Brisset, "Optimization by hybridization of a genetic algorithm with constraint satisfaction techniques", 1998 IEEE
http://iciis99.cs.unr.edu/schedule.html.
[14] Selim,SM,"An algorithm for constructing a University faculty timetable". Comput. Edue., 6. pp.323-332. 1982.
[15] Selim,SM, "An algorithm for producing course and lecture timetable". Comput. Edue., 6. pp.323-332. 1983.
[16] Dowsland,W.B. and Lim,s"Computer aided school timetabling - part1: the history of computerised timetabling", Compute Education,pp22-23. 1982,Nov.
[17] Dowsland,W.B. and Lim,s,"Computer aided school timetabling - part2: the micro-computer for school timetabling", Compute Education,pp2-4. 1982,Nov
[18] Loo,E.H. Goh,T,N. and Ong, H.L., " A heuristic approach to scheduling university timetables.", Comput. Edue. 10(3),pp.397-388.1986.
[19] N.L.Lawrie, "An Integer Linear Programming Model of a School Timetabling Problem", The Computer Journal, Vol.12, pp307-316. 1969.
[20] D.C.Wood, "A Technique for Colouring a Graph Applicable to Large Scale Timetabling Problem", The Computer Journal, Vol.12, p317-319. 1969.
[21] S.Even, A.Itai, A.Shamir, "On the Complesity of Timetable and Multicommodity Flow Problems", 16th IEEE Annual Symposium on Foundatiions of Computer Science, pp.184-193, 1975.
[22] Caroline C.Hayes, ”Agents in a Nutshell-A Very Brief Introduction”, IEEE Transactions on Knowledge and Data Engineering, VOL 11, NO.1,January/FEBRARY 1999.
[23] W3C Recommendation 10-February-1998, "Extensible Markup Language (XML)1.0", http://www.w3.org/TR/1998/REC-xml-19980210
http://www.twtec.org.tw/XML_spec.htm
[24] M.Gen , R.Cheng, "Genetic Algorithm & Engineer Design", Willey-Interscience Publication,pp.2-4,1997.
[25] P.Ciancarini, R.Tolksdorf, F.Vitali, D.Rossi, A.Knoche ”Coordinating Multiagent Applications on the WWW: A Reference Architecture”, IEEE Transactions on Software Engineering, VOL 24, NO.5,MAY 1998.
[26] M.Gen , R.Cheng,"Genetic Algorithm & Engineer Design", Willey-Interscience Publication, pp.182-183,1997.