跳到主要內容

臺灣博碩士論文加值系統

(44.210.85.190) 您好!臺灣時間:2022/12/10 13:45
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:周岳胤
研究生(外文):Yue-yin Chou
論文名稱:應用限制規劃於軍事院校教育課程配置問題
論文名稱(外文):Solving class scheduling problem of military academy using Constraint Programming
指導教授:許蒞彥許蒞彥引用關係
指導教授(外文):Li-yen Shue
學位類別:碩士
校院名稱:國立高雄第一科技大學
系所名稱:資訊管理所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:86
中文關鍵詞:限制規劃教育課程配置問題軍事院校
外文關鍵詞:class scheduling problemmilitary academyconstraint programming
相關次數:
  • 被引用被引用:0
  • 點閱點閱:210
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本研究探討軍事院校教育課程配置的問題。問題的特性包括:軍事院校教育訓期不同於一般教育單位採用學年或學期制,視規劃而定教育週期且長短不一,以「週」為編排時間單位。所有課程皆為必修課,沒有選修的情形,課程間具有一定的先後順序關係,對於先修課程而言,其課程特性為至少需修滿規定的特定課程時數之後才允許修其他相關課程,課程間關係複雜,每門課程必須在連續數週中完成,中途不允許間斷,且必須考慮每週各課程的上課時數與教師授課時數限制。在軍事院校中教育課程配置上最大的問題就是:(1) 如何從所有課程集合中決定可安排之課程與各課程的上課時數,(2) 如何指派教師授課且考慮教師每週授課時數限制,以達到最大化每週課程數量與最小化每門課程分布週數。此兩目標基本上會互相衝突,所以在求解過程中會互相牽制。本研究將軍事院校教育課程配置問題以滿足限制問題(CSP)為基礎來建構一系統發展架構,在限制式推理(CBR)之搜尋演算法方面,是以Backtracking為搜尋演算法的基礎,並結合一致性演算法來進行Constraint Propagation降低大量的搜尋空間。求解的過程中配合選取變數策略及指派變數值策略來增加求解的效能與效率。並依問題特性設定適合求解策略和求解目標順序,以達到最大化每週課程數量與最小化每門課程分布週數之目標。最後有效地且較快速地獲得滿意的配置結果。
This research focuses on class scheduling problem in military academy, which is one type of combinatorial problem. The feature of this problem each educational period is different. The total curriculum hours are 35 weekly. The military academy educational plan allocation problem is characterized by precedent -relations between curriculums, and each curriculum must be scheduled in the continuous weeks. Each curriculum must not exceed 10 hours weekly. The weekly teacher may correspond with their teaching hours, for all teachers. The purpose of this research is assign curriculum hours to weeks and assign teachers to curriculums to maximize the curriculum amount weekly and minimize the curriculum distribute over the weeks. These two objectives are in conflict, we apply Constraint Satisfaction Problem and Constraint-Base reasoning to develop a solution strategy. The first part of the solution methodology is development of a system framework for the educational plan allocation problem, which is based on Constraint Satisfaction Problem. The second part applies the Constraint-Based Reasoning for conducting the search process. The search algorithm is based on Backtracking with an Arc Consistency algorithm and applying constraint propagation to reduce search space. Strategies of decomposed processes and variable and value ordering played an important role in solution efficiency. This research provides a well-arranged and efficiently allocation result.
中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 vii
壹、緒論 1
一、研究背景 1
二、研究動機 2
三、研究目的 3
四、研究範圍與限制 4
五、論文架構 4
貳、文獻探討 5
一、Timetabling問題 5
二、軍事院校排課問題 6
三、限制規劃(Constraint Programming, CP) 9
(一)、滿足限制問題(Constraint Satisfaction
problem, CSP) 11
(二)、限制式推理(Constraint-Based Reasoning, CBR)
13
参、問題特性與分析 28
一、問題描述 28
二、問題特性 31
三、兩衝突目標決策求解問題 32
四、限制分析 33
五、問題模式 34
(一)、求解變數 34
(二)、限制式 36
(三)、兩衝突目標決策規劃 37
肆、求解方法 38
一、兩衝突目標決策求解問題 38
二、搜尋策略(Search Strategy) 42
(一)、選取變數策略(Variable Ordering) 42
(二)、指派變數值策略(Value Ordering) 44
伍、軍事院校教育課程配置系統 46
一、系統架構 46
二、系統評估 48
陸、結果分析 49
柒、結論與未來研究方向 53
一、結論 53
二、未來研究方向 53
捌、參考文獻 55
一、中文部份 55
二、英文部份 56
附錄一、教育訓期與課程基本資料 60
附錄二、授課教師資料表 64
附錄三、人工編排結果 68
附錄四、系統編排結果 73
一、中文部份
[1] 林佳慧,2004,「應用Constraint-Based Reasoning最佳化成衣製造組裝線平衡及人員配置問題」,碩士論文,國立高雄第一科技大學資訊管理系。
[2] 周明珠,2004,「多目標遺傳演算法於排課之運用」,碩士論文,樹德科技大學資訊管理研究所。
[3] 唐學明,1987,「軍事學校排課自動化之研究-以國防管理學院為例」,碩士論文,國防管理學院資源管理研究所。
[4] 唐學明,1996,「軍事學校電腦排課問題之探討」,復興崗學報,59期,頁129-155。
[5] 張永昇,1998,「規則式軍事院校電腦排課系統之研究-以國防管理學院短期班隊為例」,碩士論文,國防管理學院資源管理研究所。
[6] 楊迺聲,2005,「軍事院校班隊排課最佳化之研究」,碩士論文,國立中央大學土木工程學系在職碩士專班。
[7] 廖聖揚,2005,「應用限制規劃方法求解軍事院校排課問題」,碩士論文,國立高雄第一科技大學資訊管理系。
[8] 蔡佳吟,2003,「應用CSP規劃大學排課系統」,碩士論文,國立高雄第一科技大學資訊管理系。
[9] 歐宜庭,2005,「應用限制規劃求解煉油廠儲槽資源配置最佳化問題」,碩士論文,國立高雄第一科技大學資訊管理系。
[10] 黎漢林,許景華,李明純,張李志平,2000,供應錬管理與決策-最佳化方法之運用,儒林圖書公司。
[11] 謝玉霜,2001,「限制式規劃應用於港區貨櫃場軌道式門型起重機移動路徑之研究」,碩士論文,國立成功大學交通管理學系。

