均匀设计在排课问题中的应用

《均匀设计在排课问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第16卷第5期哈尔滨理工大学学报Vo1．16No．52011年10月JOURNALOFHARBINUNIVERSITYOFSCIENCEANDTECHNOLOGY0ct．2011均匀设计在排课问题中的应用陈滨，刘洋(1．哈尔滨医科大学基础医学院计算机教研室，黑龙江哈尔滨150081；2．总装工程兵驻沈阳地区军代室，黑龙江哈尔滨150001)摘要：针对目前高校排课系统的排课结果不均匀，造成班级或教师在某一时间段的课程过于密集或过于宽松的缺点，通过研究排课过程中的课程顺序对排课结果的影响，提出一种采用统计学中的均匀设计思想建立系统模型，并给出了评价方程．经过测试知，这种排课算

2、法的排课结果比其他算法更加均匀，由于提前根据均匀设计表给出了排课Jl瓯序，使排课的时间复杂度小于其他算法．关键词：排课问题；整数规划；均匀设计表中图分类号：TP301．6文献标志码：A文章编号：1007—2683(2011)05—0106—07ApplicationofUnIfOrmDesigninTimetableProblemCHENBin，LIUYang(1．DepartmentofComputer，HarbinMedicalUniversity，Harbin150081，China；2．PLAGeneralArmamentDepartmentRepresentat

3、iveOfficeinShenyangMilitaryRegionMilitaryRepresentativeOffice，Harbin150001，China)Abstract：Inviewofthedefectsthatcoursesofhighschoolarearrangedeitherfarmoreintensivelyorfarmorelooselyinacertainperiodoftimeforacertainclassorteacher，asaresultoftheunevencoursearangementsmadebythecourse—schedu

4、lingsystem，thisstudyworksontheinfluenceofthecoursesequencesduringtheschedulingprocessontheirresults，presentsasystematicmodelbasedontheideaofevendesigninstatistics，andputsforwardanevaluationequation．Throughtests，theresultsderivingfromthiscourse-schedulingalgorithmaremoreeventhanotheralgori

5、thms，becauseitproducescoursesequencesinadvancebyvirtueoftheevendesignform，whichsimpli·tiesthetimecomplexityforschedulingthanothermethods．Keywords：courseschedulingproblems；integerprogramming；uniformdesigntable0引言1排课问题的现状排课的算法在这四五十年来层出不穷，从最早的1．1解决排课问题的几种常见方法经验法，到现在引入了多种其他学科的理念来求解求解决排课问题的几种常

6、见方法有：精这个看似简单的问题．每一步的发展都反映着人们1)回溯法．回溯算法是一种选优搜索法，被称考虑角度的转变和探究的深入．排课问题是一个在满为解决问题的万能方法．回溯法按照所有可能的解足课程、教师、教室、班级、时间五维需求基础上追求进行向前搜索，以达到目的．若搜索到某一步时，发排课效率和更加人性化的复杂问题，已经被证明没有现其达不到预期的效果，就退回一步重新选择．但是任何算法能在多项式时间内找到最优解1J．由于在向前搜索时缺少更多的优化约束，使这种算收稿日期：2011—05—24作者简介：陈滨(1982一)，助教，Email：chenbin@elis．hrbmu．ed

7、u．cn．第5期陈滨等：均匀设计在排课问题中的应用107法在进行排课时可能存在大量的无效计算，造成时教室类型和教室容量和优先级等限制．间和空间上的浪费．依照文[7]中的回溯法对这个课表进行排课，2)遗传算法．遗传算法的工作流程如下：首先所得的结果如表2．这里的时间片指的是某个上课产生初始种群，设定适应函数作为评估适应性是否时间(详见下一章)以第1行为例，表示课程Ll由优秀的工具，选择适应性最优秀的染色体产生下一教师Sl于时间片1的时间在教室1向班级C1进行代染色体．并通过交叉和变异等手段保持和提升染授课．色体的优秀性．如此往复