-
自1963年C C Gotlieb在他的文章 The Construction of Class-Teacher Time-Tables 中提出了课表编排的数学模型，国外对学校课表的自动生成技术引起了极大的关注。一些相关的应用也取得了成功。1976年S Even在论文 The Complexity of Timetable And Multi Commodity Flow Problem 中，第一次证明了课表问题是NP完全的，即算法的计算时间是呈现指数型增长的，这一论断确立了排课表问题的理论深度。对于NP问题完全问题目前在数学上是没有一个通用的算法能够很好地解决。S Even的论证进一步将人们对课表问题复杂性的认识提高到理论高度。
- 上一篇：紫山药国内外研究现状概况
- 下一篇：国内外CZT核辐射探测器的研究现状
国外早期研究大多数使用启发式算法，在模拟人工解决此类问题的基础上进行研究。后来国外研究者们开始运用综合的技术探讨课表类问题，例如整数规划、网络模型等。另外，也有学者试图将这类问题抽象成图着色问题来进行研究。6661
国内对课表问题的研究开始于20世纪80年代初期。研究的早期主要以临界资源分配算法为主，随后出现了以人工智能理论为基础的算法，如知识推理、专家系统等。这些方法对排课问题在理论上作出了近似优化的讨论，但其实验数据较少，其搜索算法或推理过程无法从数学角度给出这些方案是否为有效性的证明。特别来说，有些算法，如遗传算法，还可能逐渐偏离全局优化解和不稳定性。
用图论的角度来对课表问题进行解决，首先提出一种理论上没有冲突的排课模型，然后综合考虑教室资源、教学效果、教师意愿等因素提出的模型优化标准，最后排课模型实现最优化，更能满足实际需要。