臺灣博碩士論文加值系統

本研究主要是在探討大學排課問題，其涉及到各項資源限制的最佳化分配，在電腦複雜度上是歸類於NP完全問題(NP-Complete Problem)，亦即排程問題是一項複雜的問題。而問題的主要結構，是將主要的五大因素：包含課程、教師、班級、教室與時間，並找出彼此間複雜的對應關係，盡力求得滿足諸多限制條件的最佳(適)解。但因為各因素彼此之間的排列組合非常多且複雜，甚至有些限制條件還具有不確定性，使得最後的解集合非常的龐大。
啟發式演算法是協助解決排課問題的好方法，通常研究當中所關心演算法的效能是其時間複雜度(Time Complexity)與空間複雜度(Space Complexity)的特性。演算法本身無所謂好壞，各有其特性，端看解決問題的設計策略而定。本研究嘗試應用基因演算法(Genetic Algorithms, GA)進行解決排課問題，並採用Matlab建構求解模式，以大學排課的實例資料進行驗證，另將結果作一比較分析。

The main purpose of this study is to investigate the school timetabling problem, it relates to allocation optimization of the limited resources. It is a NP-Complete problem in computer science. That is solving the school timetabling problem is a complex scheduling problem. The main structure of the problem includes the five main factors: curriculum, teachers, classes, classrooms and time, respectively. Then it needs to find out the relationship between each other, and try to obtain the optimal solution under satisfying all constrains.
However, due the permutations of the final solution are very huge and complex between various factors, and even some constrains are uncertainty.
The heuristic algorithm is a well method to solve the similar complex problem. Generally, the performance of solving this problem usually concerned on the time complexity and space complexity.
The algorithm itself is neither good nor, because of it own self characteristics, thus depending on the strategy of solving problem.
This study applies genetic algorithms to solve the school timetabling problem. And using Matlab software constructs as a solving model. A university timetabling case has been illustrated. And a results comparison has been analyzed.

謝 辭
中文摘要
ABSTRACT
目 錄
圖目錄
表目錄

第一章 緒論
1.1 研究背景
1.2 研究動機
1.3 研究目的
1.4 研究流程
1.5 研究範圍

第二章 文獻探討
2.1 排課問題探討
2.2國內外文獻回顧
2.3 簡介啟發式演算法(HEURISTIC ALGORITHM)
2.4 基因演算法(GENETIC ALGORITHM)
2.4.1 基因演算法(Genetic Algorithm)的源起
2.4.2 基因演算法的運作過程
2.4.3 基因演算法常見之控制參數簡介
2.4.4基因演算法之主要特性

第三章 研究方法
3.1 排課模式說明
3.1.1 案例基本假設
3.1.2 定義集合、參數、決策變數
3.2 排課目標函數模式建構與限制式
3.3研究流程
3.3.1 限制條件
3.3.2 步驟一：染色體的編碼(Encoding)
3.3.3 步驟二：初始族群(Initialization Population)
3.3.4 步驟三：評估目標值與適應函數
3.3.5 步驟四：選擇/複製
3.3.6 步驟五：交配
3.3.7 步驟六：突變
3.4應用MATLAB軟體工具

第四章 實例驗證與分析
4.1案例簡介及實驗環境
4.2 基因演算法最佳化參數設計
4.3 GA參數實驗
4.3.1 收斂世代數
4.3.2 族群大小
4.3.3 交配率
4.3.4 突變率
4.4 問題大小實驗
4.4.1 排課班級數
4.4.2 排課總學分數
4.4.3 開課總教師人數
4.5 實驗結果分析

伍、結論與建議
5.1 研究結論
5.2 未來建議

參考文獻

