杨子兰，李 睿，张 瑜

(云南大学 旅游文化学院，云南 丽江 674199)

特殊要求时间段的排课问题数学模型

杨子兰，李 睿，张 瑜

(云南大学 旅游文化学院，云南 丽江 674199)

本文对排课问题的约束条件进行深入分析，将教师、班级、课程捆绑成一个教学任务单元，并以比较重要的课程尽可能地安排在授课效果较好的节次中且多学时课程安排要尽量均匀分布为目标函数，建立0-1整数规划模型，最后结合自然班固定教室的特点，设计出启发式算法求其可行解。

捆绑式排课；整数规划；教学任务单元；启发式算法

1962年Gotlieb提出了课表编排问题的数学模型[1]，从而使之成为计算机软件应用专家和数学家共同研究的课题。1975年S.Even和cooper等人将排课问题理论化，证明了排课问题是NP完全问题[2]，当问题的规模增大时，其复杂度呈指数增长，在一般的实际情况中不可能准确地求出最优解。我国对于排课问题的研究始于20世纪80年代。1984年，林章希和林尧瑞发表了在排课问题上的实验性研究成果[3]。2006年，任克强等给出了一种基于约束满足的高校排课问题模型，提出了高质量排课系统方案[4]。2011年，宗薇根据教师、学生、教室、课程和课程时间段要求建立一个多约束条件的高校排课数学模型，采用随机可行排课法产生可行排课方案，然后利用遗传算法在可行方案中寻找最优排课方案[5]。2012年，杨彦明等人针对军队任职院校课程表编排特点，在分析军队任职院校排课因素、约束条件以及求解目标等问题基础上，建立相应数学优化模型，构建其基本求解框架，并利用遗传算法解决该问题[6]。……