基于排课问题的优化模型毕业论文

《基于排课问题的优化模型毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、毕业论文基于排课问题的优化模型一摘要排课问题是一个多目标组合规划问题。对于目标规划问题要找到最优解，必须要足够的约束条件来实现。对于多目标的组合规划问题，不同的目标集对应的约束条件是不相同的，并且目标集之间是相互影响的，所以，从实际出发，寻找出与目标集对应的约束条件建立模型是解决排课问题的一个关键。我们首先罗列出问题中所有的约束条件，再对所有的约束条件划分成三类：基本约束条件，硬性约束条件和软约束条件。我们将同一教室不能同时安排两门或两门以上的课程，同一班不能同时安排两门或以上课程，将这些约束条件视为基本约束条件，他们是排课问题的前提条件，是我们在建立模型时必须首先考虑的。而将学生班人数应不小

2、于分配给教室的座位数；每个教室的周课时总数不大于30（假设一周最多有30节课）；将有多媒体需求的课程安排到有多媒体配置的教室中去等，这些约束条件视为硬性约束条件，它们作为衡量排课方案切实可行的标准，在建立模型时这些约束条件一定要满足。而将占用教室尽可能少，同一门课的授课尽可能在同一教室，人流通量尽可能少，授课时间尽可能均匀等，这些约束条件视为软约束条件，他们作为衡量排课优劣的准则，在建立模型时这些约束条件要尽量满足。对于上述约束条件，我们先将其转化成数学表达式进行分析，针对上述的基本约束条件和硬性约束条件，我们采用分支限界法将教室划分成六类，将课程也划分为六类并与相应的教室相匹配，形成六张“教

3、室----课程”匹配表。针对上述中的软约束条件我们分别建立模型一和模型二，模型一采用0-1规划的方法，可以同时满足占用教室尽可能少，同一门课的授课尽可能在同一教室。模型二采用0-1二叉树回溯法，不仅可以满足模型一的所能满足的条件，还能满足人流通量尽可能少等条件。待模型求出结果后再做简单手工调整即可满足授课时间尽可能均匀的条件。在求解模型时，我们将数据复制到数据库中，通过JAVA编程从数据库中将数据取出进行处理，并通过分支限界法将与同一类教室匹配的课程分别存储在单独的链表中。再分别利用模型一、模型二对约束条件进行求解，先是通过LINGO软件编程对模型一进行求解，但求出的解并不能较好的满足人流通量

4、尽可能少的条件，并且工作量的大小与数据量的大小有关，当数据量很大时便不适用。故我们改用0-1二叉树回溯法，通过JAVA编程求解出比较满意的结果。为了方便非相关人员使用该模型，我们特意为模型编制了图形界面，通过点击功能按钮就能使用该模型，使得该模型易于推广。在模型检验和误差分析中，我们通过数据库检索的方法也得到了一份结果，并将其与用模型求解的结果进行比较，验证了模型的可行性，并作出了合理的误差分析。最后，我们对模型的优缺点进行了评价，并对模型做了推广。关键字：多目标组合规划分支限界法0-1规划回溯法数据库检索二问题分析该问题是一个多目标规划问题，不同的目标集对应的约束条件是不相同的，并且目标集之

5、间是相互影响的，我们从实际出发，寻找出与目标集对应的约束条件建立模型。我们首先罗列出问题中所有的约束条件，再对所有的约束条件划分成三类：基本约束条件，硬性约束条件和软约束条件。我们将同一教室不能同时安排两门或两门以上的课程，同一班不能同时安排两门或以上课程，将这些约束条件视为基本约束条件，他们是排课问题的前提条件，是我们在建立模型时必须首先考虑的。而将学生班人数应不小于分配给教室的座位数；每个教室的周课时总数不大于30；将有多媒体需求的课程安排到有多媒体配置的教室中去等，这些约束条件视为硬性约束条件，它们作为衡量排课方案切实可行的标准，在建立模型时这些约束条件一定要满足。而将占用教室尽可能少，

6、同一门课的授课尽可能在同一教室，人流通量尽可能少，授课时间尽可能均匀等，这些约束条件视为软约束条件，他们作为衡量排课优劣的准则，在建立模型时这些约束条件要尽量满足。我们可以先将学生班与该班所要上的课相关联；接着对教室进行分类，以有无多媒体，以及座位数的不同将教室分为六大类：有多媒体教室和无多媒体教室；然后根据教室的座位个数将教室分作六类：有多媒体且座位数不小于120的教室，有多媒体且座位数大于80且小于120的教室，有多媒体且座位数不大于80的教室，无多媒体且座位数大于120的教室，无多媒体且座位数大于80且小于120的教室，无多媒体且座位数小于80的教室。再对课程进行分类，以课程是否有多媒体

7、需求为标准将所有课程划分为两类，以课程对应的学生班人数不小于分配各教室的座位数并且尽可能的安排在座位数较少的教室中为标准将课程继续划分，一共分为为六类。再将课程分配到具体教室中去，这时应考虑每个教室的周课时总数不大于30。然后按班级顺序将每个班的课程填充到该课程所属的那类教室中去，当一个教室填充满或不能再填充时，再继续填充下一个教室。这样在无多班一起上课的情况下，可以做到占用教室数最少，由于是按班