课程表的空间模型及排课算法分析

排课问题的数学模型研究
排课问题是在排定学期课程表的过程中面临的一个重要问题，通过分析特定的条件，寻找出最优解来解决该问题是解决之道。

排课问题可视为一种约束优化问题，是应用数学模型来解决的一类复杂问题，其运用约束条件，求解一组变量使得整体成本最小，具有很强的实际意义。

排课问题的数学模型可以根据实际情况和应用需求来制定，一般情况下，可以采用贪心算法、费用流算法、回溯算法、动态规划算法等多种算法来解决。

贪心算法是一种简单但有效的算法，原则就是每一步取当前最优解。

其优点是算法简单，易于实现，缺点是无法保证全局最优解。

费用流算法是一种有效的排课算法，它采用图论中的费用流模型，追求最大流量决策，可以找出满足资源约束条件的最优解，即满足每一节课最少需要的资源。

回溯算法又称为试探法，按照深度优先搜索，遍历全部节点，枚举所有可能的情况，最终找到可行的解决方案。

动态规划算法是一种优化算法，它的基本思想是，对于每个时期的课程安排，给出最优解，在此基础上，不断更新，最终求出最优解。

排课问题是一个复杂而又实用性很强的问题，受到越来越多人的重视。

数学模型是解决该问题的重要手段，历来受到各大学者的关注。

通过贪心算法、费用流算法、回溯算法、动态规划算法等，可以找到满足条件的最优解。

只要模型，算法和数据得到合理的设计与使用，
排课问题的解决方案有可能实现。

总而言之，数学模型是解决排课问题的重要手段。

模型的设计应该以实际情况为准，考虑各种约束条件，寻求出真正能够满足需求的优化解决方案。

只有这样，才能高效、准确地解决排课问题，实现客观有效地排课。

学校排课课程表制定方案近年来，随着教育的发展和改革，学校排课课程表的制定对学生的学习效果和全面发展起着至关重要的作用。

如何制定一个合理、科学的课程表是每个学校都面临的一个重要问题。

本文将从学生需求、教师需求、课程设置、时间分配等方面，探讨学校排课课程表制定方案。

一、学生需求学生是学校存在的根本，他们的需求是制定课程表的出发点和依据。

每个学生都有自己的学习特点和兴趣爱好，因此，学校应该根据学生的需求，合理安排课程的类型和时间。

比如，有的学生喜欢文科类学科，而有的学生则偏爱理科类学科。

学校可以根据学生的兴趣爱好，提供艺术、体育、创新等选择性课程，使每个学生都能在学习中找到自己的兴趣和方向。

二、教师需求教师是学生的引领者和指导者，他们的教学需求也应被纳入考虑。

每个教师都有自己的教学特点和优势，学校应该根据教师的专业知识、教学经验和授课风格，合理安排教师的上课时间和课程安排。

这样，不仅能够发挥教师的专业优势，提高教学效果，也可以增加教师的工作积极性和满意度。

三、课程设置课程设置是学校排课课程表制定中的核心环节。

学校应该根据学科要求和学生需求，合理设置各类课程。

首先，要确定必修课程的时间和安排，确保学生能够达到国家规定的课程标准。

其次，要根据学生的兴趣和发展需求，设置选修课程，提供多样化的学习选择。

同时，学校还可以开设拓展课程，培养学生的创新思维和实践能力。

总之，课程设置应该兼顾学科知识的扎实性和学生全面发展的需要。

四、时间分配时间分配是学校排课课程表制定中的关键环节。

一个合理的时间分配方案，可以保证学生的学习效果和身心健康。

首先，学校要根据课程设置的要求，合理分配每天的学时。

比如，课程时间安排要分散，避免连堂课过多导致学习压力过大。

其次，学校还要合理分配每天的作息时间，以确保学生能够有足够的休息和娱乐时间。

此外，还要注重一些特殊时间段的安排，如早起课、午休时间，以满足学生的生理和心理需求。

五、课程间隔课程间隔是学校排课课程表制定中的另一个重要环节。

毕业设计（论文）题目: 排课模型分析系名: 信息与计算科学系姓名: 张维骞专业: 统计实务班级: 07731班学号: 20号指导老师: 王科2010年6月摘要排课是现在各个高校都会遇到的问题，高校教学活动中的排课也是对教学活动开展过程中需要的相关资源进行有机的组合，避免由于教学资源的浪费而影响学校教学活动的正常开展。

本文提出了在贪心算法的基础上建立数学模型，以课程人数对教室的需求，结合课程课时、类别对教师资源安排的影响，再加上教师自身及上课时间因素，通过条件筛选及实际的应用，得到各个子问题的局部最优解，再把子问题的解局部最优解合成原来解问题的一个解，在较短得时间里找到一系列比较满意的最优解。

