考试
日程方案时总是考虑把考生更多的时间段放在前面。对方案使教师满意的定义：
1、对于每个老师，监考的场次需大致相同；2、因为老师需要休息，对于每个老师，尽量不出现连续监考的情况，监考
安排也需尽量均匀。对方案使学校满意的定义：
1、使考试持续的总时间尽量短；2、设计的安排方案应该简便易行，不致过于繁复，难以实现。综合考虑，最终对于监考方案的确定分四个过程：1将所有参加考试的科目分在不同时间段，保证每个学生不会遇到在同一时间
高校大规模考试的安排方案优化
2
f第九届华东地区大学生数学建模邀请赛论文
段考两门的情况，并且尽量使总持续时间最少。2为各门考试安排教室。保证在同一时间段的各个考场都能有两名监考老师，
同时考虑教室的合理利用。3分配各门考试的时间。根据每天至多可以安排五场考试的假设将所有科目分
配到天，并遵循尽量使学生满意的原则。4为各个教师分配监考场次。每个老师尽量监考他所教授的科目，并满足使老
师满意的条件。（二）模型设计1分配各门考试的时间。1步骤1
首先，为了保证考试的总持续时间最少，我们将第一个步骤归化为如下问题：
某学校有
门课程C1C
需要进行期末考试安排，同一个学生在同一时间
只能参加一门考试，求该校期末考试最少需要安排多少场次的考试。（问题1）我们将看到这与下面的问题是等价的。下面（1）（3）引自参考资料1。（1）图节点着色问题①图节点着色问题
定义图的着色问题图G的一个图节点着色是指k种颜色1，2，，k对于G的各节点的一个分配，使得任意两个相邻的节点分配以不同的颜色。而G
的色数G是指图G节点的着色数k的最小值。
②图节点着色问题的变换定义互补图：图GV，E1，E为边的全集（任意两个属于V的节点之间都有对应边所构成的边的全体），则称图HV，EE1为图GV，E1的互补图。定义图的逆着色：图G的一个逆着色是指k种颜色1，2，，k对于G节点的一
个分配，使得一种颜色的任意两个节点都相邻。而G的逆色数G是指G逆
着色数k的最小值。
定理：图G的互补图H的逆色数H等于图G的色数G。
证明：假设图G的色数Gk，用k种颜色对图G进行一次实例着色，然
后把图G转换为互补图H，根据定义可知这个实例着色也是图G互补图H
的逆着色的一个实例，所以HG，同理可证明HG，
所以HG。
根据定理，图节点的着色问题可以变换为求互补图的逆着色问题从而得到解决。
（2）问题1转化为图节点着色问题问题1可转化为一个r