# 臺灣博碩士論文加值系統

(44.192.92.49) 您好！臺灣時間：2023/06/08 06:19

:::

### 詳目顯示

:

• 被引用:3
• 點閱:728
• 評分:
• 下載:60
• 書目收藏:1
 排課問題主要是將老師、學生、教室等相關的資源，在一定的時間內，依照一定的限制條件排入課表中。排課問題一般會做為最佳化問題，或將其轉為圖形問題來進行討論。在這篇研究中，我們著重在高中排課系統，並提出一個新的論點，將排課問題利用賽局理論中均衡方式來討論。由於要在有限時間內找出奈許均衡是很相似於要找出 NP-hard 的問題，因此，我們提出一個演算法在有限時間內找出柏拉圖均衡。柏拉圖均衡是所有的參與賽局的人都無法提出柏拉圖改善。柏拉圖改善是指一個參與賽局的人能夠提出一個改善的方式，並且不會造成任何一個其他的參賽者的獲利下降。為了避免一直重覆找到相同的局部最佳解，我們提出一個 Risk 變數去提供一個改變的機會，Risk 可以使排課的結果提升約 25%的執行效率。
 Educational timetabling is composed of a fi xing sequence of meetings among teachers, students, and related resources in a given period of time for satisfying a set of di erent constraints. The problem can be regarded as an optimization problem and solved by heuristic methods or reduced to a graph problem for solving. In this study, we focus on high school timetabling and propose a new viewpoint to solve the probelm based on the equilibrium concept in game theory. We attempt to give a strategy for all teachers to reach abalance situation quickly. While a timetabling result has no more improving can be made by a participator himself/herself, the result is in a balance situation, a.k.a. Nash Equilibruim. However, to reach an NE solution is a very di cult computation problem. Instead of searching an NE solution for a long time, we implement a polynomial-time alogrithm to search for a Pareto Optimal solution. A result is a Pareto Optimal solution when there is no more Pareto Improvement can be made by a participator. A Pareto Improvement is an improving made by a participator which will not cause any other pariticipator''s revenue decreasing. We also propose a parameter called "risk" to enhance performance and avoid to reach the same local optimal solution. The result with the parameter "risk" works approximately 25% fast in average.
 1 Introduction 11.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Related Work 52.1 Timetabling Problems . . . . . . . . . . . . . . . . . . . . . . 52.2 Solving Concepts . . . . . . . . . . . . . . . . . . . . . . . . . 73 Problem Model 103.1 Problem De nitions . . . . . . . . . . . . . . . . . . . . . . . . 103.2 Penalty Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 124 Algorithms 194.1 Algoirthm Design . . . . . . . . . . . . . . . . . . . . . . . . . 194.2 Reciprocal Exchange . . . . . . . . . . . . . . . . . . . . . . . 235 Experiment Results 255.1 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 255.2 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.3 Reciprocal Exchange . . . . . . . . . . . . . . . . . . . . . . . 285.4 Experiment Analysis . . . . . . . . . . . . . . . . . . . . . . . 296 Conclusion 31
 [1] A. Schaerf, A survey of Automated Timetabling", Arti cial IntelligenceReview, vol. 13, No. 2, pp. 87-127, April 1999.[2] Hadrien Cambazard, Fabien Demazeau, Narendra Jussien, Interactivelysolving school timetabling problems using extensions of constraint pro-gramming", PATAT 2004., Pittsburgh, PA, pp. 190-207, August 2004.[3] Je rey H. Kingston, A tiling algorithm for high school timetabling",PATAT 2004, Pittsburgh, PA, pp. 233-249, August 2004.[4] Burke E. K., Newall J. P., Weare R.F., A simple Heuristically GuidedSearch for the Timetable Problem", Proceedings of the InternationalICSC Symposium on Engineering of Intelligent System, ICSC AcademicPress, Nottingham, pp.574-579, 1998.[5] Burke E. K., Newall J. P., Weare R. F., A Simple Heuristically GuidedSearch for the Timetable Problem", Proceedings of the InternationalICSC Symposium on Engineering of Intelligent Systems, ICSC AcademicPress, Nottingham, pp. 574-579, 1998.[6] Edmund Kierian Burke and Sanju Petrovic, Recent Research Direc-tion in Automated Timetabling", In European Journal of OperationalResearch, 140/2, pp. 266-280, 2002.[7] Fabio De Cesco, Luca Di Gaspero, and Andrea Schaerf, BenchmarkingCurriculum-Based Course Timetabling: Formulations, Data Formats,Instances, Validation, and Results", PATAT 2008, Montreal, CA, August2008.[8] Edmund K. Burke, Barry McCollum, Paul McMullam, Rong Qu, Ex-amination Timetabling: A New Formulation", Practice and Theory ofAutomated Timetabling, 2006, pp. 373-375.[9] Balakrishnan, N., Lucena, A., Wong, R.T., Scheduling Examinationsto Reduce Second-Order Conicts, Computers & Operations Research",Computers and Operations Research, vol. 19, pp. 353-361, 1992.[10] Myszkowski P., Norberciak M., Evolutionary Algorithms for TimetableProblems", Annales UMCS, Sectio Informatica, vol. I, Lublin, 2003.[11] Yakhno T., Tekin E., Application of Constraint Hierarchy toTimetabling Problems", Proceedings of EurAsiaICT 002, SpringerVer-lag, vol. 2510, pp. 11-18, 2002.[12] Burke E. K., MacCarthy B., Petrovic S., Qu R., Structured Cases inCase-Based Reasoning - Reusing and Adapting Cases for TimetablingProblems", KnowledgeBased Systems 13, 2000.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 基因演算法在國民中學排課問題之最佳化研究 2 演化式策略在國民中學排課問題之最佳化研究

 無相關期刊

 1 國小自動排課系統之研究─粒子群最佳化演算法的應用 2 排課問題之研究－以高雄第一科技大學運籌管理系為例 3 運用模糊理論於排課預處理作業-以遠東科技大學資管系為例 4 應用資料探勘技術於排課系統之研究 5 以C語言撰寫排課系統-以逢甲應數系為例 6 基因演算法在國小排課問題之應用 7 電腦自動化排課系統之研究 8 以成本導向為基礎之排課系統 9 演化式策略在國民中學排課問題之最佳化研究 10 基因演算法在國民中學排課問題之最佳化研究 11 設計啟發式演化式策略最佳化國民中學排課問題 12 非規律性課程排課之研究 13 網頁式排課管理系統 14 基於人工智慧之排課系統 15 應用於大學科系的一套課程排課優化系統

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室