中文部份
任書鳴(2007)。應用資料探勘技術於排課系統之研究。靜宜大學資訊管理學系研究所碩士論文，未出版，台中。
吳仲銘(2007)。基因演算法與單體法於PID參數最佳化調整之應用。國立台灣海洋大學機械與機電工程學系研究所碩士論文，未出版，台北。
李杰濃(2005)。以樣式技術為基礎之大學排課黑板系統。大葉大學資訊工程學系碩士論文，未出版，彰化。
周明、孫樹棟(2005)。遺傳算法原理及應用，五版。國防工業出版社，北京。
林明德、林師檀(1999)。禁忌搜尋法與遺傳演算法混合模式在地下水復育優選問題之應用。第十六屆環境規劃與管理研討會。
林誌銘(2009)。應用基因演算法於捷運列車運行計劃之研究。國立交通大學運輸科技與管理學系博士論文，未出版，新竹。
邱元泰(2002)。遺傳演算法在排課問題之應用。國立中正大學數學研究所碩士論，未出版，嘉義。
唐學明(1996)。軍事院校電腦排課問題之探討。復興崗學報，第59期，頁129-155。
翁得榮(2007)。排課問題之研究－以高雄第一科技大學運籌管理系為例。國立高雄第一科技大學運籌管理所碩士論文，未出版，高雄。
張良安(2004)。運用基因演算法建置大專院校之排課系統。育達商業技術學院資訊管理研究所碩士論文，未出版，台北。
許武義(1999)。網頁式排課管理系統。暨南國際大學資訊管理學系研究所碩士論文，未出版，南投。
陳木松、廖鴻翰(1998)。適應性突變運算及其運用。大葉學報，第7卷第1 期，頁91-101。
陳奕憲(2011)。基因演算法在國民中學排課問題之最佳化研究。南華大學資訊管理學系研究所碩士論文，未出版，台中。
陳盈樺(2007)。基因演算法於多目標全球成衣報價之應用。國立台中技術學院事業經營研究所碩士論文，未出版，台中。
楊迺聲(2005)。軍事院校班隊排課最佳化之研究。國立中央大學土木工程學系碩士在職專班研究所碩士論文，未出版，中壢。
廖時興(2012)。軍事院校多班隊多班次排課最佳化之研究。真理大學企業管理學系研究所碩士論文，未出版，台北。
廖聖揚(2005)。應用限制規劃方法求解軍事院校排課問題。國立高雄第一科技大學資訊管理所碩士論文，未出版，高雄。
蔡宇宗(2008)。運用模糊理論於排課預處理作業-以遠東科技大學資管系為例。樹德科技大學資訊工程學系研究所碩士論文，未出版，高雄。
鄭惟中(2003)。電腦自動化排課系統之研究。逢甲大學工業工程學研究所碩士論文，未出版，台中。
關銘(2004)。以OWL DL 及SWRL 為基礎建置推論雛形系統- 以大學排課問題為例。中原大學資訊管理研究所碩士論文，未出版，中壢。
蘇木春、張孝德(2002)。機器學習：類神經網路、模糊系統以及基因演算法則。全華科技出版社，台北。