关键词：排课；多因素；贪心算法；数学模型AbstractTimetabling university now will encounter various problems, Timetabling university teaching activities is also carried out in the course of teaching activities related to a combination of organic resources, avoid waste of teaching resources to affect the normal teaching activities carried out.This paper proposes a greedy algorithm based on mathematical models, the number of the classroom curriculum requirements, combined with curriculum lessons, teacher resources category on the impact of the arrangements, together with their teachers and class time factors, and screening and the actual application conditions , each sub-problem by the local optimal solution, then the local sub-optimal solutions of problem synthesis of the original solution a solution of the problem, found in a relatively short time series were relatively satisfied with the optimal solution.Keywords: Timetabling; multi-factor; greedy algorithm; mathematical model目录引言 (1)第1章问题重述、模型的假设及变量说明 (1)1.1、问题重述 (1)1.2、模型的假设 (5)1.3、变量说明 (5)第2章模型建立与求解 (7)2.1建立排课模型 (7)2.2问题一求解 (8)2.3问题二求解 (10)2.4问题三求解 (12)第3章略模型的分析、检验和评价推广 (13)3.1排课模型分析与检验 (13)3.2排课模型的评价及推广 (13)3.3程序的编写和计算 (14)结论 (20)致谢 (21)参考文献 (22)引言排课问题是查找满足多因素约束的“教室—课程—时间—教师”配对。

学校排课的优化模型摘要排课是学校的一项常规工作,也是学校教育教学管理过程中不可或缺的重要环节。

在学校教务管理工作中，课程的编排是一项十分复杂、棘手的工作。

它不仅关系到学校教学工作的正常运行、教学效果、学生发展及教学资源的整合和科学高效的利用,而且关系到教师的身心健康和教育教学质量。

排课需要考虑时间、课程、教学区域、教室、班级、教师等多种因素。

本文就此类问题进行讨论，并根据题目要求深入分析后，将该问题归结为优化问题，确定了“将教师、课程、教室三个因素优化组合，并并分配到课表上的不同时间段上，形成最终课表”的解决方案。

首先建立各因素间关联关系，根据各因素间约束关系的不同，将多重约束条件为硬约束（强制要求）和软约束，写出各因素间的目标函数。

其次，为课表上四个时间段随机分配课表，以0-1规划方法分别将教师、教室分配到课表上的不同时间段上。

最终，形成了一份尽可能多的满足课程、教师、教室的要求的课表。

本文采用0-1规划法、逐级优化法，并考虑多重约束条件，形成了一个良好的排课模型。

并根据题目给出的数据，通过计算机编程，进行模型验证，求出了所需课表。

且在方案合理性分析中用计算机模拟的方法分析了教室的种类对排课结果的影响，最后给出了教师、教室、课程的配置建议。

一．问题的重述在学校的教务管理工作中，课程表的编排是一项十分复杂、棘手的工作。

排课需要考虑时间、课程、教学区域、教室、班级、教师等多种因素。

经优化的排课，可以在任意一时间段内，教师不冲突，授课不冲突，授课的班级不冲突，教室占用不冲突，且综合衡量全校课表在宏观上是合理的。

如何利用有限的师资力量和有限的教学资源，排出一个合理的课程安排结果，对稳定教学秩序、提高教学质量有着积极意义。

某高校现有37个自然班，编号为1..N；教师共有79名，编号为1..M；有教室50间，编号为1..R；有课程数54.课表编排规则：1.同一自然班不在同一时候参加不同教学班的授课；2. 同一教师不能同时参加不同教学班的授课；3. 一个教室不能同时开两门课程；4. 满足课程的教室类型需求；5. 学生人数不能超过教室容量；6. 同一门课程尽量不在同一天开课两次及以上；7. 一个自然班的课程尽量分布均匀到每天；8. 教师上课尽量集中，同时一天尽量不要超过6节，最好4节10. 晚上尽量不排课。

排课算法分析：由于本论文的排课是针对中学课程，学生的上课教室不变，并且一个教室只有一个班级使用，因此学生班级教室可以看成是一个变量。

约束条件 (5)排课要遵循很多约束条件，可以分为两大类，硬约束和软约束。

其中，硬约束为必须满 (5)足的条件，而软约束是为了让排出的课表更合理、更人性化，只要尽量满足。

(5)硬约束包括： (5)教师授课时间冲突，即一个老师在一个时间段只能授一门课程 (5)班级上课时间冲突，一个班级在一个时间段只能上一门课程 ........................................... 5 由于其他条件产生的约束条件，某些课程必须排在早上；某些课只能排在上午的3，4节或者下午，如体育课等等；这些硬性规定的约束条件。

(5)以上条件必须全部遵守，才能排出一个正确的课表。

(5)软约束包括： ........................................................................................................................... 5 一门课程如果一周上多次课，不要在一天内安排多次，并且希望能隔开上满足教师教案的周期性，使其富有人性化 (5)某些教师对上课时间有某些特定喜好。

(5)适应度函数： ................................................................................................................................... 5 遗传算法靠适应度来评估和引导搜索，我们可以采用一种十分自然的的方法来考虑约束条件，即在进化过程中，迭代一次就设法检测一下新的个体是否违背了约束条件。

