臺灣博碩士論文加值系統

排課問題主要是將老師、學生、教室等相關的資源，在一定的時間內，依照一定的限制條件排入課表中。排課問題一般會做為最佳化問題，或將其轉為圖形問題來進行討論。在這篇研究中，我們著重在高中排課系統，並提出一個新的論點，將排課問題利用賽局理論中均衡方式來討論。由於要在有限時間內找出奈許均衡是很相似於要找出 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 a
balance 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 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Related Work 5
2.1 Timetabling Problems . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Solving Concepts . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Problem Model 10
3.1 Problem De nitions . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Penalty Mechanism . . . . . . . . . . . . . . . . . . . . . . . . 12
4 Algorithms 19
4.1 Algoirthm Design . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Reciprocal Exchange . . . . . . . . . . . . . . . . . . . . . . . 23
5 Experiment Results 25
5.1 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.3 Reciprocal Exchange . . . . . . . . . . . . . . . . . . . . . . . 28
5.4 Experiment Analysis . . . . . . . . . . . . . . . . . . . . . . . 29
6 Conclusion 31

[1] A. Schaerf, A survey of Automated Timetabling", Arti cial Intelligence
Review, vol. 13, No. 2, pp. 87-127, April 1999.
[2] Hadrien Cambazard, Fabien Demazeau, Narendra Jussien, Interactively
solving 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 Guided
Search for the Timetable Problem", Proceedings of the International
ICSC Symposium on Engineering of Intelligent System, ICSC Academic
Press, Nottingham, pp.574-579, 1998.
[5] Burke E. K., Newall J. P., Weare R. F., A Simple Heuristically Guided
Search for the Timetable Problem", Proceedings of the International
ICSC Symposium on Engineering of Intelligent Systems, ICSC Academic
Press, Nottingham, pp. 574-579, 1998.
[6] Edmund Kierian Burke and Sanju Petrovic, Recent Research Direc-
tion in Automated Timetabling", In European Journal of Operational
Research, 140/2, pp. 266-280, 2002.
[7] Fabio De Cesco, Luca Di Gaspero, and Andrea Schaerf, Benchmarking
Curriculum-Based Course Timetabling: Formulations, Data Formats,
Instances, Validation, and Results", PATAT 2008, Montreal, CA, August
2008.
[8] Edmund K. Burke, Barry McCollum, Paul McMullam, Rong Qu, Ex-
amination Timetabling: A New Formulation", Practice and Theory of
Automated Timetabling, 2006, pp. 373-375.
[9] Balakrishnan, N., Lucena, A., Wong, R.T., Scheduling Examinations
to Reduce Second-Order Con
icts, Computers & Operations Research",
Computers and Operations Research, vol. 19, pp. 353-361, 1992.
[10] Myszkowski P., Norberciak M., Evolutionary Algorithms for Timetable
Problems", Annales UMCS, Sectio Informatica, vol. I, Lublin, 2003.
[11] Yakhno T., Tekin E., Application of Constraint Hierarchy to
Timetabling 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 in
Case-Based Reasoning - Reusing and Adapting Cases for Timetabling
Problems", KnowledgeBased Systems 13, 2000.