排课数学模型

软件工程硕士论文：高校自动排课系统排课算法研究与应用(一)摘要排课，是给学校各专业的教学计划中设置的课程安排合适的时间和地点，也就是给每个班的课程安排时间和地点。

排课工作在教学管理中很重要也很繁琐，计算机自动排课系统，可以降低排课人员的工作量，减少排课中的人为因素。

但排课问题属于NP问题，即无法直接得到答案，只能通过猜测获取可能结果。

通常NP问题虽无答案，却有算法，算法不能直接告诉答案，但可以用来判断可能的结果是否J下确可行。

因此，要做好排课工作，提高排课效率，研究排课算法是必不可少的。

本文在查阅大量相关文献的基础上，对高校的排课问题进行了分析，通过对人工智能中的启发式搜索理论的研究，对优先权策略和分配策略加以分析和应用，设计出排课算法启发式排课算法(HTA)。

同时，又对HTA算法中薄弱点(主要是对课程等对优先权过于敏感)进行进一步改造，即在HTA算法的基础上，应用一些拟人的算法或策略，包括靠边策略、择劣策略、前景探测策略、学习策略，减少算法中各因素对优先权的敏感，克服HTA算法的缺陷，完善HTA算法内容。

改造后的算法命名为eHTA算法。

通过实验，证明eHTA算法在减少人工干预排课次数、好时间好教室的利用、尽量满足约束条件、班级和教师的同负荷均衡等方面，能够产生很好的效果，大大提高了排课效率。

论文还介绍了基于eHTA算法的江苏海事职业技术学院自动排课系统构架，并将系统应用的效果与人工排课进行对比，以科学的方式，证明eHTA算法在提高排课效率各方面的作用。

关键词：启发式算法，eHTA，排课The Research and Application of UniversityCoursesTimetabling AlgorithmAbstractCourses timetabling,is to arrange the appropriate time and the place to thecurriculum in school each specialized plan of instruction or is for each class’Scurriculum arrangement．Each semester,coursestimetabling work is in theteaching supervisory work key point and the difficulty．Auto-course timetablingcan help reduce working pressure and mall·made interruption．Courses timetabling,belonging to the NP question，is unable to give the direct answer,but a possibleresult through guess．Although the question does not have the answer，has thealgorithm actually，the algorithm usually cannot tell the answer,but Can tell whetherthe some possibility is true of false．Therefore，it is essential to research oftimetabling．It may help to enhance the timetabling efficiency，promote teachingmanagement level enhancement．This article in the consult massive correlation 1iterature foundation has carried onthe analysis to courscs timetabling，through to the artificial intelligence inspirationalsearch theory research，applied to the priority strategy and the assignment strategy,has designed new algorithm Heuristic Timetabling Algorithm(HTA)．At the sametime，also to HTA algorithm in regarding curriculum the priority too sensitiveshortcoming has made the improvement，proposed the eHTA algorithm，appliessome personification’S algorithm or the strategy，“keeping to the side’’strategy,“selecting the poor'’strategy,“the prospectsurvey'’strategy,“studying'’strategy，reduces in the algorithm the curricula to the priority sensitivity．Through theexperiment，proved the eHTA algorithm in the reduced manual intervention numberof times，the good time good classroom use，satisfies theconstraint condition，theclass and grade and teacher's date load as far as possible balanced and SO on the aspects，can produce the very good results，enhanced the courses timetabling efficiency greatly．The paper also introduced based on the eHTA algorithm Jiangsu MaritimeInstitute’S courses automatic course timetabling system framework．It has alsorecorded this system application effect carried on the past artificial timetabling thecontrast，by the science way，proves the eHTA algorithm in the enhancementtimetabl ing efficiency various aspects function．Key Words：Heuristic Timetabling Algorithm，eHTA，courses timetabling1绪论1．1论文的研究目的在我国高等教育中有两个主体：一是学生主体，二是教师主体。

最多 只能安 排一 门课 ； （ ２ ） 教 师 在 同一 时 间最 多 只能
…
｝； 上 课班 级集 合 ： Ｃ＝ ｛ Ｃ 。 ， Ｃ ， Ｃ 一 Ｃ ｝； 上课
Ｒ＝｝ Ｒ ， Ｒ ， Ｒ － － Ｒ ｝； 上 课教师集 合 ： Ｓ 安排 一 门课 ； （ ３ ） 教 室 在 同一 时 间最 多 只 能 安排 一 门 教室 集合 ： ｛ Ｓ ， Ｓ ２ ， Ｓ 一 Ｓ ｝； 可 用 时 间 集 合 ：Ｔ ＝ ｛ ， ， 课； （ ４ ） 教室 座位数 必须 满足上 课学 生人数 。同 时 ， 还
务 排 课 系统 排 课 结 果 更 具 合 理 性 。
［ 关键 词］蚁群算法 ； 课程编排 ； 算法优化 ［ 中图分类号］Ｔ Ｐ ３ ０ １ ． ６ ［ 文献标 志码 ］Ａ ［ 文章编号 ］１ ０ ０ ８ — ５ ８ ２ ３ （ ２ ０ １ ３ ） ０ ７ － ０ １ ２ ０ － ０ ２ ［ 收稿 日期 ］２ ０ １ ３— ０ ４—２ ５
第２ ９卷
Ｖｏ １ ． ２９
第 ７期
Ｎｏ． ７
兰州教 育 学院 学报
Ｊ ＯＵ ＲＮＡＬ ＯＦ Ｌ ＡＮＺ Ｈ０Ｕ Ｉ Ｎ Ｓ Ｔ Ｉ Ｔ ＵＴ Ｅ ＯＦ ＥＤＵ Ｃ ＡＴ １ ０Ｎ
２ ０ １ ３年 ７月
Ｊ ｕ １ ．２ ０１ ３
高校智能排课系统中蚁群 算法 的应用探讨
优势 ， 提高教 学质 量 。 ｌ １ 为了全 面 优化 排课 结 果 ， 在 课 在合 适 的时间 和教室 内且 不发 生 冲突 。 因此 ， 排课 有 开 设 课 程 集 合 ：Ｌ ＝ ｛ Ｌ ， Ｌ ， Ｌ ， 程编 排 中应 该遵 循 以下 原 则 ： （ １ ） 学 生 在 同一 时间 以下 五 个 因 素 ：

