跳到主要內容

臺灣博碩士論文加值系統

(44.192.22.242) 您好!臺灣時間:2021/07/28 06:17
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:蕭榮亭
研究生(外文):Jung-Ting Hsiao
論文名稱:應用多代理人系統於大學排課問題之研究
論文名稱(外文):A Study of Applying Multi-Agent System to the University Timetabling Problem
指導教授:許通安許通安引用關係
指導教授(外文):Tong-An Hsu
學位類別:碩士
校院名稱:中原大學
系所名稱:資訊管理研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:中文
論文頁數:91
中文關鍵詞:多代理人系統代理人大學排課排課
外文關鍵詞:university timetablingMAStimetablingmultiagent systemagent
相關次數:
  • 被引用被引用:9
  • 點閱點閱:223
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
對國內大多數教室空間不充足的大專院校而言,排課業務是每學期所必須面對的一項艱巨任務,同時也是一項吃力不討好的工作,其原因除了排課本身是一個相當複雜問題之外,如何能產生一個可以符合大多數任課教師期望的教師課表則更是一項更為重大的挑戰。本研究基於多agent系統(Multi-Agent System)的技術,利用以物以物交易(Barter)為基礎,並應用荷蘭式拍賣來做為交易的協定機制來進行授課時段的交換。
本研究中同時比較了弱勢優先和隨機排序等二種拍賣順序,並增加了一個有別於一般agent是以自利(self-interested)為基礎的利他(Altruistic)型的agent在買賣雙方,此一利他型agent會在有助於提昇全體利益的前提下會犠牲自己個人的利益。經由實驗之後發現利用多agent的拍賣機制所進行的時段交換交易的確可以有效的提昇全體教師授課滿意度,再經由利他型agent的導入則可以更加改善全體的教師滿意度,但是競標方是利他型agent或者是拍賣方是利他型agent又或者是雙方agent都是利他型則並無顯著的差異存在;在拍賣順序方面,拍賣順序是否為隨機排序則並不會影響到結果。
For each universities and colleges in Taiwan, the issue of constructing a semester-long timetabling of courses is not only one arduous task but also a taxing and thankless job. In addition to the reason that it is a complicated problem universities and colleges face each semester, how to produce a conflict-free semester-long timetabling of courses which matches with great majority teachers’ expectations will be one greater challenge. Based on the fundamental techniques of many-agent system (Multi-Agent System), this study aims to utilize the mechanism of Dutch auction in doing business trade on things, intending to solve teacher's satisfaction problems of timetabling of courses by exchanging each other’s time periods through the teachers.

