跳到主要內容

臺灣博碩士論文加值系統

(3.239.4.127) 您好!臺灣時間:2022/08/16 02:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:葉杰榮
研究生(外文):Chieh-Jung Yeh
論文名稱:應用ConstraintSatisfactionProgramming方法來探討即時排課問題
論文名稱(外文):The Development of Timetabling System Using Constraint Satisfaction Programming
指導教授:許蒞彥許蒞彥引用關係
指導教授(外文):Li-Yen Hsue
學位類別:碩士
校院名稱:國立高雄第一科技大學
系所名稱:資訊管理系
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:92
中文關鍵詞:排課滿足限制的問題硬性限制軟性限制
外文關鍵詞:timetablingConstraint Satisfaction Problemhard constraintsoft constraint
相關次數:
  • 被引用被引用:6
  • 點閱點閱:600
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
作業研究的領域常將排課問題視為資源分配問題。資源分配問題中必須以滿足所有限制為前提,將有限的資源分配給每一個活動,使每個活動都可以取得所需資源而順利進行。排課問題中的課程可以視為活動,而授課老師、修課班級、教室與上課時間則可以視為活動所需的資源。在排課問題中必須將有限的資源,如:老師、學生、教室、上課時間,分配給每一個課程,並且要符合資源安排的限制與學校的排課準則,使課程可以順利進行。排課問題的目的是滿足學生修習必修課與選修課的需求、讓老師達到授課時數的責任、將空堂集中安排或是讓學生能有最大的選課彈性。排課問題之所以困難是因為這類問題所具有的排列組合特性使得搜尋空間非常龐大;再加上排課過程中的重重限制,如:資源限制與排課規則…等,使得在廣大的搜尋空間中只有少數幾個解可以滿足限制。滿足資源限制與排課規則…等硬性限制的課表,只能算是可行的課表;若要提高課表的滿意度則必須要考量更多的軟性限制,也就是每個課表當事人的個別需求。但在實務上不可能完全滿足每一個老師的個別需求,比較可行的解決方案是讓課表可以滿足所有的硬性限制,並且盡可能的滿足軟性限制。本研究採用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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 104.施永豐、林隆光、王勢爵、王鵬程、柯良時:實驗性近視之研究Ⅲ─光線對眼球發育之影響。中華民國眼科醫學會雜誌 1993;32(1);36-40。
2. 102.汪孝慈、林藎良:電腦工作站光環境與視覺舒適度之個案研究。照明學刊 1999;16(2):8-16。
3. 83.薛小生:照度基準之抉擇。電機技術 1983;9(3):49-58。
4. 78.簡水靖:照明品質與設計。電機月刊 1998;8(3):220-4。
5. 61.紀佳芬、林房儹:電腦作業視覺疲勞的量測方法。勞工安全衛生簡訊 1998;28:5-8。
6. 44.陳明德、王安祥、李德松:影響螢幕視覺績效與視覺疲勞因素之文獻探討。亞東工業專科學校學報 1998;18:1-15。
7. 31.毛義方、黃如瑋、陳秋蓉、蔡明煌、鄭淑芳、周青光、陳美蓮:電腦顯示終端機作業人員自覺疲勞狀況研究。勞工安全衛生研究季刊 1998;6(2):71-85。
8. 24.翁林仲、姚大統、洪英彥、崔華翰:眼科「電腦終端機症候群」研究─視力、屈光杜、眼壓及調節功能。中華民國眼科醫學會雜誌 1994;33(3):385-393。
9. 210.林雅俐:工作/休息策略對多媒體使用者之瀏覽績效及視覺疲勞度影響研究。工業工程學刊,17(6),p565-571,2000。
10. 190.黃福進、曾順輝:正常族群淚功能指數之評估。中華民國眼科醫學會雜誌,37(4),p452-457,1998。
11. 183.蔡武甫:眼睛覺得很乾澀─乾燥感。健康世界,123期,p161-186,1996。
12. 184.劉秀雯、陳威呈:門診病患乾眼症之發生率。中華民國眼科醫學會雜誌,36(4),p356-360,1997。
13. 162.吳鑑修、林新智、謝瑞玟:淡水馬偕護校學生眼屈光狀態之縱系列研究:眼壓與屈光杜、眼軸長度之關係。中華民國眼科醫學會雜誌,34(4),p74-77,1995。
14. 17.陳志勇、林彥輝:半導體業人因工程潛在危害探討。勞工安全衛生簡訊 1997;24:7-8。
15. 16.蔡明成、陳晶川、高宏成:淺談a-TFT-LCD模組封裝技術。電子月刊 2000;6(11):186-196。