摘要
时间表问题是一类特殊的资源调度问题，广泛应用于学校课程安排、会议日程安排、体育比赛和航班时刻表的制定等。所以如何求解时间表问题成为一个关键的问题。本文以大学课程安排为例子，介绍了一种图形学和人工智能算法相结合的一种方法来对时间表问题进行求解。
图形理论中的着色问题其本质是一个划分问题，将相互之间有冲突的点划分到不同的子集中去。所以，由于图形着色的这种独特的能力，在现实中有着广泛的应用，尤其是在需要解决冲突的领域。
遗传算法是一种借鉴生物界自然选择和进化机制发展起来的算法，具有高度并行、随机、自适应强的特点，是一种非常有效解决NP完全问题的方法。
课程安排问题由于要考虑的限制条件相对来说比较多，属于限制满足的问题，根据这个特征，本文利用图形着色理论(Graph Color Theory)的点着色来表示这些限制条件，将整体的排课分解成三种图形(周图形、日图形、教室图形)来表示。图形中各个节点为要进行分析的对象，即教师、课程、时段以及教室，每条边表示对象之间的互斥关系。
本文的工作重点在于对点着色模型进行求解。针对点着色模型，提出了两个切实可行的求解方法。第一个是分组遗传算法，第二个是基于序列模型的点着色求解方法。
Timetable Problem(TTP) is a special problem of resource arrangement which is widely applied in course scheduling problem(CSP)、all sorts of large conferences、sports games and plane scheduling problem. How to resolve TTP is a key point. This paper introduces a method based on the graphics theory and the artificial intelligence that to resolve the TTP.
In essence, the graph coloring theory is a partition problem. It divided the points which conflict with each other into different subsets. Based on this instinct, graph theory has been used widely to solve the problem that need to solve the conflict problem.
Genetic algorithm is an intelligent algorithm that simulates the process of biological evolution. As a new algorithm of overall optimized search, it has achieved broad application in solving optimization problems due to such distinctive features as simplified process, universality, robustness and availability of parallel processing. Genetic algorithm has become an effective method to resolve NP completeness problem.
General speaking, CSP is a part of constraint satisfaction problem. Employing vertex coloring of graph theory, we can easily transfer the CSP into a solvable problem. For CSP has to assign each course a specific time slot, this study is the first ever to construct three lays of graphs, named as weekday, daily, and room graphs to simplify the problem. The nodes are then defined as teacher, course, timetable and classroom. The edge connected two nodes means confliction, which says both of the two nodes not existence simultaneously.
The emphasis of this paper is to solve the graph model. To solve the model, this paper brings forward two methods. The first one is group genetic algorithm, the second one is merge model.
引文
[1] 熊炎，李大卫，王莉，张庆灵；基于遗传算法的大学课程表研究[D]；数学的实践与认识。2004．6
[2] http://www.imada.sdu.dk/～marco/gcp/[OL]
[3] Johnson, Aragon, McGeoch and Schevon "Optimization by Simulated Annealing: An Experimental Evaluation; Part {Ⅱ}[D], Graph Coloring and Number Partitioning" in Operations Research vol. 39, 378-406, 1991.
[4] Daniel Brelaz "New Methods to Color the Vertices of a Graph" in CACM(22), 251-256, 1979.[D]
[5] Culberson and Luo DIMACS Series, Volume 26, "Cliques, Coloring and Satisfiability" Editors: David S. Johnson and Michael A. Trick, 245-284, 1996.[J]
[6] Culberson "Iterated Greedy Graph Coloring and the Difficulty Landscape " Technical Report TR92-07 [D]
[7] Culberson, Beacham and Papp Hiding our colors in CP'95 Workshop, Studying and Solving Really Hard Problems, Cassis, France, pages 31—42, September 1995.[D]
[8] Bollobas and Thomason "Random Graphs of Small Order" in Random Graphs'83, 47-97, 1985.[D]
[9] Bennet Manvel "Extremely Greedy Coloring Algorithms" in Graphs and Applications (Proceedings of the First Colorado Symposium on Graph Theory, 1982), Frank Harary and John S. Maybee (Eds.) 257-270, 1985.[D]
[10] G. Campers and O. Henkes and J. P. Leclerq "Graph Coloring Heuristics: A Survey, Some New Propositions and Computational Experiences on Random and "{L}eighton's' Graphs" in Operational Research'87 (Buenos Aires, 1987) 917-932, 1988.[D]
[11] A. Hertz and D. de Werra "Using Tabu Search Techniques for Graph Coloring" in Computing(39) 345-351, 1987. [D]
[12] Jensen T R, Tort B. Graph Coloring Problems[M]. New York: A Wiley2Interscience Publication,1995.[D]
[13] Bondy J A, Murty U S R. Graph Theory with Application[M]. The Macmillan Press L TD London, Basingtoke and New York,1976.
[14] Gibbons A. Algorithm Graph Theory[M] Cambridge University Press. Cambridge, London, New York, 1985.
[15] 殷剑宏，吴开亚编著；图论及其算法[M]；中国科学技术大学出版社，2003．7，ISBN7-312-01558-1
[16] 王小平，曹立明等，遗传算法—理论、应用于软件实现[M]，西安交通大学出版社，2002．1，ISBN 7-5605-1448-0
[17] 张文修，梁怡编著]；遗传算法的数学基础[M]；西安交通大学出版社，2000．5，ISBN7-5605-1256-9
[18] 雷英杰 张善文 李续武 周创明 编著；MATLAB遗传算法工具箱及应用[M]；西安电子科技大学出版社 2005．4，ISBN 7-5606-1484-1
[19] 任庆生，叶中行，曾进，戚飞虎；对常用选择算子的分析[D]；上海交通大学学报。2004．4
[20] D. Brelaz,New methods to color vertices of a graph, Commun. Acm 22(1979)251-256 [D]
[21] F. Leighton, A graph coloring algorithm for large scheduling problems. J. Res.Nat. Bureau of standards 84(1979)489-505[D]
[22]M. Chains, A. Hertz and D. de Werra, Some experiments with simulated annealing for coloring graphs, Euro. J. Oper. Res. 32(1987)260-266.[D]
[23] D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimization by simulated annealing: An experimental evaluation, Part II; Graph coloring and number partitioning, Oper. Res. 39(1991)378-406[D]
[24] A. Hertz and D. de Werra, Using tabu search techniques for graph coloring, Computing 39(1987)345-351.[D]
[25]E.Falkenauer.A new representation and operators for genetic algorithms applied to grouping problems. Evolutionary Computation,2(2):123-144,1994[D]
[26]Practice and Theory of Automated Timetabling 3,Third International Conference, PATAT 2000 Konstanz, Germany, August 2000 Selected Papers[M]
[27]Mitchell,M.:An Introduction to Genetic Algorithms.MIT Press,Cambridge,MA(1998)[M]
[28]Burke, E.,Newall,J-P.:Multi-Stage Evolutionary Algorithm for Timetable Problem.IEEE Trans.Evol.Comput.(1999)[M]
[29]Carter,M.W.,Laporte,G.,Lee,S.Y.: Examination Timetabling: Algorithmic Strategies and Applications.J.Oper.Res.Soc.74(1996)373-383[D]
[30]Carter,M.W.,Laporte,G.,Chinneck,J.W.: A General Examination Scheduling System.Interfaces 24(1994)109-120[D]
[31]Schaerf,A.:A Survey of Automated Timetabling.Artif.Intel.Rev.13(1999)87-127[D]