Menu
毕业论文
计算机论文
经济论文
生物论文
数学论文
物理论文
机械论文
新闻传播论文
音乐舞蹈论文
法学论文
文学论文
材料科学
英语论文
日语论文
化学论文
自动化
管理论文
艺术论文
会计论文
土木工程
电子通信
食品科学
教学论文
医学论文
体育论文
论文下载
研究现状
任务书
开题报告
外文文献翻译
文献综述
范文
图的染色问题在排课表中的应用+文献综述(3)
很明显,在任何正常边色数中,和任一顶点关联的各边必须分配以不同的颜色。由此推之,
参照图1的例子,可知在(2.1)式子中允许出现严格的不等式。而在 是偶图的情况下,等式成立(定理2)[1]
偶图,即二部图,指若图 的顶点集可划分为两个非空子集 和 ,使得任一条边都有一个端点在 中,另一个端点在 中,则称 为二部图(或偶图),记为
下面我们运用边染色的概念以及其基本定理对排课表问题进行求解。
2.2 排课表问题的介绍
2.2.1 排课表问题的背景介绍
在一所学校里,有 位教师 ,…, 和 个班级 ,…, 。已知教师 给班级 上 课时, = 称为
教学
要求矩阵。假定只有 个教室可供利用。要求制订一张完善的课表 ,使得需要的课时数尽可能少(用 表示其中最小者) , 同时在一节课时内最多占用的教室数量也尽可能少(用 表示其中最小者) 。这样的课表称为最优课表。
上述问题,通常称之为排课表问题[6]。
排课表的基本要求是避免冲突,防止教学事故,但由于没有好的算法,在手工排课时,需要付出很多的劳动,即便如此,也不能从理论上保证不会冲突。因此,随着教学资源、师资力量和招生规模的变化,每次需要多大的工作量、多长时间能排出来以及能不能正常安排教学过程都难以定论。在排课表时,需要考虑的约束和资源限制太多,有时即使排出的课表能够使用,也不能保证方案是效果最好的。
冲突限制主要表现在同一时段既不能一个老师给两个班上课(合班除外),也不能有两个老师给同一个班级上课;合班课不能跟小班课冲突,即某个班的小班课不能跟它与其他班的合班课排在同一时段内。资源约束是指实验室和合班教室一般都属紧缺资源,排课时应该针对每个时间段平均分配使用的班级。除冲突限制以及资源的约束外,排课时还应该考虑相邻两次课不能排的太近,排在一天或相邻的两天都不能符合要求。比如每周4个学时的课程,排在星期一、三或星期二、四或星期三、五都是可以的,每周6个学时的课,排在星期一、三、五则是比较理想的。为满足这方面的要求,需要在模型中设计效果优化算法。
排课模型中的关键是避免排课冲突的排课算法。目前大多数算法是模仿手工排课的做法和经验,通过
计算机
反复对比来避免冲突的发生,排课的过程是直接按照排课的习惯进行时间和教室的分配,遇到了冲突再设法调整,而每次的调整都可能造成新的冲突,不能保证最优解收敛的速度。因此效率低下。另外这种方法不能保证最终方案最优。
解决排课表问题,可以运用图论中的边染色。将教师 与班级 之间的授课关系转化成二部图的边染色[7],如下图2所示每一个对应的授课用一条边来表示, 要给 班级上 节课,那么 与 之间用 条线连接,然后用正常的边染色。使用同一种颜色的边代表可以在同一课时进行。从而安排出一个课表计划。
图2
边染色理论可以从根本上避免手工排课的不确定性,它可以在保证不冲突的前提下,分配授课时段,也可以对方案进行优化。我们用常用模型对高校排课问题进行简化和边染色计算。
2.2.2 排课表问题是一个NP完全问题
设有 位教师和 个班级和 个教室,其中教师 要给班级 上 节课。应如何在最少节次 内排完所有的课。这问题可转化为:给定一偶图 其中 ={ , ,…, }, ={ , ,…, }, ={ } 与 间有 条边,应如何将边集 划分成互不相交的 个匹配( ,…, ),且使 为最小?由边染色问题知,只要求出偶图 的 = =∆-边着色即可。
共4页:
上一页
1
2
3
4
下一页
上一篇:
整函数的阶型与零点+文献综述
下一篇:
线性回归中最小二乘估计的改进
浅谈中学数学函数最值问题的求解方法
基于决策树算法的篮球联赛预测
数形结合在中学数学中的...
浙江省工业企业发展的因子分析
中美小学数学课堂教学的比较
杭州历年中考三角形的题型分析
论数形结合在中学数学教育中的应用
C#学校科研管理系统的设计
公寓空调设计任务书
AT89C52单片机的超声波测距...
10万元能开儿童乐园吗,我...
国内外图像分割技术研究现状
神经外科重症监护病房患...
承德市事业单位档案管理...
中国学术生态细节考察《...
医院财务风险因素分析及管理措施【2367字】
志愿者活动的调查问卷表