This study makes a comparison between the two types of offering order which are the “weak first” and “randomly arranging”. Besides, another Altruistic type of agent is added which is different from others and is able to be known on the premise of contributing to promoting all interests and losing its own personal interests. It is found that the teacher's satisfaction can be effective promoted after utilizing the Multi-Agent System auction mechanism and the result could be more effective if Altruistic type of agent is incorporated. However, there is no significant difference whether the auction bidder, auctioneer or both is Altruistic type of agent. Also, whether in auctioning is arranged randomly will not influence the result.
目錄
論文摘要................................................ i
ABSTRACT ............................................... ii
誌謝.................................................. iii
圖目錄................................................. vi
表目錄................................................ vii
第一章緒論............................................. 1
1.1 研究背景與動機.................................... 1
1.2 研究目的.......................................... 4
1.3 研究範圍與限制.................................... 5
1.3.1 研究範圍...................................... 5
1.3.2 研究限制...................................... 6
1.4 研究流程.......................................... 7
第二章問題說明與文獻探討............................... 8
2.1 排課問題探討...................................... 8
2.1.1 排課問題定義................................ 8
2.1.2 排課元素說明............................... 10
2.2 排課相關文獻回顧................................. 13
2.2.1 排課解決問題分類........................... 13
2.2.2 排課解決問題相關文獻....................... 15
2.3 多agent 系統(Multi-Agent System)................. 18
2.3.1 agent 技術................................... 18
2.3.2 效用函數.................................... 21
2.3.3 多agent 技術................................. 22
2.3.4 agent 技術的系統觀點......................... 24
2.3.5 拍賣........................................ 27
第三章研究方法........................................ 29
3.1 研究說明.......................................... 30
3.2 滿意度協調作業環境說明............................ 33
3.3 agent 的種類...................................... 35
3.4 效用函數.......................................... 37
3.4.1 教師總授課時段滿意度效用函數................. 37
3.4.2 評估教師某一授課時段單位滿意度.............. 42
3.5 agent 間滿意度協調機制............................ 44
3.5.1 執行拍賣.................................... 48
3.5.3 提案與交易的確定............................ 52
第四章系統實作與結果分析.............................. 54
4.1 系統實作.......................................... 54
4.1.1 系統開發工具介紹............................ 55
4.1.2 實驗數據說明................................ 57
4.2 實驗說明與實驗設計................................ 61
4.3 結果分析.......................................... 64
4.3.1 全體平均滿意度分析........................... 64
4.3.2 個別教師滿意度分析.......................... 69
4.3.1.1 教師滿意度改善人數分析................. 69
4.3.1.2 個別教師滿意度改善分析................. 69
4.3 實驗限制.......................................... 71
第五章結論與未來展望.................................. 72
參考文獻............................................... 74
附錄................................................... 77
附錄一、排課程式...................................... 77
附錄二、各式組合之效用結果............................ 87
附錄三、Post Hoc 檢定................................. 89

圖目錄
圖1 . agent 的抽象圖.................................. 19
圖2 agent 架構圖..................................... 36
圖3 拍賣教師提供叫價提案............................. 49
圖4 價競標教師出價................................... 49
圖5 拍賣教師選擇出價提案............................. 50
圖6 教師滿意度協調系統架構圖......................... 54
圖7 協調與管理agent 程式畫面......................... 56
圖8 實驗後滿意度分佈圖............................... 66

