时间表问题

时间表问题（Time Table Problem，简称TTP）是运筹学领域中组合优化问题之一。它有广泛的应用背景。

时间表问题详细介绍

时间表问题（Time Table Problem，简称TTP）是运筹学领域中组合优化问题之一。它有广泛的应用背景。

时间表问题简介

如护士工作时间表、各种体育赛事安排时间表、火车时刻表、各类院校每学期的考试时间表、课程表等等。Wren 将时间表定义为满足约束条件的安排方案，即将关于所研究对象的特定资源安排到一定时空中，并使其尽可能多的满足一系列目标约束。Burke 称TTP 简单地说就是将一系列的事件安排到特定的时域点上，使得同一空间（容量充足）、同一时间只允许一个事件占用。在简化情况下如果有m 个事件安排到n 个时域点上，则共有n的m次方种安排方案；因在约束条件下每一种方案都有其适用的约束范围，故只有极少数方案可以满足全部约束条件。求解TTP 就是寻找满足全部约束条件的最优安排方案。 最初人们是通过手工方式编排TTP，但这种方式费时、费力，而且随着时代的进步关于各类TTP 的信息量大幅度增加，手工制表已经很难找到满意的结果，Even 等人已证明TTP 是一个具有NP 难度的问题。因此求解TTP引起了各领域专家的极大兴趣，并对其进行了深入的研究，不断的将一些现代优化算法用于求解该类问题，如神经网络技术（Neural Networks，简称NN）、专家系统（Expert System，简称ES）、模拟退火算法（Simulated Annealing，简称SA）、进化计算（Evolutionary Computation，简称EC）等等。

时间表问题参考文献

1. Wren A. Scheduling, timetabling and roster a special relationship ,Proceeding of the Practice and Theory of Automated Timetabling,Springer-Verlag LNCS, 1996, 1153: 46-76.

2. Burke E, Elliman D and Weare R. Specialized recombination operators fortimetabling problems , T. C. Fogarty, Evolutionary Computing, AISBWorkshop Leed, UK. Selected Papers, Springer-Verlag, Berlin: 1995, 75-85.

3. Even S, Itai A and shamir A. On the complexity of timetable andmulti-commodity flow problems , SIAM Journal on Computing, 1976, 5(4):691-703.