如果不满足约束条件，则将其作为无效个体出去。

但是不满足约束条件的个体中，可能包含有前面几代的演化过程中保存下来的有效信息，如果出去，重新开始，可能造成资源的浪费，增加演化的时间。

2004年3月内蒙古大学学报(自然科学版)M ar.2004第35卷第2期A cta Scientiarum N aturalium U niversitatis N ei M ongo l V o l.35N o.2 文章编号:1000-1638(2004)022*******课表的多指标数学模型及解决方法Ξ张春梅1,行　飞1,梁治安2(1.内蒙古大学理工学院,呼和浩特010021;2.上海财经大学应用数学系,上海200433)摘要:课程表问题又称时间表问题(ti m etable p roblem),是一个多指标的优化决策问题,也是组合规划中的典型问题.对已有的时间表问题进行探讨,并研究其数学模型及解决方法.关键词:时间表问题;遗传算法;多指标决策中图分类号:O221.7 文献标识码:A1　排课问题的提出 一所学校为了保证其正常的高水平教学质量,必须制定一套严密、规范的教学计划,并严格执行.课程安排在学校教学计划中又处于核心地位.合理准确的课程表对提高教学水平至关重要.2　排课问题的实质 课程表问题又称时间表问题.课表编排是一个多指标的优化决策问题,是组合规划中的典型问题.课程表的编排就是解决对时间和空间资源争夺而引起的冲突.70年代中期,S.Eveo等人论证了课表问题是N P完全类问题〔1〕,之后很多人尝试采用各种方法对此问题求解.但由于课表问题所涉及的信息较多,并且求课表问题最佳解的时间复杂性是课表规模的指数级,所以对于有一定规模的课表问题,一般采用求较佳解的算法.3　课表的数学模型及约束条件3.1　排课问题的形式化描述在课表编排问题中涉及到班级、教师、时间、课程、教室等五个相互制约的因素.分别用以下集合表示:课程集合　s={s1,s2,…,s n};时间集合　t={t1,t2,…,t n3};班级集合　c={c1,c2,…,c n1};教室集合　r={r1,r2,…,r n4};教师集合　p={p1,p2,…,p n2}时间和教室的笛卡尔积为:N=T×R={(t1,r1),(t1,r2),…(t n3,r n4)},N中的元素称为时间—教室对.课表问题的求解过程就是对任何s i=(i=1,…,n)∈S寻找一个合适的老师P j(j=1,2,…,n2)∈P和合适的时间—教室对(t1,r m)∈N(l=…n3,m=1,…n4),在安排时不能发生冲突,同时尽量满足经验常识.3.2　课表问题的冲突情况:1)同一时间,一个教师同时上一门以上课程;2)同一时间,一个班级同时上一门以上课程;3)同一时间,一个教室同时上一门以上课程;4)选课人数大于当前指定的教室的最大容量.3.3　须满足一些经验常识1)一门课在一周内分散安排,提供可引导性学习环境;2)保留一些特殊的时间,如户外活动;3)一周多学时的同一门课应尽量安排在一个教室(方便教师及学生);4)尽量安排在好的教学时间点(如上Ξ收稿日期:2003201220基金项目:国家自然科学基金资助项目(10261005);内蒙古大学青年科学基金资助项目(ND0204)作者简介:张春梅(1970～),女,内蒙古乌盟人,内蒙古大学理工学院硕士,讲师.041内蒙古大学学报(自然科学版)2004年午比下午好);5)安排到教室中的人数应尽量和教室的大小吻合,一方面资源合理利用,另外教学效果也好,因此一个好的时间表就是一个无冲突且能更多地满足经验常识的安排.4　已有的排课问题的解决方法4.1　基于人工智能原理李明〔2〕给出一个实用的大学课表编排模型,问题模型定义如下:定义1　排课表问题中基本时间表计划问题:设“可安排教学时”集H,“课程”集L( L =n L),“学生”集S( S =n S)组成小组{S i}(i=1,2,…,n l)(S=S1∪S2∪…∪S nl,S i∩S j不一定为空集),“教师”集T,对于每个学生S ij∈S i(教师t∈T),有一个“空闲时间”集A(s ij)ΑH(A(t)ΑH);对于每门课程l∈L,有一个“可安排时间”集A(l)ΑH,并且对于每一三元组(s i,t,l)∈{S i}×T×L,有一个“要求教学时间”数目R(s i,t,l)∈Z+0　(其中Z+0表示非负整数集),求完成所有课程的时间表,即求函数f:({s i}×T×L×H)→{0,1},(其中f(s i,t,l,h)=1表示学生组s i教师t在时间h内上课程l),使得:(1)仅当h∈(∩A(s ij))∩A(t)∩A(l)时,f(s i,t,l,h)=1;(2)对于每个h∈H和s i,t∈T,至多有一个l∈L满足f(s i,t,l,h)=1;(3)对于每个h∈H和s i,lt∈L,至多有一个t∈T满足f(s i,t, l,h)=1;(4)对于每个h∈H和t∈T,l∈L,至多有一个s i满足f(s i,t,l,h)=1;(5)对于每个三元组(s i,t,l)∈{S i}×T×L,恰好有R(s i,t,l)个h∈H满足f(s i,t,l,h)=1定义2　最小时间约束条件集:称定义1中条件(1)～(5)为排课表问题须满足的最小时间约束条件集.定义3　(教室)资源分配问题:设有“教室”集C,每个教室c∈C均满足一定条件A(c),且时间表已经安排好.要求:在一定的约束条件下为每个h∈H且满足f(s i,t,l,h)=1的所有三元组(s i,t,l)∈{S i}×T×L分配教室C.算法主要思想是通过引入一个规则库(知识库),来有效地处理各种复杂约束条件,并在这个规则库的指导下,搜索满足条件的时间集.由于搜索是在规则库的指导下进行的,所以称这个算法是基于智能的.安排好时间表后,进行教室资源的分配.洪力奋〔3〕等用人工智能的原理及专家系统知识构造出了类似的数学模型及有关编排算法,对排课的死锁问题进行了处理.主要设计了两个推理机,一个推理机是根据课程模式要求,根据既定规则找出合适的时间与教室.第二个推理机解决死锁问题而设置(所谓死锁即规则遍历完,仍存在时间冲突或教室冲突).4.2　利用集合的概念及其相关运算董艳云等人〔4～5〕在分析排课所遵循的基本原则和模糊性原则的基础上,定义了课元之间关于教师的相关关系和关于自然班的相关关系.提出以课元相关运算和候选时空片计算为核心的计算机排课算法,其算法描述如下:令C cou表示排课课元的集合,令T T EA,C CL A,R ROO和S SL I分别表示参与排课的教师、班级、教室和时间片的集合.此外,用C T Y={0,1,2,…}表示课元的课程类型集合,其中类型0的课元为必修课或必选课,对同一自然班,这类课的排课时间不允许与其它课冲突,其它类型的选修课按允许时间冲突的课元子集归类.1)课元的相关关系计算.假定用F T:C COU→T T EA描述课元任课教师集合,用F C:C COU→C CL A描述课元的自然班集合,则课元的相关关系定义如下:定义　课元关于教师的相关关系R T:C COU→C COU为{v} F T(u)∩F T(v)≠ (1)R T(u)=∪v∈C COU 课元关于自然班的相关关系R C:C COU→C COU为{v} F C(u)∩F C(v)≠ (2)R C(u)=∪v∈C COU式(1)和(2)中:u∈C COU,R T(u)的物理意义表示课元u的任课教师所担任的所有课程;R C(u)的物理意义表示课元u的上课班所上的所有课程.2)候选时空片计算.假定用F CT:C COU→C T Y描述课元的课程类型集合,用F CR:C COU→R T Y描述课元可选的教室类型集合,用F CS :C COU →C S I 描述课元所需的最小教室容量,用F R T :R ROO →R T Y 描述教室的类型,用F R S :R COU →R S I 描述教室容量,用F S :C COU →S SL I 表示课元已分配到的时间片集合,用F S R :C COU →S SL I ×R ROO 表示课元已分配到的时空片的集合.由排课的基本原则(1)和(2)可知,课元u ∈C COU 可选用的时间片取决于它的相关课元已分配到的时间片及课程类型,即A S (u )=S SL I -∪v ∈R T (u )F S (v )-∪v ∈R C (u )F S (v ) F CT (u )=0∨F CT (u )≠F CT (v )(3) 由排课的基本原则(3)可知,课元u ∈C COU 可选用的教室A R (u )取决于该课元所要求的教室类型和容量,即 A R (u )=∪r ∈R TRO{r } F R T (r )∈F CR (u )∧F CS c (u )ΦF RS (r )(4) 所以,课元u ∈C COU 可选用的时空片(候选时空片)A R (u )为A S R (u )=∪s ∈A s (u )r ∈A R (u )(s ,r )-∪v ∈C COU F S R (v )(5) 本算法最后通过关系数据库实现.课元数据库T EA CH .DB F ,班级数据库CLA SS .DB F ,教室数据库ROOM .DB F .按照上述排课算法及软件实现方法,已成功地开发出高校计算机排课软件.文献〔5〕提出的算法借鉴了资源管理的思想,使用以集合为元素的矩阵建立了问题的数学模型.时间模型定义如下:排课一般以一个学期作为一个独立的阶段,假定一个学期由Z 周组成(例如Z =18),每周可以使用的授课时间为S 个单位时间(如S =24),则一学期可以使用的总授课时间为N =S ×Z .这里S 和Z 可以作为系统参数.整个有效的时间域可以定义为集合K ={1,2,…,n -1,n },教师、班级和教室被占用的任何时间是K 的一个子集.算法的实现是以集合运算为基础的.该算法是动态、次优的,但时间和空间复杂性几乎和问题规模成正比.4.3　应用专家系统〔6〕文中将传统的数据库和专家系统结合起来,充分发挥各自的长处,达到优势互补的目的.系统将拥有的几方面的知识:教室、班级、课程、教师、时间等详细资料存入数据库中,将排课中的一些限制条件放入规则库中,为了便于规则的推理和编辑,所有的规则采用统一格式:对象 属性 属性值 要求 置信度对象有教师、班级、教室;教师的属性有编号、名称、职称,班级的属性有编号、年级、系别,教室的属性有编号、名称;要求包括时间或教室要求两种;置信度是一个0～1的数,等于1表示此规则是必须满足,大于0.5表示最好满足,等于0表示一定不能,小于0.5表示最好不能这样.专家系统使用排课专家的大量排课知识策略(这里的策略指把求解过程看成对一种与或图的搜索),通过查询数据库和进行规则推理,灵活的编排出符合要求的课表.4.4　分批与或图与匈牙利算法结合从前面课表的形式化描述中可看到,课表问题可看作匹配问题.其数学模型如下:把课表看成是有n 门课,怎样分配到n 个时间2教室对中的问题.需要系数矩阵,其元素c ij >0(i ,j =1,2,…,n ),表示指派第i 门课到第j 个时间2教室对时的期望值,该期望值反映教师、学生和学校根据教育的特点对该时间上某门课的观点;解题时还需引入变量x ij ,其取值只能是1或0,即x ij =1 (当指派第i 门课到第j 时间2教室对时)x ij =0 (当不指派第i 门课到第j 时间2教室对时)问题要求极小化时,数学模型为m in Z =6n i =16n j =1c ij x ij 约束条件为6n i =1x ij =1 (j =1,2,…,n );6n j =1x ij =1 (i =1,2,…,n );x ij =1或0(i ,j =1,2,…,n ) 该问题较好的解法是用匈牙利算法.该算法的主要思想是基于下面的定理:如果系数矩阵[c ij ]的每一行元素中分别减去(或加上)一个常数u i (称为该行的位势),从每一列元素中分别减去(或加上)一个常数v j (称为该列的位势),于是得到新的矩阵[b ij ],其中,第i 行第j 列141第2期张春梅等　课表的多指标数学模型及解决方法241内蒙古大学学报(自然科学版)2004年元素为b ij=c ij-u i-v j,则结果[b ij]的最优解等价于矩阵[c ij]的最优解.甘肃工业大学的魏平等人〔7〕采用分批与或图和分批优化的匈牙利算法相给合的方法实现.如把上课时间、场地、设备和连续上课时间超过两节的具有特殊要求的课程分为一批,采用搜索算法,且优先排课,然后对余下的课采用分批优化匈牙利算法和分批与或图搜索法相结合进行排课,一批中限制条件较多时采用匈牙利算法,其他采用分批与或图算法,从而提高编排效率.4.5　分组优化决策算法和定额匹配算法在课表的编排问题中,课程、时间、教室是三个相互制约的因素,1)课程定义:课程是由开课教学单位按教学任务书的要求指派讲员构成的一个教学班,课程的记录类型由下面字段定义:〈课程〉∷=〈课号〉〈课名〉〈讲员〉〈周学时〉〈人数〉〈班集合〉〈排课要求〉设L={l l-课程},L表示待排的课程任务集合.Πl1,l2∈L,若(l1〈讲员〉)=(l2〈讲员〉)或(〈班集合〉)∩(l2〈班集合〉)≠ ,称课程l1与l2相关,记作l1・l2=1,否则称无关,记作l1・l2=0.相关课程将争夺周课表上的时间.2)时间、时间模式定义　设T={t t—周课表上的时间}表示周课表上的时间集合,且若t={Ρ1,Ρ2,…,Ρn},叫做个数为n的时间组.若t中的时间个数n及Ρi在表上的时间间隔分布符合某种上课的学时机制,则称t为周学时为n的时间模板(或时间模式).下文中用t(l)表示课程的一个时间模板.若l1・l2=1,且t(l1)∩t(k2)≠ ,则称两个相关课程的时间模板冲突,记作t(l1)・t(l2)=1,否则,为不冲突,记作t(l1)・t(l2)=0.不相关课程的时间模板恒为t(l1)・t(l2)=0.3)教室、“时间教室”定义:教室的记录类型由下面字段定义:〈教室〉∷=〈教室名〉〈房间号〉〈人数〉〈功能〉.假定周课表上任何一个时间均有k个教室可供选用.即ΠΡi∈T则时间Ρi上的k个教室为r(Ρi) ={r1(Ρi),r2(Ρi),r3(Ρi),…,r k(Ρi)},用r j(Ρi)表示时间Ρi的第j个教室,通常,排课时总是先确定课程l的时间模板,再选教室,课程l的“时间教室”记为r(t(l)),其意义为:r(t(l))={r j(Ρi) Ρi∈t(l),i=1,2,…,n;n=(l〈周学时〉);r j(Ρi)∈r(Ρi)}其中t(l)为课程的合适的时间模板,并且每个r j(Ρi)均是在时间Ρi满足课程l的人数(区间)要求的某个教室.除非时间相连,且该课要求占用同一教室,否则时间教室中的r j(Ρi)与r j+1(Ρi+1)不必相同.l1,l2∈L,若t(l1)与t(l2)有相同的时间,且在这相同时间r(t(l1))与r(t(l2))存在相同的教室,则称课程的“时间教室”选择冲突,记作:r(t(l1))・r(t(l2))=1,否则为不冲突,记为r(t(l1))・r(t(l2))=0.无论l1,l2是否相关,均必须满足r(t(l1))・r(t(l2))=0.4)课程安排、课表定义:Πl∈L,选择l的不冲突时间模板(在课程相关的意义下时间模板不冲突)和分派不冲突“时间教室”,称为构造课程l的一个课表安排,记作l(l),l(l)也是记录类型:l(l)∷=〈l〉〈t(l)〉〈r(t(l))〉课程安排集合用D={l l=l(l),l∈L}表示.l1,l2∈D,l1=l(l1),l2=l(l2),在课程l1、l2相关意义下,保证t(l1)・t(l2)=0,并且还满足r(t(l1))・r(t(l2))=0,则称D为一个合适的排课集合.即D中的课程安排,两两教室必须不冲突;若课程两两相关,D中的课程安排还必须两两时间不冲突.王祜民等人〔8～9〕将课程集合中按优等级逐次分组,每组用优化决策方法排课,这是一种在启发式准则指导下,逐次的、向前的构造性排课过程.通过分组优化决策算法,先难后易逐组编排课表.那些学时多,班数多的大合班课是最难编排的课程,要先将这些课组编排到课表中去,形成称为D e的阶段课表.而定额匹配算法是解决某些特殊课程(组)的自动编排问题.所谓的特殊课,如体育课、按水平分班的外语课等,该种课程的班集合中的班数目大,因而排课难度与大合班课类似,但班级可任意组合在一起,排课时可动态挑选班组合,这使排课有更多的选择机会.4.6　作为满意约束问题处理把排课问题当作满意约束问题,对此已有多种解决方法,如图着色〔10〕,在图着色的示例中计算时间相当长,因为一旦指定的值失败就需做大量的反跟踪,原因是没有办法避开不可行解.4.7　启发式算法用启发式算法〔11〕如禁忌搜索〔12〕、模拟类似于自然界金属的退火过程的模拟退火〔13〕、类似于自然界种群遗传的遗传算法〔14,15〕;在算法的具体实现过程中,所采用的方法有用事先做好的特殊操作去产生一个可行解;也有的在适应度函数中并入惩罚;或采用修复程序过滤不可行基因;也可采取将问题中的一些约束条件消除或弱化的方法重新对问题给出表述等几种.A .co lo rn l 在高中课表的启发式算法中以特定的高中课表为例给出了模拟退火(SA )、禁忌搜索(T S )、遗传算法(GA )三种算法的比较结果〔16〕.他认为T S 是最好的算法,GA 产生的解比SA 好.但是最终用户相对于SA 和T S 更易接收GA .4.8　遗传算法意大利的A .co lo rn i 等人用遗传算法求解高中课表的安排问题〔16〕.文中将每位老师的活动作为基因,这些活动包括上课、休息、写论文等,分别用字符0、1…9、a 、b 、…p 表示.意大利高中每周上课30h ,以时间点为列,所有老师为行组成二维染色体,适应度函数定义为最小化总代价,其中组织代价指临时教学岗位没有安排老师,个人代价指不想休息时休息,教训代价指一周的几天内同一门课集中在一起;姚新的教室安排问题,主要优化的是教室的合理利用〔15〕;另日本的Sigeru .O 采用遗传算法中加入控制约束的方法解决大学课表安排问题〔14〕;用自适应的遗传算法求解大学课表安排问题〔17〕,根据大学课程安排的特点,将课程分为必修课P 、选修课Q 两类.并对两类课分别给出其染色体编码和适应度函数.在P 类课中适应度函数考虑了两点:第一点是要使所安排的课尽可能占用好的时间点,所以我们对一天的四个时段分别给出了期望值:8:00----12:00为12;10:00----12:00为8;2:00----4:00为4;4:00----6:00为1.在这种定义下我们所涉及的20个时间点的期望值如表1所示:表1　时间的期望值Table 1　preferences of ti m eslot时间点T 1T 2T 3T 4T 5T 6T 7T 8T 9T 10T 11T 12T 13T 14......T 20期望值128411284112841128 (1) 第二点如果某一门课多于1个时间片(4学时或多于4学时),或一个教师带两门以上的课,都希望能在时间上分散安排,这样从学生接收知识和教师的教学效果上都是很好的.我们用编号相同的两课的时间差来描述这种离散度并给出相应的期望值.如表3所示:表2　课程离散度期望值Table 2　preferences of i n terval degree of courese两课时间差1,192,3,17,184,5,15,166,7,13,148,9,10,11,12期望值0241016 所以定义适应度函数f (g )=6ni =1(g (t (S i ))+h (S i ))(g ),其中g (t (s i ))表示课程所占时间片的期望值,h (s i )表示课程离散度,f 即为所有课程时间期望值与课程离散度之和.在Q 类课中主要考虑的是让教室有效合理地得到利用.因此我们的适应度函数定义为:g (x )=A ×6n i =11l (r (S i ))-Q (S i ) +1(x ) 其中Q (s i )表示课程s i 的选课人数,表示课程s i 所在教室的大小.该式分母中加1是为了避免房间大小与选课人数正好相等的情况出现,从而产生O 分母.杂交概率和变异概率的选取在相当大程度上影响算法的收敛速度和近优解的质量,为加快GA 的搜索效率和有效地防止陷于局部最优解,本文采用自适应的杂交概P c 和变异概率P c =k 1sin (Π2×f m ax -f ′c f m ax -f avg )　f ′c Εf avg k 2 f ′c <f avgPm =k 3sin (Π2×f m ax -f m f m ax -f avg )　f m Εf avg k 4 f m <f avg 其中:0<k 1、k 2、k 3、k 4≤1是群体的最大适应度函数值,f avg 是群体的平均适应度函数值,f ′c 是进341第2期张春梅等　课表的多指标数学模型及解决方法441内蒙古大学学报(自然科学版)2004年行杂交的两个染色体串中适应度函数值较大者,f m是变异串的适应度函数值.由自适应的杂交概率和变异概率的定义可以看出,定义的形式满足:0ΦP cΦ1;0ΦP mΦ1,另外,当f′c=f m ax时,P c=0;f m=f m ax时,Pm=0.这表明当前代的最优个体不经过杂交操作和变异操作而直接进入到下一代.5　结束语 该文给出了排课问题的数学模型及解决方法,其思想和方法对解决类似的优化组合问题也有一定的借鉴作用.参考文献:[1]　Garey M R,Johnson D S.Co m p u te and Intractability:A Gu id e to the theory of N P co m p leteness[M].San fran2cisco:W.H,F reem an Co.,1979.[2]　李明.一个基于智能化搜索的排课表演算法及其client server实现[J].现代计算机,1997,59:21～22.[3]　洪力奋.基于人工智能原理的大学课表编排模型[J].合肥工业大学学报(自然科学版),1999,22(4),101～104.[4]　陈洁.学校教务部门排课问题的数学模型及算法[J].管理信息系统,1999,3:53～56.[5]　董艳云,钱晓群,张宇舒.基于课元相关运算的高校排课算法[J].甘肃交通大学学报,1998,33(6):670～673.[6]　周建新,王科俊等.课表编排专家系统[J].计算机应用,2000,20(5):76～78.[7]　魏平,熊伟清.计算机辅助课表编排技术的研究[J].甘肃工业大学学报,1997,23(4):76～81.[8]　王祜民,赵致格.排课表问题中的分组优化决策算法[J].控制与决策,1999,14(2):109～114.[9]　王祜民,赵致格.时间表问题中的定额匹配算法[J].清华大学学报,1998,38(6):8～11.[10]　W erra D de.A n Introducti on to T i m etabling[J].E u r.J.Op nl.R cs.S oc,1985,48(11):1178～1190.[11]　W righ t M.Schoo l T i m etabling using H euristic Search[J].J.Op nl.R cs.S oc,1996,47(3):347～357.[12]　H ertz A.F inding a feasible course schedule using tabu search[J].D iscrete A pp lied M athe m atics,1992,35(2):250～270.[13]　A bram son A.Constructing schoo l ti m etables using si m ulated annealing:Sequential and Parallel A lgo rithm s[J].M anag e m ent S cience,1991,37(1):98～113.[14]　Safaai D,Sigeru O.Inco rpo rating constraint p ropagati on in genetic algo rithm fo r university ti m etable p lanning[J].E ng ineering A pp lications of A rtif icial Intellig ence,1999,35(2):241～253.[15]　L uan F,Yao X.So lving real2w o rld lecture room assignm ent p roblem s by genetic algo rithm s,Comp lexity Inter2nati onal[J].A n E lectronic J ou rnal of Co m p lex S y ste m R esearch,1996,3:87～90.[16]　Co lo rni A,M arco.do rigo,M aniezzo V.M etaheuristics fo r h igh schoo l ti m etabling[J].Co m p u tational Op ti2m iz ation and A pp lications,1998,(9):275～298.[17]　张春梅,行飞.用自适应的遗传算求解大学课表安排问题[J].内蒙古大学学报(自然科学版),2002,33(4):459～464.(责任编委　孙　炯) T he M u lti2target M athem atical M odeland So lu ti on of T i m etab le P rob lemZHAN G Chun2m ei1,X I N G Fei1,L I AN G Zh i2an2(1.Colleg e of S ciences and T echnology,N ei M ong ol U n iversity,H ohhot010021,P R C;2.D ep a rt m en t of A pp lied M a the m a tics,S hang ha i F inance and E cono m ics U n iversity,S hang ha i200433,P R C) Abstract:T i m etab le p rob lem is a m u lti2target op ti m ized decisi on p rob lem and typ ical p rob lem in adm in istrati on and p lann ing.Som e ex isting m athem atical m odels and so lu ti on s of the ti m etab le p rob lem are discu ssed.Key words:ti m etab le p rob lem;genetic algo rithm s;m u lti2target decisi on。