14种策略7大模型“绝杀”排列组合排列组合问题是高考的必考题，它联系实际生动有趣，但题型多样，思路灵活，不易掌握，实践证明，掌握模型和解题方法，识别并化归到模式，熟练运用，是解决排列组合应用题的有效途径。

第一部分——组合的常见技巧策略一：合理分类与准确分步策略分类相加:每类方法都能独立地完成这件事 ；分步相乘:只有各个步骤都完成了，才能完成这件事。

【例1】有11名外语翻译人员，其中5名是英语译员，4名是法语译员，另外两名是英、法语均精通，从中找出8人，使他们可以组成翻译小组，其中4人翻译英语，另4人翻译法语，这两个小组能同时工作，问这样的8人名单可以开出几张？【解析】：按只会英语的有4名、3名、2名分类4431422456525524C C C C C C C C ++【例2】见后面【例19】【特别提醒】 在解排列组合问题时，一定要以两个原理为核心。

按元素的性质分类，按事情发生的过程分步。

综合题通常是整体分类再局部分步。

【类题演练】1、360的正约数（包括1和360）共有 个。

（答案24）2、工厂实验生产中需依次投入2种化工原料，现有5种原料可用，但甲、乙两种原料不能同时使用，且依次投料时，若使用甲原料，则甲必须先投放. 那么不同的实验方案共有____种 （答案15）；3、公司招聘进8名员工，平均分给下属的甲、乙两个部门.其中两名英语翻译人员不能同给一个部门；另三名电脑编程人员也不能同给一个部门，则不同的分配方案有______种 （答案36）；4、f 是集合{}4,5,6M =到集合{}1,0,1N =-的映射。

（答案①7；②9） ①若(4)(5)f f +(6)f =，则映射共有 个 ； ②若()3xf x +为奇数，则映射共有 个。

5、（2010湖南卷理科7)在某种信息传输过程中，用4个数字的一个排列（数字也许重复）表示一个信息，不同排列表示不同信息，若所用数字只有0和1，则与信息0110至多有两个对应位置上的数字相同的信息个数为（ ） （答案B ）（A ）10 （B ） 11 （C ）12 （D ）156、（2010浙江卷17）有4位同学在同一天的上、下午参加“身高与体重”、“立定跳远”、“肺活量”、“握力”、“台阶”五个项目的测试，每位同学上、下午各测试一个项目，且不重复。

赛程安排的数学模型与分析1．前言n支球队在同一场地上进行单循环赛有多种赛程安排，问题是如何编制符合公平性的赛程，数学上这是一个满足一定指标要求的配对排序问题。

本文在合理假设的基础上，由问题的数学实质，建立出问题的线性规划模型；由问题的特殊性将n分为偶数与奇数分别研究，获得关于各队每两场比赛之间相隔场次数上限的一般公式，用构造性方法加以证明；运用归纳的方法发现了这种特殊排序中的对称规律，由此设计出符合上限要求的计算机算法与实际人工编制法。

文中对赛程优劣的评价指标也作了较多的探讨。

本文一个特点是，分析研究迄今体育界实际使用的赛程“循环编制法”，发现其对n为奇数时编制的赛程公平性差，给出了一种n 为奇数时编制简便、结果合理的人工编制法。

2．问题的提出你所在的年级有5个班，每班一支球队在同一块场地上进行单循环赛, 共要进行10场比赛. 如何安排赛程使对各队来说都尽量公平呢. 下面是随便安排的一个赛程: 记5支球队为A, B, C, D, E，在下表左半部分的右上三角的10个空格中, 随手填上1,2,⋯10, 就得到一个赛程, 即第1场A对B, 第2场B对C, ⋯, 第10场C对E. 为方便起见将这些数字沿对角线对称地填入左下三角.这个赛程的公平性如何呢, 不妨只看看各队每两场比赛中间得到的休整时间是否均等. 表的右半部分是各队每两场比赛间相隔的场次数, 显然这个赛程对A, E有利, 对D则不公平.从上面的例子出发讨论以下问题:1) 对于5支球队的比赛, 给出一个各队每两场比赛中间都至少相隔一场的赛程.2) 当n支球队比赛时, 各队每两场比赛中间相隔的场次数的上限是多少.3) 在达到2) 的上限的条件下, 给出n=8, n=9的赛程, 并说明它们的编制过程.4) 除了每两场比赛间相隔场次数这一指标外, 你还能给出哪些指标来衡量一个赛程的优劣, 并说明3) 中给出的赛程达到这些指标的程度.赛程安排直接影响比赛的公平性，如何建立衡量一个赛程的优劣的指标，建立编制公平合理的排列问题的数学研究，也有数学意义。