臺灣博碩士論文加值系統

作業研究的領域常將排課問題視為資源分配問題。資源分配問題中必須以滿足所有限制為前提，將有限的資源分配給每一個活動，使每個活動都可以取得所需資源而順利進行。排課問題中的課程可以視為活動，而授課老師、修課班級、教室與上課時間則可以視為活動所需的資源。在排課問題中必須將有限的資源，如：老師、學生、教室、上課時間，分配給每一個課程，並且要符合資源安排的限制與學校的排課準則，使課程可以順利進行。排課問題的目的是滿足學生修習必修課與選修課的需求、讓老師達到授課時數的責任、將空堂集中安排或是讓學生能有最大的選課彈性。排課問題之所以困難是因為這類問題所具有的排列組合特性使得搜尋空間非常龐大；再加上排課過程中的重重限制，如：資源限制與排課規則…等，使得在廣大的搜尋空間中只有少數幾個解可以滿足限制。滿足資源限制與排課規則…等硬性限制的課表，只能算是可行的課表；若要提高課表的滿意度則必須要考量更多的軟性限制，也就是每個課表當事人的個別需求。但在實務上不可能完全滿足每一個老師的個別需求，比較可行的解決方案是讓課表可以滿足所有的硬性限制，並且盡可能的滿足軟性限制。本研究採用Constraint Satisfaction Programming的方法為排課問題提出解決方案，在解決方案中除了考慮硬性限制以確保課表的可行性外，還考慮老師的認知模式以作為排課問題中的軟性限制。最後以高雄第一科技大學資管系的排課問題為例，驗證本研究所提出的解決方案。

The timetabling problem is generally considered as a resources allocation problem in OR, where resources of teachers, students, classrooms, and courses are to be allocated into timeslots of a weekly timetable to achieve an objective function; while subject to constraints among resources. The objective function is to offer a course schedule that can satisfy the needs of students in taking both required and elective courses, fulfill the teaching responsibility of teachers, and, at the same time, minimize slack timeslots within a timetable or maximize the freedom of course selection. The heart of the problem is the constraints that exist as regulations, within each resource, and between resources; and have exhibited the unwelcome nature of combinatorial problems. While there have been many optimization solution approaches suggested in the past, the increasing need to offer a working environment with humanity has forced the management to take into consideration many additional soft constraints. With the understanding that it is impossible to satisfy all personal needs of teaching staff, one needs to look for new solution approaches that can satisfy all hard constraints and as many soft constraints as possible. This study focuses on the application of Constraint Satisfaction Programming to develop a class timetable, which consists of hard constraints that must be satisfied to produce a feasible solution, and soft constraints that represent the ideal cognitive model of teaching staff. The actual course scheduling needs of the Department of Information Management of National Kaoshuing First University of Science and Technology is used for this study.

目錄 i
圖目錄 iii
表目錄 iv
第一章、 緒論 1
第一節、 排課簡介 1
第二節、 研究背景 4
第三節、 研究動機 4
第四節、 研究目的 6
第二章、 文獻探討 7
第一節、 排課問題的特性以及表示模型 7
一、 排課問題的combinatorics性質 7
二、 預排課程與資源的可利用性及不可利用性 12
第二節、 解決方法的分類 13
一、 作業研究（Operations Research, OR） 13
二、 人機互動（Human-Machine Interaction） 15
三、 人工智慧（Artificial Intelligence，AI） 17
第三章、 滿足限制的問題（Constraint Satisfaction Problem，CSP） 20
第一節、 CSP的定義 22
第二節、 Arc consistency 23
第三節、 搜尋演算法 24
第四節、 以CSP方法描述問題的原則 26
第五節、 求解CSP的經驗法則 27
第四章、 系統分析與設計 29
第一節、 排課問題描述 29
第二節、 系統分析 31
一、 變數 32
二、 限制 35
第三節、 排課問題的模型以及解決方案 38
第四節、 系統設計 43
一、 變數編碼 44
二、 限制的規劃 48
第五節、 系統流程設計 56
第六節、 搜尋演算法與目標函數 64
第五章、 系統建置與評估 69
第一節、 系統架構 69
第二節、 系統功能 72
一、 編輯排課相關資料 72
二、 選取軟性限制 74
三、 執行排課 75
第三節、 系統評估 77
第六章、 結論與建議 83
第一節、 結論 83
第二節、 建議 83
參考文獻 86
附錄一：認知模型意見調查表 91