课程设计排序和算法分析一、教学目标本课程旨在通过排序和算法分析的学习，让学生掌握排序算法的基本原理和实现方法，培养学生解决问题的能力，提高学生的逻辑思维和编程实践能力。

具体目标如下：1.理解排序算法的概念和作用。

2.掌握常见的排序算法（如冒泡排序、选择排序、插入排序等）的原理和实现。

3.理解算法分析的基本概念和方法。

4.能够运用排序算法解决实际问题。

5.能够分析算法的时间复杂度和空间复杂度。

6.能够运用编程语言实现排序算法。

情感态度价值观目标：1.培养学生对计算机科学的兴趣和热情。

2.培养学生解决问题的积极性和主动性。

3.培养学生团队合作的意识和能力。

二、教学内容本课程的教学内容主要包括排序算法、算法分析和编程实践。

具体安排如下：第1-2节：排序算法的概念和原理。

介绍排序算法的作用，讲解冒泡排序、选择排序和插入排序等常见排序算法的原理和实现。

第3-4节：算法分析的基本概念和方法。

介绍算法分析的目的，讲解时间复杂度和空间复杂度的概念和方法。

第5-6节：编程实践。

让学生运用所学的排序算法解决实际问题，培养学生的编程能力和解决问题的能力。

三、教学方法为了提高学生的学习兴趣和主动性，本课程将采用多种教学方法，包括讲授法、讨论法、案例分析法和实验法等。

