臺灣博碩士論文加值系統

大學排課作業影響層面因素來自教授、學生、課程、學校系所資源以及相關法規等。限於人類有限的理性，人工排課很難在教授、學生、課程三方面的偏好與限制上求取平衡點，故過去排課常採單一因素導向。在本研究中，提出以適應性基因演算法與模糊推論為基礎的大學排課系統。本研究建議以五階段方式進行排課，並藉由學生與教授輸入排課偏好和需求，形成各排課因子權重，編成適合度函數，然後再利用適應性基因演算法與模糊推論進行課程時段與教室的排定。本研究經系統實作，證實適應性基因演算法應用於排課上可避免傳統基因演算法不成熟收斂（Premature convergence）的情況發生，更由於系統提供一收集非排課人員的偏好機制，以及在系統中導入模糊推論，將選修課的衝突程度與教室配適程度反應於適合度函數中，如此兼顧排課效率與品質，更能製作出近乎最佳且人盡滿意的課表。

University timetabling operation can be affected by several factors involving professors, students, instruction resources and related regulations. Owing to the limited human bounded rationality, it is difficult, for the manual timetabling operation, to concern all of the constraints comprehensively. Based on this reason, the single factor was just concerned in the past operation. In this thesis, a timetabling system based on the adaptive genetic algorithm （AGA） and fuzzy inference is proposed. This system provide a five-step timetabling process, in which the factor-weight of fitness function is considered by using the preference data submitted by professors and students. Afterward the system use AGA and fuzzy inference to arrange the time and the classroom to every subject. After system implementation, we can confirm that this system not only can avoid premature convergence as a result of the use of AGA, but it also can generate a near-optimal and satisfactory timetable in virtue of the collection mechanism for the preference data and the employment of fuzzy inference.

第一章 緒論 1
1.1 研究背景與動機 ……………………………………………… 1
1.2 研究目的 ……………………………………………… 2
1.3 研究範圍 ……………………………………………… 3
1.4 研究架構與論文章節概要……………………………………… 4
第二章 文獻探討 7
2.1 排課問題探討 ……...……………………………………… 7
2.2 排課相關文獻回顧 …………………………………….……… 12
2.2.1 國外部份 …..……………………………………… 12
2.2.2 國內部份 …..……………………………………… 17
2.2.3 基因演算法用於排課相關文獻 …..……………… 19
第三章 理論基礎 20
3.1 基因演算法 ……………………………………………… 20
3.1.1 編碼（Encoding） …………………………………… 22
3.1.2 群體初始化（Initialization） ……………………… 22
3.1.3 評估（Evaluation） ………………………………… 22
3.1.4 選擇（Selection） …………..……………………… 22
3.1.5 交配（Crossover） ………………………………… 22
3.1.6 突變（Mutation） ………………………………… 23
3.2 適應性基因演算法 ……………………………………… 24
3.3 模糊邏輯理論 …………………………………………… 27
3.3.1 起源 ……………….……………………………… 27
3.3.2 模糊集合論與模糊邏輯 ……..…………………… 28
3.3.3 模糊推論 ……………………..…………………… 30
3.3.4 模糊控制系統 ………………..…………………… 30
3.4 限制滿足問題 ………….……..………………………… 36
3.4.1 定義 ……………………….……………………… 36
3.4.2 搜尋演算法 ………………………..……………… 37
第四章 排課問題解決方案 40
4.1 目標 …….…….………………………………………… 40
4.2 限制條件分類與處理 ………………..…………………… 40
4.2.1 硬性限制條件 ………….……………………… 40
4.2.2 軟性限制條件 …...…………….……………… 41
4.2.3 限制條件之處理 ….…………….……………… 42
4.3 系統運作流程 …………………..………………………… 42
4.3.1 決定授課科目表 ………….……………………… 43
4.3.2 學生進行課程預選 ……….……………………… 43
4.3.3 學生、教授設定排課偏好與需求 ….…………… 44
4.3.4 排課執行子系統進行排課 ………….…………… 44
第五章 系統實作 63
5.1 系統需求分析 …………………………………………… 63
5.2 系統架構與系統開發軟體 …..…………………………… 64
5.3 系統測試與實驗的資料 ……..…………………………… 70
第六章 結果與建議 71
6.1 系統操作與說明 ………..………………………………… 71
6.1.1 偏好需求設定子系統 ………….………………… 71
6.1.2 排課執行子系統 ……………….………………… 76
6.2 實驗結果 ………………..……………………….……… 88
6.3 研究成果 ………………..……………………….……… 91
6.4 未來研究方向 ………..………………………….……… 92
參考文獻 93