二、英文部份
[12] Barták R., 1998, “On-line Guide to Constraint Programming”, http://kti.ms.mff. cuni.cz /~Barták/constraints/intro.html .
[13] Barták R., 1999, “Constraint Programming: In Pursuit of the Holy Grail”, In Proceedings of week of Doctoral Students (WDS99), PartⅣ, pp.555-564.
[14] Bessiere C., 1994, “Arc-consistency and arc-consistency again”, Artificial Intelligence 65, pp.179-190.
[15] Bessiere C., Freuder E. C., and Régin J. R., 1999, “Using constraint metaknowledge to reduce arc consistency computation”, Artificial Intelligence 107, pp.125-148.
[16] Borning, A., 1994, Principles and Practice of Constraint Programming, Rosario, Orcas Island, WA, USA.
[17] Brailsford S. C., Potts C. N., and Smith B. M., 1999, “Constraint satisfaction problems: algorithm and applications.” European Journal of Operational Research, 119, pp 557-581.
[18] Burke E.K., Kingston J., and Jackson K., et al., 1997, “Automated University Timetabling: The State of the Art”, The Computer Journal, 40(9), pp.565-571.
[19] Burke E.K., Ross P. (Eds.), 1996, The Practice and Theory of Automated Timetabling I: Selected Papers from the 1st Int’l Conf., Springer Lectures Notes in Computer Science Series, Vol.1153, Napier University, August29-September 1,1995.
[20] Burke E.K., Carter M. (Eds.), 1998, The Practice and Theory of Automated Timetabling II: Selected Papers form the 2nd Int’l Conf., Springer Lectures Notes in Computer Science Series, Vol.1408, University of Toronto, August 20-22, 1997.
[21] Burke E.K., Wilhelm E. (Eds.), 2000, The Practice and Theory of Automated Timetabling III: Select Papers from the 3rd Int’l. Conf., Springer Lectures Notes in Computer Science Series, Vol.2079, University of Constance, August, 2000.
[22] Burke E. K. and Petrovic S., 2002, “Recent Research Directions in Automated Timetabling”, European Journal of Operational Research.
[23] Caprara A., Focacci F., Lamma, et al., 1998, “Integrating Constraint Logic Programming and Operations Research Techniques For The Crew Rostering Problem”, Software-Practice & Experience 28, pp.49-76.
[24] Carter M.W., Laporte G., and Chinneck, J.W., 1994, “A General Examination Scheduling System”, Interfaces 24, pp.109-120.
[25] Cheng Y., 1999, “Arc Consistency Revisited”, Information Processing Letters 70,pp. 175-184.
[26] Cooper T.B. and Kingston J.H., 1996, “The Complexity of Timetabling Construction Problems”, pp.183-295.
[27] David J. M., Chew T.L., 1995, “Constraint-based applications in production planning: examples from the automotive industry.”, In: Proceedings of Practical Applications of Constraint Technology (PACT’95). Practical Applications Company, Blackpool, UK, pp.37-51.
[28] Dincbas M., Simonis H., Van Hentenryck P., 1988, “Solving a cutting-stock problem in constraint logic programming.”, In: Logic Programming, MIT Press, Cambridge, MA, pp.42-58.
[29] Gaschnig J., 1979, “Performance Measurement and Analysis of Certain Search Algorithms”, Ph.D. diss., Dept. of Computer Science, Carnegie Mellon Univ.
[30] Ilog Optimization Suit-White Paper, 2001, http://www.ilog.com/products/ optimization/papers.cfm.
[31] Krzysztof R.Apt, 2003, Principles of Constraint Programming, Cambridge University Press, Cambridge.
[32] Kumar V., 1987, “Depth-First Search”, In Encyclopaedia of Artificial Intelligence,volume 2 , ed. S. C. Shapiro, 1004-1005. New York: Wiley.
[33] Kumar V., 1992, “Algorithm for Constraint Satisfaction Problems: A Survey”, AI Magazine, vol.13, pp.32-44.
[34] Mackworth A.K., 1977, “Consistency in networks of relations”, Artificial Intelligence, 8(1), pp.99-118.
[35] Mohr R. and Henderson T.C., 1986, “Arc and path consistency revised”, Artificial Intelligence 28, pages 225-233.
[36] Montanary, U., 1974, “Networks of constraints foundational properties and applications to picture processing”, Information Sciences, vol7,p95-132.
[37] Montanari, U., Rossi, F., 1995, Principles and Practice of Constraint Programming- CP ''95, Cassis, France.
[38] Nuitjen W.P.M., Gunnen G.M., and Aarts E.H.L., et al., 1994, “Examination timetabling: A case study for constraint satisfaction”, In: Proceedings of Workshop on Constraint Satisfaction Issues Raised by Practical Applications, pp.11-19.
[39] Perlin M., 1992, “Arc consistency for factorable relations”, In Artificial Intelligence 53, pp.329-342.
[40] Podelski, A., 1994, Constraint Programming: Basics and Trends, 1994 Chatillon Spring School, Chatillon-sur-Seine, France.
[41] Regin J. C., Puget, J. F., 1997, “A filtering algorithm for global sequencing constraint.” In: Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, vol.1330, pp.32-46.
[42] Sabin D., Freuder E.C., 1994, “Contradicting conventional wisdom in constraint satisfaction”, Proceedings of European Conference on Artificial Intelligence (ECAI-94), Wiley, Chichester, UK, pp.125-129.
[43] Safaai Deris, Sigeru Omatu, Hiroshi Ohta, 2000, “Timetable planning using the constraint-based reasoning.”, Computer & Operations Research, vol. 27, pp.819-840.
[44] Saraswat, V., Van Hentenryck, P., 1995, Principles and Practice of Constraint Programming, MIT, London, England.
[45] Schaerf A., 1995, “A survey of automated timetabling”, Artificial Intelligence Review, vol.13, pp.87-127.
[46] Shaw P., 1998, “Using constraint programming and local search methods to solve vehicle routing problem”, In: Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, vol.1520, pp.417-431.
[47] Tsang E., 1993, Foundations of Constraint Satisfaction, Computation in Cognitive Science.
[48] Van Hentenryck P., Carillon, J.P., 1988, “Generality versus specificity: An experience with AI and OR techniques.” In: Proceedings of 7th Conference on AI 2(AAAI 88). AAAI Press, Cambridge, MA, pp.660-664.
[49] Van Hentenryck P., Deville Y., and Choh-Man T., 1992, “A Generic Arc-consistency Algorithm and its Specializations”, Artificial Intelligence, vol.57,pp.291-321.
[50] Waltz. D., 1972, “Generating Semantic Description from Drawings of Scenes with Shadows”, Technical Report AI271, MIT, MA.
[51] Wren, A., 1996, "Scheduling, Timetabling and Rostering–A special Relationship?" ,In: 1st Int''l Conf., Springer Lectures Notes in Computer Science Series, 1996 pp.46-75.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top