1.讲授法：通过讲解排序算法的原理和实现，让学生掌握基本概念和知识。

2.讨论法：通过分组讨论，让学生深入理解排序算法的优缺点和适用场景。

3.案例分析法：通过分析实际问题，让学生学会运用排序算法解决实际问题。

4.实验法：通过编程实践，让学生掌握排序算法的编程实现和算法分析。

四、教学资源为了支持本课程的教学内容和教学方法，我们将选择和准备以下教学资源：1.教材：《数据结构与算法》。

2.参考书：《算法导论》、《排序算法与应用》等。

3.多媒体资料：PPT课件、教学视频等。

4.实验设备：计算机、编程环境等。

5.在线资源：相关论坛、博客、教程等。

五、教学评估本课程的教学评估将采用多元化的评估方式，以全面、客观、公正地评估学生的学习成果。

课程表的空间模型及排课算法分析摘要本文在课程表问题分析的根底上，建立了课程表的空间数学模型，并据此模型推出排课算法，建立了排课系统的E-R图，描述了采用软件实现排课的计算过程。

关键字排课算法数学模型E-R图随着计算机的普及，如何利用软件系统来进行课程编排，是各个高校面临的问题。

目前已经有一些比较成熟的排课软件，其大局部作为教务管理系统的一个子系统存在，其排课算法和数据采集效率及排课效率都各不相同，各有特点。