[1] 王怡仁，「電腦輔助之排課系統」，雲林科技大學工業工程與管理技術研究所碩士論文，民國87年。
[2] 包冬意，賴永進，吳智暉，「大專院校排課自動化之研究」，大葉學報，2:（1），民國82年，頁135-144。
[3] 向殿政男著，中國生產力中心技術引進服務組編譯，「FUZZY手法進階」，台北市：全華科技圖書，民國81年。
[4] 范揚明，「模糊理論在股票投資決策上的應用」，國立暨南國際大學資訊管理研究所碩士論文，民國90年。
[5] 唐學明，「軍事學校電腦排課問題之探討」，復興崗學報（59），民國85年，頁129-155。
[6] 張獻文，「運用哈普費爾德-譚克類神經網路開發自動化排課系統」，大葉大學資訊管理研究所碩士論文，民國87年。
[7] 許武義，「網頁式排課管理系統」，國立暨南國際大學資訊管理研究所碩士論文，民國89年。
[8] 陳志昇，「大專院校排課電腦化之研究」，國立成功大學工業管理研究所碩士論文，民國73年。
[9] 菅野道夫著，中國生產力中心技術引進服務組編譯，「FUZZY控制」，台北市：全華科技圖書，民國80年。
[10] 葉耀明，王富民，「基因演算法於排課問題上之研究」，中華民國全國計算機會議，民國90年，頁B044-B051。
[11] 蔡振芳，「深度與廣度搜尋行為在因演算法搜尋的研究」，新世紀、新思維國際學術研討會，民國90年3月，頁355-368。
[12] D. Abramson, J. Abela, “A parallel genetic algorithm for solving the school timetabling problem”, Technical Report, Division of Information Technology, C.S.I.R.O., Apr. 1991.
[13] M. Almond, “An algorithm for constructing university timetables”, The Computer Journal, 1966;8, pp.331-340.
[14] E. D. Barraclough, “The application of digital computer to the construction of timetables”, The Computer Journal, 1965;8, pp.136-146.
[15] Sally C. Brailsford, Chris N. Potts, Barbara M. Smith, “Constraint satisfaction problems: algorithms and applications”, European Journal of Operational Research, 1999;199, pp.557-581.
[16] J. N. G. Brittan and F. J. M. Farley, “College timetable construction by computer”, The Computer Journal, 1971;14, pp.361-365.
[17] Edmund Bruke, David Elliman, Rupert Weare, “A genetic algorithm for university timetabling”, Proceedings of the Second East West International Conference on Computer Technologies in Education, Crimea, Ukraine, 1994, pp.35-40.
[18] Y. L. Chan, “A genetic algorithm shell for iterative timetabling.”, Unpublished M.Sc. thesis, Department of Computer Science, R.M.I.T., 1994.
[19] Alberto Colorni, Marco Dorigo, Vittorio Maniezzo, “Genetic algorithms and highly constrained problems: The timetable case”, Parallel Problem Solving from Nature, Springer-Verlag, 1990, pp.55-59.
[20] Safaai Deris, Sigeru Omatu, Hiroshi Ohta, “Timetable planning using the constraint-based reasoning”, Computers & Operations Research, 2000;20, pp.819-840.
[21] Safaai Deris, Sigeru Omatu, Hiroshi Ohta, Puteh Saad, “Incorporating constraint propagation in genetic algorithm for university timetable planning”, Engineering Applications of Artificial Intelligence, 1999;12, pp.241-253.
[22] M. Dimoopulou, P. Miliotis, “Implementation of a university course and examination timetabling system”, European Journal of Operational Research, 2001, pp.202-213.
[23] W. B. Dowsland and S. Lim, “Computer aided school timetabling-part2: the microcomputer for school timetabling”, Computer Education, 1983, pp.2-4.
[24] S. Even, A. Itai and A. Shamir, “On the complexity of timetable and multicommodity flow problems”, 16th IEEE Annual Symposium on Foundations of Computer Science, 1975, pp.184-193.
[25] Hsiao-Lan Fang, “Genetic algorithms in timetabling and scheduling”, Ph.D. Thesis of Department of Artifical Intelligence, University of Edinburgh, 1994.
[26] R. Feldman, M. C. Golumbic, “Optimization algorithms for student scheduling via constraint satisfiability”, The Computer Journal, 1990;33:4, pp.356-364.
[27] Lars Gislen, Carsten Peterson, Bo Soderberg, “Complex scheduling with Potts neural networks”, Neural Computation, 1992, pp.805-831.
[28] C. C. Gotlieb, “The construction of class─teacher timetabling”, Proc. IFIP Congress, 1962, pp.73-77.
[29] Himawan Gunadhi, V. J. Anand and Yeong Wee Yong, “Automated timetabling using an object-oriented scheduler”, Expert System With Applications, 1996;10:2, pp.243-256.
[30] Hertz, A. “Tabu search for large scale timetabling problems”, European Journal of Operational Research, 1991;54, pp.39-47.
[31] John H. Holland, “Adaptation in natural and artificial systems”, Ann Arbor: The University of Michigan Press, 1975.
[32] Chin-Teng Lin and C. S. George Lee, “NEURAL FUZZY SYSTEMS: A Neural-Fuzzy Synergism to Intelligent Systems”, Prentice-Hall International, Inc., Upper Saddle River, New Jersey, U.S.A., 1996.
[33] Si-Eng Ling, “Intergating genetic algorithms with a Prolog assignment problem as a hybrid solution for a polytechnic timetable problem”, Parallel Problem Solving form Nature Ⅱ, Elsevier Science Publisher B.V., 1992, pp.321-329.
[34] Andrea Schaerf, “A survey of automated timetabling”, Computer Science/ Department of Software Technology, 1995.
[35] S. M. Selim, “An algorithm for producing course and lecturer timetables”, Computer Education, 1983;7:2, pp.101-108.
[36] Gadi Solotorevsky, Ehud Gudes, Amnon Meisels, “Raps- a rule-based language for specifying resource allocation and timetabling problems”, Technical report, Department of Mathematics and Computer Science, Ben-Gurion University, Israel, 1991.
[37] M. Srinivas, L. M. Patnaik, “Adaptive probabilities of crossover and mutation in genetic algorithms”, IEEE Transaction on Systems, Man and Cybernetics, 1994;24:4, pp.656-667.
[38] Shisanu Tongchim, “Coarse-grained parallel genetic algorithm for solving the timetable problem”, Proc. Of 3rd Annual National Symposium on Computational Science and Engineering, Bangkok, 1999.
[39] Arabinda Tripathy, “School timetabling — a case in large binary integer linear programming”, Management Science, Dec. 1984;30:12, pp.1473-1489.
[40] D. C. Wood, “A technique for colouring a graph application to large scale timetabling problem”, The Computer Journal, 1969;12.