表目錄
表1 教師J 每週各時段之意願表......................... 41
表2 滿意度協調中一輪拍賣的進行步驟................... 45
表3 樣本程資料說明................................... 57
表4 排課系統建立初始課表各次的執行時間............... 60
表5 實驗組合......................................... 61
表6 實驗中各組合執行的順序........................... 62
表7 實驗間的變異數分析............................... 65
表8 實驗後全體教師各項組合平均滿意度變化............. 65
表9 自利群和利他群間之組別統計量..................... 67
表10 自利群和利他群間之獨立樣本檢定................... 67
表11 不同輪流方式間之組別統計量....................... 68
表12 不同輪流方式間之獨立樣本檢定..................... 68
表13 實驗後教師滿意度各項變化人數..................... 69
表14 所有教師經由對實驗前後的教師滿意度成對樣本統計量. 70
表15 所有教師經由對實驗前後的教師滿意度成對樣本相關... 70
表16 所有教師經由對實驗前後的教師滿意度成對樣本檢定... 70
1.Lawrence Ong. "An Investigation of an Agent-Based Scheduling in Decentralised Manufacturing Control", Thesis of of M.Phil, Department of Engineering , University of Cambridge, August 2003
2.Rina Azoulay-Schwartz, Sarit Kraus. "Negotiation on Data Allocation in Multi-Agent Environments", http://citeseer.ist.psu.edu/azoulay-schwartz02negotiation.html, 2002
3.Brian F. Cooper,Hector Garcia-Molina. ”Bidding for storage space in a peer-to-peer data preservation system”, International Conference on Distributed Computing Systems, 2002
4.Miclael Wooldridge. ”An Introduction to Multiagent Systems”, John Wiley & Sons Ltd, 2002
5.Sarit Kraus. ”Strategic Negotiation in Multiagent Environments”, The MIT Press, 2001
6.Nils J.Nilsson. “Artificial Intelligence A New Synthesis”, Morgan Kaufmann, 1999
7.Maria Lin Sui Ling. ”Multiagent Constraint Satisfaction and Optimisation”, PHD Thesis, Imperial College of Science, Technology and Medicine, University of London, 2002
8.R.F. Weare, "Automated Examination Timetabling",PhD Thesis, Department of Computer Science, University of Nottingham, UK, June 1995
9.Burke E.K., Elliman D.G. and Weare R.F., “A University Timetabling System Based on Graph Colouringand Constraint Manipulation”, T Journal of Research on Computing in Education. Vol. 26. issue 4,1993
10.Sandhu, “Automating Class Schedule Generation in the Context of University Timetabling Information System”, PhD Thesis, School of Management, Nathan Campus, Griffith University, 2001
11.Sandholm, ”Distributed rational decision making. In Multiagent System” p201~258, MIT Press ,1999
12.K.Socha, M. Sampels, M. Manfrin, “Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art”, 3rd European Workshop on Evolutionary Computation in Combinatorial Optimization,2003
13.Edmund K. Burke, James P. Newall, Rupert F. Weare, “Memetic Algorithm for University Exam Timetabling”, 1st International Conference on the Practice and Theory of Automated Timetabling, 1996
14.Rupert Weare, Edmund Burke, Dave Elliman, “A Hybrid Genetic Algorithm for Highly Constrained Timetabling Problems”, Technical Report NOTTCS-TR-95-8, January 1995
15.Wilhelm Erben, Jürgen Keppler,” Genetic Algorithm Solving a Weekly Course-Timetabling Problem”, Proceedings of the First International Conference on the Practice and Theory of Automated Timetabling (ICPTAT '95), 1995
16.Alberto Colorni, Marco Dorigo, “A Genetic Algorithm To Solve The Timetable Problem”, COMPUTATIONAL OPTIMIZATION AND APPLICATIONS JOURNAL,1993
17.Andrea Schaerf, “Tabu Search Techniques for Large High-School Timetabling Problems”, Report of National Research Institute for Mathematics and Computer Science,1996
18.Christian Blum, Sebastião Correia, Marco Dorigo, Ben Paechter, Olivia Rossi-Doria, Marko Snoek,” A GA evolving instructions for a timetable builder”, Proceedings of the 4th International Conference on Practice and Theory of Automated Timetabling (PATAT 2002),2002
19.Jacques Ferber,”Multi-Agent Systems-An Introduction to Distributed Artificial Intelligence”, Addison-Wesley, 1999
20.Nicholas R. Jennings, Katia Sycara, Michael Wooldridge,” A Roadmap of Agent Research and Development”, Journal of Autonomous Agents and Multi-Agent Systems, 1998
21.Miclael Wooldridge. “Reasoning about Rational Agents”,The MIT Press, 2000
22.Landa, J.,Burke, E.”An Introduction to Multiobjective Metaheuristics for Scheduling and Timetabling”, Metaheuristics for Multiobjective Optimisation, pp. 91--129, Springer, 2004
23.U. Endriss, Y. Chevaleyre, S. Estivie, and N. Maudet. “Welfare engineering in practice: on the variety of multiagent resource allocation problems”, Proceedings of the First International Workshop on Computer Science and Decision Theory, pages 83-100, 2004
24.Ljiming Liu. ”Autonomous Agents and Multi-Agent Systems: Explorations in Learning, Self-Organisation and Adaptive Computation’, World Scientific Publish,2001
25.王富民,2001,基因演算法於排課問題上之研究,國立臺灣師範大學資訊教育研究所碩士論文
26.許武義,1989,網頁式排課管理系統,暨南國際大學資訊管理學系碩士論文
27.趙博,范玉順,MAS技術在生產調度研究中的應用,生產與控制,2003
28.林偉立,分散式限制滿足問題之研究,國立中興大學資訊科學研究所碩士論文,2001
29.陳瑞斌,智慧型網路拍賣與議價機制之研究,朝陽大學資訊管理系碩士班碩士論文,1999
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