應用多代理人系統於大學排課問題之研究

A Study of Applying Multi-Agent System to the University Timetabling Problem

蕭榮亭(Jung-Ting Hsiao)

指導教授 ： 許通安

中原大學/商學院/資訊管理研究所/碩士(2005年)

https://doi.org/10.6840/cycu200500055

摘要

對國內大多數教室空間不充足的大專院校而言，排課業務是每學期所必須面對的一項艱巨任務，同時也是一項吃力不討好的工作，其原因除了排課本身是一個相當複雜問題之外，如何能產生一個可以符合大多數任課教師期望的教師課表則更是一項更為重大的挑戰。本研究基於多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.

並列關鍵字

university timetabling ； MAS ； timetabling ； multiagent system ； agent

參考文獻

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

7. Maria Lin Sui Ling. ”Multiagent Constraint Satisfaction and Optimisation”, PHD Thesis, Imperial College of Science, Technology and Medicine, University of London, 2002