外文部份
Aderemi, O. A., Sawyerr, B. A., Montaz, M. A. (2009). A heuristic solution to the university timetabling problem. Engineering Computations, 26(8), 972-984.
Adler, D. (1993). Genetic algorithms and simulated annealing: a marriage proposal. IEEE International Conference on Neural Networks, 2, 1104-1109.
Bagley, J. D. (1967). The behavior of adaptive systems which employ genetic and correlation algorithms. Dissertation Abstracts International Journal, 28(12), 125-139.
Beligiannis, G. N., Moschopoulos, C. & Likothanassis, S. D. (2009). A genetic algorithm approach to school timetabling. Journal of the Operational Research Society, 60(1), 23-42.
Burke, E., Yuri, B., Newall, J., & Sanja, P. (2004). A time-predefined local search approach to exam timetabling problems. IIE Transactions. 36(6), 509-528.
Burke, E. K., & Newall, J. P. (2004). Solving examination timetabling problems through adaption of heuristic orderings. Annals of Operations Research, 129, 107-134.
Burke, E. K., & Petrovic, S. (2002). Recent research directions in automated timetabling. European Journal of Operational Research, 140(2), 266-280.
Burke, E. K., Pham, Nam., Rong, Q., & Yellen, J. (2012). Linear combinations of heuristics for examination timetabling. Annals of Operations Research, 194(1), 89-109.
Carter, M. W., & Laporte, Gilbert. (1998). Recent developments in practical course timetabling. European Journal of Operational Research, 140(2), 266-280.
Chang, K. H. (2012). Stochastic Nelder-Mead simplex method-A new globally convergent direct search method for simulation optimization. European Journal of Operational Research, 220(3), 684-694.
Chang, P. T., Lin, C. S., Hung, K. C., Lee, H. H., & Chang, C. H. (2010). Collaboration and Competition Process： A Multi-Teams and Genetic Algorithm Hybrid Approach. International Journal of Artificial Life Research, 1(3), 61-89.
Cook, D. F., Ragsdale, C. T., & Major, R. L. (2000). Combining a neural network with a genetic algorithm for process parameter optimization. Engineering Applications of Artificial Intelligence, 13(4), 391-396.
Cooper, T. B., & Kingston, J. H. (1996). The complexity of timetabling construction problems. Computer Science, 1153, 281-295.
De Jong, K. A. (1975). Analysis of the behavior of a class of genetic adaptive systems. The University of Michigan, Ann Arbor, MI.
Enzhe, Yu., & Sung, K. S. (2002). A genetic algorithm for a university weekly courses timetabling problem. International Transcations in Operational Research. 9(6), 703-717.
Even, S., Itai, A., & Shamir, A., (1976). On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing, 5(4), 691-703.
Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Mass: Addison, Wesley.
Goerigk, M., & Schobel, A., (2011). Engineering the modulo network simplex heuristic for the periodic timetabling problem. Artificial Intelligence and Lecture Notes in Bioinformatics, 6630, 181-192.
Grefenstette, J. (1986). Optimization of control parameters for genetic algorithms. IEEE Transactions of Systems, Man & Cybernetics, 16(1), 122-128.
Holland, J. H. (1962). Adaptation in natural and artificial system. Cambridge, USA, MA: MIT Press.
Horst A, Eiselt., & Laporte, G. (1987). Combinatorial optimization problems with soft and hard requirements. Journal of the Operational Research Society, 38, 785-795.
Huntley, C. L., Donald, E. B., & Andrew, R. S. (1989). A parallel genetic heuristics for the quadratic assignment problem. Paper presented at the meeting of Proceedings of the Third International Conference on Genetic Algorithms, 406-515.
Jeong, K., & Lee, J. J. (1996). Adaptive simulated annealing genetic algorithm for system identification. Engineering Applications of Artifical Intelligence, 9(5), 523-532.
Liao, Y. J., Bogju, L., & Randolph, D. (1998). A hybrid approach to modeling metabolic systems using a genetic algorithm and simplex method. Journals & Magazines, 28(2), 173-191.
Liaw, C. F. (2000). A hybrid genetic algorithm for open shop scheduling problem. European Journal of Operational Research, 124(1), 28-42.
Lin, H., & Yamashita, K., (2000). Hybrid simplex genetic algorithm for blind equalization using RBF networks. Mathematics and Computers in Simulation, 59(4), 293-304.
Lindfied, G. & Penny, J. (2000). Numerical methods using matlab. (2nd ed.). Prentice Hall.
Mirrazavi, S. K., Mardle, S. J., & Tamiz, M. (2003). A two-phase multiple objective approach to university timetabling utilising optimization and evolutionary solution methodologies. Operational Research Society, 54(11), 1155-1166.
Mooney, E. L., Rardin, R. L., & Parmenter, W. J. (1995). Large-scale classroom scheduling. IIE Transactions, 1(28), 369-378.
Murata, T., Ishibuchi, H., & Tanaka, H. (1996). Genetic Algorithms for Flowshop Scheduling Problems. Computers and Industrial Engineering, 30(4), 1061-1071.
Nelder, J. A., & Mead, R. (1965). A simplex method for function minimization. Computer Journal, 7(4), 308-313.
Nguyen, D. T. (2007). Solving timetabling problem using genetic and heuristic algorithms. Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/ Distributed Computing, Nong Lam Univ, Ho Chi Minh City. 3, 472-477
Pearl, J. (1984). Heuristic：Intelligent search strategies for computer problem solving. Boston, MA, Addison-Wesley.
Prashant, P. B., Sudhir, R. B., & Vijay, S. K. (2010). Optimum coordination of overcurrent relay timing using simplex method. Electric Power Components and systems, 38(10), 1175-1193.
Rao, S. S. (1996). Engineering optimization-Theory and Practice (3ed.). John Wiley & Sons, Interscience Publication.
Renders, J. M., & Bersini, H., (1994). Hybridizing genetic a hill-climbing methods for global optimization: Two possible ways. Proceedings of the 1st IEEE Conference on Evolutionary Computation Intelligence, Orlando, 312-317.
Sabar, N. R., Ayob, M., Kendall, G., Rong, Q., (2012). A honey-bee mating optimization algorithm for educational timetabling problems. European Journal of Operational Research, 216(3) 533-543.
Sadaf, N. J. & Shengxiang, Y. (2011). A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling. Journal of Scheduling, 14(6), 617-637.
Schaerf, A. (1995). A survey of automated timetabling. Artificial Intelligence Review, 127.
Shengxiang, Y., & Jat, S. N. (2011). Genetic algorithms with guided and local search strategies for university course timetabling. IEEE Transactions on systems, man, and Cybernetics—part C: Applications and reviews. 41(1), 93-106.
Sirag, D. J., & Weisser, P. T. (1987). Toward a unified thermodynamic genetic operator. Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their appliction, 116-122.
Slim. A., & Michael, M. (2000). University course timetabling using constratint handling rules. Journal of Applied Artificial Intelligence. 14, 311-325.
Spendley, W., Hext, G. R., & Himsworth, F. R. (1962). Sequential application of simplex designs in optimization and evolutionary operation. Technometrics, 4(4), 441-461.
Ting,C. K., Li, S.T., & Lee, C. N. (2001). TGA: A New Integrated Approachto Evolutionary Algorithms. Congress on Evlutionary Computation (ECE2001), 2, 917-924.
Vesin, J. M., & Gruter, R. (1999). Model selection using a simplex reproduction genetic algorithm. Signal Processing, 78(26), 321-327.
Victor, A. B. (1996). Computer-aided school and university timetabling: The new wave. Computer Science, 1153, 22-45.
Wayne, S. (2005). Applying data mining to scheduling courses at a university. Communications of the Association for Information Systems, 16, 463-474.
Wren, A. (1996). Scheduling, timetabling and rostering：a special relationship? Computer Science, 1153, 46-75.
Wu, C. Y., & C. H. Shu. (1996). Topological optimization of two-dimensional structure using genetic algorithms and adaptive resonance theory. Tatung Journal, 26, 213-224.
Yen, J., & Bogju, L., (1997). A simplex genetic algorithm hybrid. IEEE International Conference on Evolutionary Computation, 175-180.
Zahra, N. A. (2005). Hybrid heuristics for Examination Timetabling problem. Applied Mathematics and Computation. 163(2), 705-733.