高校课程表排课设计因素多和结构复杂被归结为NP(NndeterinistiPly-ninalplexity)问题。

本文在文献[2]提出的课程表的矢量空间的概念根底上，进一步完善设计及算法，并实现一个更具体可行的排课过程。

课程表的问题，是解决教师、课程、班级、教室、时间的组合问题，这个问题的数学描述是给定一组学生S(S1，S2，……Si)，一组课程(1，2，……j)，一组教师T(T1，T2，……Tk)，一组教室R(R1，R2，……R)，一个时间序列N(N1，N2，……Nn)，问题的求解目的是找出这些序列的每个元素之间的一一对应关系，其中这些元素的组合要满足一定的对应关系。

诸如：①S-之间的对应关系；②T-之间的对应关系；③R-之间的对应关系；④T-N之间的对应关系；⑤S-N之间的对应关系；这些对应关系是主要考虑的限制条件，还有一些次要的限制条件。

这是一个复杂的NP问题，它的求解是一个完整类的求解问题。

在文献[2]中使用代数的矢量空间的概念，将S，，T，N，R中每个组中的每一个元素的组合用5维空间的点来表示，合并S和为一个维度，合并N和R为一个纬度，可得3维空间点阵。

本文引入教学任务概念，如图1所示，本文进一步将空间点阵细化，明确具体开课点在空间上的交点来源及含义。

在T，，S对应的平面上的点定义为教学任务1〔1，S1，1，T1〕，，S坐标上对应的点是班级排课序列，空间点P1，P2即为求的开课的时间和地点。