臺灣博碩士論文加值系統

課程排程問題（Course Scheduling）是學校每學期必須處理的例行工作，一般而言，課程指派受到教師時間偏好、課程學分數、修課學生人數與教學資源等諸多因素所影響，因此問題可視為在多重限制條件之下，尋優解的指派問題。傳統的課程指派係以人工手調的方式進行，由於限制條件複雜且無結構特性，問題甚難以量化模式描述，常無法以電腦自動化方式處理，為一項勞力與人工成本密集的工作。
課程排程問題由於考量的限制式相當多，屬於限制滿足問題。基於此特性，本研究利用易於將問題中限制條件表示出的圖形著色理論（Graph Color Theory）中之點著色（vertex coloring）來分析整體的排課問題，首次嘗試將整體的排課流程以三種圖形（週圖形、日圖形、教室圖形）來表示，圖形中的節點為欲分析的對象，即教師、課程、時段及教室；而邊表示教師、課程以及班級間互斥之實體限制；在問題求解上，本研究著重於課程指派至教室後，教室對於該課程教學品質之影響程度，因此以修正「權重圖形之點著色」表示課程指派後之相對品質與績效。在最佳解搜尋方面，由於問題存在區域解，故本研究輔以全域最佳解的禁忌搜尋法（Tabu Search）進行求解，有別於其他研究，本研究利用兩個禁忌名單，分別儲存同時段課程的教室互換以及課程移動時段的屬性，設計出一演算法來提供最佳排課方案。
本研究之目的期能構建學校排課一般化指派程序，並探討圖形著色理論應用於排課問題之適用性，以期排課問題能以更人性化、自動化方式處理，提昇作業品質。
實例驗證方面，本研究利用淡江大學研究所為例，對學校所開出之研究所課程進行改善求解，結果發現經由本研究所設計之求解規則，確實能將其總成本降低，接近最佳解。在教室相關特性分析上，本研究亦針對實際情形進行使用教室的增加及減少、不同懲罰成本的設定進行相關的分析，得到的結果亦能提供相關單位在教室指派上的參考方向。

Course scheduling problem （CSP） is a routine procedure for school administration in each semester. However this problem is complicated with numerous constrains; such as the necessary space for a specific lecture, limited rooms and time sluts for competence among those scheduled courses, and the tolerant walking distance for class transferring from one place to another. In other words, CSP can be grouped as an optimization assignment problem under constrains, most of which are amorphous and hard to be described in mathematical forms. For this reason, CSP has little aid by any computer system.
General speaking, CSP is a part of constraint satisfaction problem. Employing vertex coloring of graph theory, we can easily transfer the CSP into a solvable problem. For CSP has to assign each course a specific time slut, this study is the first ever to construct three lays of graphs, named as weekday, daily, and room graphs to simplify the problem. Four sets of nodes are then defined as teacher, course, timetable and classroom. The edge connected two nodes means confliction, which says both of the two nodes not existence simultaneously. To address the preference associated with teaching quality, we modify the vertex coloring into a weighted graph. Furthermore, to search the best scheduling courses, a modified global optimum Tabu Search algorithm, with double Tabu lists, is designed to avoid possible local points. One Tabu list stores the exchanged classroom and course information, and the other saves the time slut information.
According to the course scheduling in graduate school of TamKang university, this study shows that CSP in reality can be solved in an automatic way in a short time. Meanwhile, it does improve the teaching quality if making change of currently been executed courses as long as reformulating CSP with weighted preference. Finally, the sensitivity analysis provides valuable information of the trend and logic for room management.

第一章 緒論
1.1 研究背景與動機………………………………………………1
1.2 研究目的………………………………………………………1
1.3 研究對象與範圍………………………………………………2
1.4 研究方法………………………………………………………2
1.5 研究內容與流程………………………………………………2
1.5.1 研究內容……………………………………………………2
1.5.2 研究流程……………………………………………………3
第二章 文獻回顧
2.1 排課作業問題之探討…………………………………………4
2.2 排課問題之相關研究…………………………………………6
2.2.1 數學規劃法…………………………………………………6
2.2.2 啟發式解法…………………………………………………7
2.2.3 圖形著色理論………………………………………………8
2.2.4 資料庫管理及專家系統……………………………………8
2.2.5 限制規劃……………………………………………………9
2.3 圖形著色理論…………………………………………………9
2.4 全域最佳解搜尋法……………………………………………13
2.5 小結……………………………………………………………15
第三章 研究方法
3.1 圖形著色理論…………………………………………………19
3.1.1 點著色………………………………………………………19
3.2 禁忌搜尋法……………………………………………………21
3.3 圖形著色理論應用於排課問題………………………………28
3.3.1 點著色………………………………………………………28
3.4 構建圖形………………………………………………………29
3.4.1 週圖形………………………………………………………29
3.4.2 日圖形………………………………………………………31
3.4.3 教室圖形……………………………………………………34
3.5 圖形求解………………………………………………………35
3.5.1 圖形著色……………………………………………………35
3.5.2 目標式構建…………………………………………………36
3.6 最適排課之禁忌搜尋法………………………………………37
3.7 求解流程………………………………………………………40
第四章 實例測試與分析
4.1構建相關集合….………………………………………………44
4.1.1 輸入集合……………………………………………………44
4.1.2 整理出之集合………………………………………………46
4.1.3 輸出集合……………………………………………………46
4.2簡例測試……………………………………………………….48
4.3結果分析……………………………………………………….58
第五章 實例驗證
5.1 排課作業之現況………………………………………………59
5.2 懲罰成本之制定………………………………………………63
5.3 實例驗證………………………………………………………66
5.4 結果分析………………………………………………………70
5.4.1 資料分析方面………………………………………………70
5.4.2 演算流程方面………………………………………………72
5.4.3 敏感度分析…………………………………………………72
5.5 小結……………………………………………………………77
第六章 結論與建議
6.1 結論……………………………………………………………78
6.2 建議……………………………………………………………80
參考文獻……………………………………………………………81
附錄一 簡例測試相關資料集合

