基于整数规划的排课模型研究

【摘要】根据本校教学资源的拥有情况，分析并提出了排课问题中的关键要素和约束条件，并基于此建立优化排课问题的数学模型，确定排课目标函数，主要对排课问题进行严格的数量关系描述。排课问题就是要在满足一定约束条件下来协调各种教学资源之间的多维冲突，同时还要尽可能满足一些软性约束条件，从而使排出的课表更加合理，满足人性化的需求。

整数规划是一类要求问题中的全部或一部分变量为整数的数学规划。如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。在数学规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求结果必须是整数。本文采用整数规划的方法建立排课问题的数学模型，优化高等院校的排课。

1.排课问题描述

1.1 排课问题要素

从本校的实际情况来看，排课主要考虑时间、班级、课程、教室和教师这五个要素。对这些要素进行透彻的分析以及适当的预处理，是建立排课模型的基础。

（1）时间：排课问题中涉及的时间概念有学年、学期、周、天、时间段等。结合本校上课时间安排，只考虑按周来组织课表。每周5天教学日，每天10节课，分5个时间段，每2节课为一个时间段，每学期每周课表固定。

（2）课程：每门课程都有自己的编号、名称、学时和学分等要求，每门课程每周需要安排的学时体现为课程的学分，1学分的概念就是在每个教学周安排1个学时；周学时为奇数的课程，排课时的实际周学时，取为比该课程周学时数大的最小偶数。

（3）教室：每个教室要有自己的编号和类别名称（如普通教室、多媒体教室、微机室等）等，每个教室在同一时间只能上一门课，且满足教室的类型和教室的容量等要求。

（4）班级：每个班级要有自己的编号和名称，在同一时间一个班级只能上一门课程。

（5）教师：每个教师要有自己的工号和名称，在同一时间一个教师只能上一门课程。

1.2 排课问题约束条件

因为排课问题要满足多种约束条件，为了降低问题复杂度，可将排课的约束条件按照程度分为两大类：硬性约束和软性约束。前者是排课问题中必须遵循的原则，是衡量排课方案是否切实可行的标准，后者是排课过程中应当予以考虑，不一定必须满足，但如果满足可使排课结果更加合理，是衡量排课方案优劣的标准。

2.排课数学模型的建立

基于排课问题涉及的要素和约束条件建立如下排课问题的数学模型，主要对排课问题进行严格的数量关系描述。

2.1 模型参数

3.结论

虽然我们给出了排课问题的目标方程。但是，在不同的教学环境和不同的评价人的主观因素下，很难确定各个目标方程的权重。所以，对于课表优劣的衡量仍然是一个模糊的概念。基于以上的情况，我们不需要寻找问题的最优解，而应该寻找满足约束条件（F，C，L，R，T）的较优组合，从中选择一个作为较优课表。后续我们将进一步研究求解整数规划问题的算法，使排课达到最优组合。

参考文献

[1]鄂强金.基于混沌遗传算法的排课问题研究[硕士学位论文].哈尔滨工程大学，2009.

[2]A.S.Asratian.Investigation of some mathematical model of scheduling theory[D].Moscow University，1980.

[3]于艳东.基于遗传模拟退火算法的智能组卷系统研究[硕士学位论文].内蒙古大学，2011.

[4]C c Gotlieb.The Construction of Class-Teacher Time-Tables.1963.

[5]基于分治和贪心相结合的排课算法研究[D].课程论文：青岛农业大学，2010.