1. Alain Hertz and D. de Werra (1987), “Using Tabu search techniques for graph coloring” Computing 39, 345-351.
2. Alain Hertz and D. de Werra (1990), “The Tabu search metaheuristic: how we used it” Ann. Math. Artificial Intelligence 1, 111-121.
3. Alain Hertz (1991), “Tabu search for large scale timetabling problems.” European Journal of Operational Research 54, 39-47.
4. Alain Hertz (1992), “Finding a feasible course schedule using Tabu search.” Discrete Applied Mathematics 35, 255-270.
5. Angelo Monfroglio (1988), “Timetabling through a deductive database: A case study.” Data & Knowledge Engineering 3, 1-27.
6. Arabinda Tripathy (1992), “Computerised decision aid for timetabling — a case analysis.” Discrete Applied Mathematics 35, 313-323.
7. Bernd A. Knauer (1974), “Solution of a timetable problem.” Computer and Operational Research 1, 363-375.
8. Carlier, J., Pinson, E., (1989), “An algorithm for solving the job-shop problem.” Management Science 35, 164-176.
9. Chen, C.-C., Smith, S.F., (1997), “Applying constraint satisfaction techniques to job shop scheduling.” Annals of Operations Research 70, 327-357.
10. Claude Le Pape (1996), “Constraint-based scheduling: principles and application.”, Intelligent Planning and Scheduling Solutions (Digest No. 1996/197), IEE Colloquium on, 1996 Page(s): 5/1 -5/6
11. C. Berge, Graph, Gauthier-Villars, Paris(1983)
12. D. de Werra (1985), “An introduction to timetabling.” European Journal of Operational Research 19, 151-162.
13. D. de Werra (1985), “Graph, hypergraph and timetabling.” Methods of Operations Research 49, 201-213.
14. D. de Werra (1997), “Restricted coloring models for timetabling.” Discrete Mathematics 165/166, 161-170.
15. D. de Werra (1997), “The combinatorics of timetabling.” European Journal of Operational Research 96, 504-513.
16. David Johnson (1993), “A database approach to course timetabling.” Journal of the Operational Research Society, Vol. 44, No. 5, 425-433.
17. Dincbas, M., Simonis, H., Van Hentenryck, P., (1998) “Solving a cutting-stock problem in constraint logic programming.” In: Kowalski, R.A., Bowen, K.A. (Eds), Logic Programming. MIT Press, Cambridge, MA, pp.42-58.
18. Erlenkotter, D., (1978), “A dual-based procedure for uncapacitated facility location.” Operations Research 26, 991-1009.
19. Gadi Solotorevsky, Ehud Gudes, and Ammon Meisels (1994), “RAPS: a rule-based language for specifying resource allocation and time-tabling problems.” IEEE transactions on knowledge and data engineering, Vol. 6, No. 5, October, 681-697.
20. Gendreau, M., Laporte, G., Potvin, J,-Y., (1997), “Vehicle routing: modern heuristics.” In: Aarts, E.H.L., Lenstra, J.K. (Eds.), Local Search in Combinatorial Optimization. Wiley, Chichester, UK, pp.311-336.
21. Haralick, R. and Elliott, G. (1980), “Increasing tree search efficiency for constraint satisfaction problems.” Artificial Intelligence 14, 263-313.
22. Himawan Gunadhi, V. J. Anand and Yeong Wee Yong (1996), “Automated timetabling using an object-oriented scheduler.” Expert Systems with Applications, Vol. 10, No. 2, pp. 243-256.
23. Irvin J. Lustig and Jean-François Puget, “Program != program: constraint programming and its relationship to mathematical programming.”, http://www.ilog.com/products/optimization/tech/interfaces_informs.pdf.
24. John M. Mulvey (1982), “A classroom/time assignment model.”, European Journal of Operational Research 9, 64-70.
25. Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C., (1992), “An experimental evaluation; Part II, graph coloring and number partitioning.” Operations Research 39, 378-406.
26. Kiaer, L. and Yellen, J. (1992). “Weighted graph and university course timetabling.” Computers & Operations Research, 19, 59-67.
27. Le Kang and George M. White (1992), “A logic approach to the resolution of constraints in timetabling.” European Journal of Operational Research 61, 306-317.
28. Mackworth, A.K. (1977) “Consistency in networks of relations.” Artificial Intelligence 8, 99-118.
29. Menezes, F., Barahona, P., (1994), “Heuristics and look-ahead integration to solve constraint satisfaction problems efficiently.” Annals of Operations Research 50, 411-426.
30. Montanart, U. (1974) “Network of constraints: fundamental properties and applications to picture processing.” Information Science 7, 95-132.
31. N. Chahal and D. de Werra (1989) “An interactive system for constructing timetables on a PC.” European Journal of Operational Research. 40,32-37.
32. Nuijten, W.P.M., Aarts, E.H.L., (1996), “A computational study of constraint satisfaction for multiple capacitated job shop scheduling.” European Journal of Operational Research 90, 269-284.
33. Proll, L., Smith, B.M., (1998), “Integer linear programming and constraint programming approaches to a template design problem.’ INFORMS Journal on Computing 10, 165-275.
34. Ryan, D., (1992), “Solution of massive generalized set partitioning problems in aircrew rostering.” Journal of the Operational Research Society 43, 459-467.
35. S. Even, A. Itai, A. Shamir (1976), “On the complexity of timetable and multicommodity flow problems.” SIAM Journal on Computing 5, 691-703.
36. Sabin, D. and Freuder, E.C. (1994) “Contradicting conventional wisdom in constraint satisfaction.” In: Cohn, A.G. (Ed.), proceedings of European Conference on Artificial Intelligence (ECAI-94). Wiley, Chichester, UK, pp.125-129.
37. Sally C. Brailsford, Chris N. Potts, Barbara M. Smith (1999), “Constraint satisfaction problems: algorithms and applications.” European Journal of Operational Research 119, 557-581.
38. Safaai Deris, Sigeru Omatu, Hiroshi Ohta, Puteh Saad (1999), “Incorporating constraint propagation in genetic algorithm for university timetable planning.” Engineering Applications of Artificial Intelligence 12, 241-253.
39. Safaai Deris, Sigeru Omatu, Hiroshi Ohta (2000), “Timetable planning using the constraint-based reasoning.” Computer & Operations Research 27, 819-840.
40. SB Deris, S Omatu, H Ohta and PABD Samat (1997), “University timetabling by constraint-base reasoning: A case study.” Journal of the Operational Research Society, 48, 1178-1190.
41. Smith, B.M. (1996) “Succeed-first or fail-first: A case study in variable and value oudering heuristic.” In: Proceedings of The Third International Conference on the Practical Applications of Constraint Technology (PACT'97). Practical Applications Company, Blackpool, UK, pp.321-330.
42. Thuriot, C., Ershler, J., Lopez, P., (1994), “Decision approach to workload distribution.” Production Planning & Control 5, 533-542.
43. Vasant Dhar and Nicky Ranganathan (1990), “Integer programming vs. expert systems: a experimental comparison.” Communications of the ACM, Volume 33, Number 3, March, pp.323-336.
44. Van Hentenryck, P., Deville, Y., Teng, T.-M., (1992), “A generic arc-consistency algorithm and its specializations.” Artificial Intelligence 57, 291-321.
45. Vaessens, R.J.M., Aarts, E.H.L., Lenstra, J.K., (1996), “Job shop scheduling by local search.” INFORMS Journal on Computing 8, 302-317.
46. Zhu Chun Bao, “Development of an intelligent timetable scheduling system using constraint-based-reasoning approach.” http://www.ilog.com/corporate/users/papers/Nanyang.pdf.