1.王怡仁，電腦輔助之排課系統，國立雲林科技大學工業工程與管理技術研究所碩士論文，民國87年6月。
2. 包冬意，大專院校排課自動化之研究，大業學報，第二卷第一期，頁135-144，民國82年12月。
3. 吳明澤，將排程專家知識對應至法則之實務做法，淡江大學資訊管理研究所碩士論文，民國82年6月。
4. 吳泰熙、張欽智，以禁忌搜尋法則求解推銷員旅行問題，大業學報，第六卷第一期，民國86年12月。
5. 金國忠，依規則為基礎的排課系統之研究，淡江大學管理科學研究所碩士論文，民國74年6月。
6. 許文楷，專校教師課程指派決策支援系統之研究，和春學報，第四期，頁121-131，民國86年7月。
7. 張百棧，圖形著色理論在考試時間表問題的應用，工業工程學刊，第十二卷第二期，頁81-88，民國84年4月。
8. 唐學明，軍事學院排課自動化之研究 — 以國防管理學院為例，國防管理學院資源管理研究所碩士論文，民國76年6月。
9. 陳伯亮，簡介圖形著色問題，數學傳播，第十七卷第四期，頁27-31，民國82年12月。
10. 陳志昇，大專院校電腦化之研究，國立成功大學工業管理學系碩士論文，民國73年6月。
11. 陳國清，GDA與RRT啟發式解法在VRP問題上之應用，國立交通大學交通運輸研究所碩士論文，民國87年6月。
12. 盧坤勇，電腦化排課系統指派法則探討，聯合學報，第十二期，頁107-116，民國83年11月。
13. 韓復華、陳柏榮、王國琛，應用限制規劃求解排課問題：以交通大學全校性課程排課為例，中華民國第六屆運輸網路研討會論文集，頁33-42，民國90年11月。
14. 韓復華、陳國清，成本擾動法（NM）與兩極跳躍法（FF）在TSP問題應用之研究，國立交通大學運輸工程與管理學系畢業專題研究報告。
15. 顏上堯、黃韋凱、杜宇平，節點塗色問題求解演算法求解之研究，中華民國第四屆運輸網路研討會論文集，頁94-103，民國88年10月。
16. Brelaz, D. “New Methods to Color the Vertices of A Graph,” Communications of the ACM, Vol.22, pp.251-256, 1979.
17. Carter, M. W. and Craig A. Tovey, “When Is The Classroom Assignmnet Problem Hard?”, Operation Research, Vol.40, No.1, pp.28-39, 1992.
18. Chams, M., A. Hertz and D. Werra, “Some Experiments with Simulsted Annealing for Coloring Graph,” European Journal of Operational Research, Vol.34, pp.260-266, 1987.
19. Charon, I. And Hudry, O., “the Noising Method: A New Method for Combinational Optimization,” Operation Research Letters, Vol.14, No.3, pp.133-137, 1993.
20. Costa, Daniel, “A Tabu Search Algorithm for Computing an Operational Timetable,” European Journal of Operational Research, Vol.76, pp.98-110, 1994.
21. Dueck, Gunter and Scheuer, Tobias, “threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing,” Journal of Computational Physics 90, pp.161-175, 1990.
22. Dueck, Gunter. “New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel,” Journal of Computational Physics 104, pp.86-92, 1993.
23. Garey, M. R. and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman & Company, San Francisco, 1979.
24. Glassey, C. Roger and Michael Mizrach, “A Decision System for Assigning Classes to Rooms,” Interfaces, Vol.16, No.5, pp92-100, 1986.
25. Glover, F. “Heuristics for Integer Programming Using Surrogate Constraints,” Decision Sciences, Vol.8, No.1, pp.156-166, 1977.
26. Glover, F. “Tabu Search: a Tutorial,” Interfaces, Vol.20, pp.74-94, 1990.
27. Gu, J. and Huang, X., “Efficient Local Search Space Smoothing: A case Study of the Traveling Salesman Problem(TSP),” IEEE Transaction on Systems, Man and Cybernetics, Vol.24, No.5, pp.728-736, 1994
28. Knox, J. “Tabu Search Performance on the Symmetric TSP,” Computers & Operations Research, Vol.21, No.8, pp.786-802, 1994.
29. Metropolis, N., Rosenbluth, A. Rosenbluth, M., Teller A. and Teller, E., “Equation of State Calculations by Fast Computing Machines,” Journal of Chem. Physics, Vol.21, pp.1087-1092, 1953.
30. Mulvey, J. M., “A Classroom/Time Assignment Model,” European Journal of Operational Research, Vol.9, No.2, pp.151-162, 1982.
31. Taillard, E. “Robust Taboo Search for the Quadratic Assignment Problem,” Parallel Computing, Vol.17, pp.443-455, 1991.
32. Werra, D. de, “An Introduce to Timetable Problem,” Computers and Operations Research, Vol.19, No.2, pp151-162, 1985
33. Werra, D. de, “Restricted Coloring Models for Timetabling,” Discrete Mathematics, pp.161-170, 1997.
34. Werra, D. de and Lausanne, “Heuristics for Graph Coloring,” Computing Suppl. 7, pp.191-208, 1990.