摘要
排课问题是涉及班级、教师、教室等因素的决策优化问题，也是组合规划中
的典型问题。在自动排课系统中，处理排课问题所用的算法处于核心地位，由于
排课问题本身的复杂性，寻找这样一个有效算法还是有相当的难度。本文课题来
源于自动排课问题的求解算法研究。
本文借鉴以往的成功经验并结合本学校的实际情况，提出了一种基于禁忌搜
索算法的排课问题解决方案。首先，使用网络最大流算法预处理，把授课任务分
成若干组，同组的任务可以同时进行而不发生冲突，而且保证教室需求量不大于
供〖本文来自：毕业设计论文网www.paper51.com〗应量。然后，使用禁忌搜索寻求任务组与时间的最优组合方式。最后，给任务
分配教室输出课表。本文先给出了算法的总体框架，然后对如何建立网络流模型
以及禁忌搜索的各个要素进行了详细的说明，最后使用真实数据进行了仿真测试。
这种方案结合了经典的网络流算法与禁忌搜索算法，使两种算法优势互补，
带来了较好的处理问题能力。经实际数据的仿真验证，该算法具有一定可行性和
适用性。
关键词：排课问题组合优化网络流禁忌搜索
Abstract
Abstract
Course-timetablingproblem,anoptimizationdecision-makingprobleminvolving
factorssuchasclasses,teachersandclassroomsetc,isatypicalproblemof
combinatorialplanning.Inanautomated-course-timetablingsystem,thealgorithmof
coursetimetablingenjoysthecorestatus,butitisratherdifficultforustofindan
effectiveprocessingalgorithmduetothecomplexityofthecourse-timetablingproblem
itself.Thesubjectstudiedinthispaperoriginatesfromtheresearchonthealgorithmof
automaticcourse-timetablingproblem.
Thispaperintroducedamethodtosolvethecourse-timetablingproblembasedon
taboosearch.First,usesthenetworkmax-flowalgorithminpreprocessingtodividethe
teachingtasksintoseveralgroups,inwhichthetaskscanbecarriedonsimultaneously
withoutcollisionsandthenumberoftherequiredclassroomsnotlagerthanthenumber
ofthesuppliedones.Second,seeksabestcombinationbetweentaskgroupsandtime
slotsusingtaboosearch.Last,assignsaclassroomtoeveryteachingtaskandoutputs
thecoursetimetable.Thispaperproposesanoutlineofthealgorithmatfirst.Then,a
detailedexplanationisgivenonhowtoestablishthenetwork-flowmodelaswellas
howtousetheessentialfactorsintaboosearch.Finally,usestherealdatatocarryout
thesimulationtest.
Theimplementationoftheplan,whichunifiestheclassicalnetworkflows
algorithmandthemodernheuristictaboosearchalgorithm,causesthesuperioritiesof
twoalgorithmssupplementingeachother,andimprovestheabilityofprocessing
problems.Afterconfirmedthroughtherealdatasimulation,thealgorithmwhichthis
paperproposedisofcertainfeasibilityandtheserviceability.
Keywords:Course-TimetablingProblemCombinatorialOptimization
NetworkFlowTabooSearch
目录
目录
第一章绪论..........................................................1
1.1排课问题简述...................................................1
1.2国内外研究现状.................................................2
1.2.1排课问题的历史..............................................2
1.2.2排课问题的求解方法..........................................2
1.2.3当前研究趋势及存在的问题....................................4
1.3本文的研究意义及所做工作.......................................5
1.4论文结构.......................................................6
第二章排课模型的建立与分析..........................................7
2.1西电教务流程及排课特点简介.....................................7
2.1.1教务流程简介...............................................7
2.1.2教学教务信息系统简介.......................................8
2.2课表的制定原则.................................................9
2.3排课系统的基本需求分析........................................11
2.4排课问题模型..................................................12
2.4.1符号约定..................................................12
2.4.2建立组合优化模型..........................................12
2.5本章小结......................................................13
第三章禁忌搜索算法理论研究.........................................15
3.1组合优化问题的求解............................................15
3.1.1组合最优化概念.............................................15
3.1.2邻域及邻域搜索.............................................15
3.1.3启发式算法.................................................17
3.2禁忌搜索算法..................................................18
3.2.1禁忌搜索原理...............................................18
3.2.2禁忌搜索算法流程...........................................19
3.2.3禁忌搜索示例...............................................20
3.2.4禁忌搜索的收敛性...........................................24
3.3基于禁忌搜索的组合优化........................................24
目录
3.4本章小结.......................................................26
第四章基于禁忌搜索的排课问题求解...................................27
4.1算法总体思想...................................................27
4.2符号定义.......................................................28
4.2.1基本信息定义...............................................28
4.2.2基本函数定义...............................................28
4.2.3组合信息定义...............................................28
4.3基于网络流的预处理算法.........................................28
4.4基于禁忌搜索的时间分配算法.....................................30
4.5后续操作.......................................................34
4.6算法运行实例分析...............................................34
4.6.1输入数据...................................................34
4.6.2预处理步骤分析.............................................35
4.6.3禁忌搜索过程分析...........................................36
4.6.4输出周课表.................................................38
4.7本章小结.......................................................39
第五章总结与展望...................................................41
5.1对本文工作的总结...............................................41
5.2对进一步研究的展望.............................................42
致谢................................................................43
参考文献............................................................44
读研期间研究成果....................................................47
参考文献
[1]CotliebCC.Theconstructionofclass-teachertimetable.Information
processing[C].Proc.IFIPCongress62.1962.73-77
[2]EvenS,ItaiA,ShamirA.OntheComplexityofTimetableand
MultieommodityFlowProblems[J].SIAMJournalonComputing.1976,5(4):691
-703
[3]Murphy,JandR.Suter.Schoolschedulingbycomputer-thestoryof
GSAP[J].EducationalFacitiliesLabs.Inc.NewYork,December,1964.
[4]E.D.Barraclough.Theapplicationofadigitalcomputertothe
constructionoftimetables[J].TheComputerJournal.1965,8(2):136-146
[5]Ferland,J.AandRoys.Timetablingproblemforuniversityasassignment
ofactivitiestoresources[J].ComputersandOperationsResearch.
1985,12(2):207-218
[6]D.deWerra.Anintroductiontotimetabling[J].EuropeanJournalof
OperationalResearch,19(1985)151-162.
[7]Wood,D.c.Atechniqueforcoloringagraphapplicabletolargescale
timetablingproblem[J].ComputerJournal.12(1969),317-319
[8]G.A.NeufeldandJ.Tartar.Graphcoloringconditionsfortheexistence
ofsolutionstothetimetableproblem[J].CommunicationsoftheACM.
1974,17(8):450-453.
[9]孙建平,梅晓勇,肖政宏,史忠植.关联规则在高校智能排课系统中的应用[J].
计算机应用.2002,22(5):37-39
[10]吴金荣.求解课程表问题的分支定界算法[J].运筹与管理.2002,
11(1):17-22
[11]王枯民,赵致格.排课表问题中的分组优化决策算法[J].控制与决策.1999,
14(2):109-114
[12]谢凡荣.求解排课表问题的一个启发式数值算法[J].运筹与管理.2005,
14(10):36-40
[13]黄干平，姚自珍，张轶静.使用模拟退火算法解课表问题[J].武汉大学学报
(自然科学版)[J].2000,46(5),559-56
[14]A.Colorni,M.Dorigo,andV.Maniezzo.Ageneticalgorithmtosolve
参考文献45
thetimetableproblem[J].TechnicalReport90-060revised,Politecnicodi
Milano,Italy,1992.
[15]LarsVestergaardKragelund.Solvingatimetablingproblemusinghybrid
geneticalgorithms[J].Software-PracticeandExperience.vol.27(10),
1997,1121-1134
[16]杨宇.高校排课系统理论研究与开发——遗传算法在课表问题中的应用[D].
北京理工大学硕士学位论文.2003
[17]张春梅,行飞.用自适应的遗传算法求解大学课表安排问题[J]，内蒙古大学
学报(自然科学版).2002,33(4)
[18]唐勇,唐雪飞,王玲.基于遗传算法的排课系统[J].计算机应用，200222[10]
[19]业宁,梁作鹏,董逸生.一种基于遗传算法的TTP问题求解算法[J].东南大学
学报(自然科学版).2003,33(1)
[20]王健,董改芳,许道云.自动排课系统的模型与实现[J].贵州大学学报(自然
科学版).2004,21(2)
[21]郑月锋.遗传算法在求解时间表问题中的应用研究[D].浙江工业大学硕士学
位论文.2005
[22]张林.基于蚁群算法的排课系统研究与设计[D].安徽大学硕士学位论文.
2005
[23]InternationalTimetablingCompetition[OL]
http://www.idsia.ch/Files/ttcomp2002/oldindex.html
[24]PAKostuch,TimetablingCompetition-SA-basedHeuristic[OL]，
http://www.idsia.ch/Files/ttcomp2002/kostuch.pdf
[25]Jean-Fran