带有冗余量的机房排课问题算法设计与实现

摘要

排课历来都是高校教学事务管理中一项非常重要的工作。近年来，由于信息技术的飞速发展，计算机已经开始渗透到高校的各门课程中，因此如何安排机房的使用时间，提高高校计算机机房的利用率，已成为安排机房课程表的重点。机房课程表的安排与传统教室课程表的安排显著不同，因为对于计算机这样一个高度复杂精密的试验设备，在安排课表时必须考虑其故障率因素，要预留出一定数量的冗余机器，保障每个上机试验的学生有机器可用。当一门课程中参加上机实验课的学生人数较多时，在安排上机实验课的课表时，除了要考虑机器冗余数量以外，还要注意机房规模大小、理论课授课班中各自然班的上机时间同步性、以及各机房中上机人数的均衡性对授课效果的影响等因素。在目前已有的各种排课设计方案中，多数是针对普通教室的，而没有考虑实验室设备冗余量需求等情况。随着高校招生规模的扩大，需要使用计算机的课程日益普及，设计这类带有冗余量的机房排课算法有更为重要的理论价值及实际意义。
　　本文根据安排上机实验课课程表时出现的情况和问题，分析总结了机房排课过程中的必要需求，为了算法设计的需要，对相关需求的概念给出了数学描述，如机房机器冗余度，机房故障率，差值比例等。为了高效地获得机房排课方案，综合运用图论网络流理论、模糊聚类分析和模糊评价方法设计排课算法，具体过程如下：
　　首先根据课程需求情况和数量将排课过程分解为了若干层，在每一层中，根据本层要满足的需求，利用网络流模型获得了所有可行的排课方案，然后运用模糊聚类方法对所得方案进行分类，并选取每一类中最具代表性方案进入下一层，当所有层遍历完成后，采用模糊综合评价方法对所得方案的冗余度等评价指标计算了评判函数值，当评判函数值符合要求时，所得方案即为所得近似最优排课方案，否则回溯至上一层重新选取其他类中方案，但若某层中所有类的方案均已搜索完成仍未获得近似最优排课方案，则继续回溯至上一层重新选取其他的类继续搜索。
　　本文以哈尔滨工程大学2012年线性代数上机实验课课表作为实验对象，实现了上机实验课课表的自动生成，并将所得方案与原手工排课方案进行对比。结果表明，与原排课方案相比，本算法生成排课方案的评判函数值明显更高。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1课题背景

1.2课题的研究意义及方法

1.3课题的国内外研究现状

1.4论文的主要工作

第2章 机房排课需求分析

2.1保证正常授课秩序的需求

2.2提高授课质量的需求

2.3机房机器冗余度的需求

2.4本章小结

第3章 两种模糊数学方法在机房排课中的应用

3.1排课方案的模糊聚类分析方法

3.2排课方案的模糊综合评价方法

3.3本章小结

第4章 一种图论方法在机房排课中的应用

4.1图论简介

4.2排课的网络流模型

4.3 本章小结

第5章 机房冗余度优化排课算法设计与实验

5.1算法设计

5.2带冗余量排课问题分析

5.3具体步骤分析

5.4实验结果对比

5.5本章小结

结论

参考文献

攻读硕士学位期间发表的论文及取得的科研成果

致谢