排课问题分组优化决策中的

A2006,21(1):31-36Appl.Math.J.ChineseUniv.Ser.ACourseRank,,(,100084):(Timetabling)NP-,.,,..,.Markov,(CourseRank).2002,,.:(Timetabling);(CourseRank);Markov;NP-;:O224:A:1000-4424(2006)01-0031-06:2004-12-02L1(CourseTimetabling),(),,,.,,,,.,,,,.(CourseTimetabling)NP-.M1,2N,,,.(),,,O.,,OM3,4N.,.,、.,.、,.,、,.,.,,.,,.CourseRank,,,../CourseRank,,.01,.23456789:,,;a,=,=?,..@,,@.,,,.,.,,.,AarkoB,AarkoB.,,CourseRank,CooDEeFaDeRankGHI,AarkoB.232J9K7LMN6O8P,,QR,SRTSUVV,UVVVVWWQP,,QXYSZ[\WR]RR]R,P,;Z[\YV,[\,^[\_,[\‘_S_aUW^[\,^[\TSV,UIQ[\,^[\YU,,Vb^[\bUQ^[\,Q/c@/UUcj=ΣigijG,p,1-p.A=(aij)n×n,aij=pgij/cj+δ,δ=(1-p)/n,Aδ,.p=0.85,n=1000,δ=1.5×10-4.AMarkov,aij∈(0,1),1,Σiaij=1.Perron-Frobenius,x=Axx=(x1,x2,…,xn)T,,Σixi=1,.A1x.xMarkov,CourseRank,xi∈(0,1).QR,,CourseRank.STCUVUTVUW.XYZe[1S1,2,…,\]S1,2,…,n.YZe[2^n×\=(_ij),S_ij=1,ji0,ji‘,YZe[Ran×n=(cij).^\×n=(_ij),a.bij,,,a=^×^T]bij,a0=(c0ij)=^×^Ta,cij=bijc0ij.,.,a.YZe[4CourseRank.x=Ax,xCourseRank.,YZe[2,^n×\,,^n×\,.W.c,1000,,MaZdabe,10,2eRRSCourseRank,,,,,.#$%&&%,’()*+,-./01&21&&341.1’()*+,-./01&’()*+,-./01%$&5&6&&73358%5&33&6&&7%71&5171$&6&&$%%37$858&6&&59%397551$&:&&5;3;8214;%1$5&6&&5$3%72%4318%&6&&5$$;89%&;%&6&&55%%&2148131&6&&%88;31&179&6&&%887%1,’()*+,-./0,2142551$4,’()*+,-./0,,.,,.,’()*+,-./0,’()*+,-./0.,,’()*+,-./0,’()*+,-./0.%’()*+,-./0.%3,%8,’()*+,-./0.,,,,,,,’()*+,-./0’()*+,-./0.,%13,,7,,,’()*+,-./0.$5=%112CourseRankCourseRank17470.002251820230.00220921624400.002123127290.0020775GPS36270.001982040440.0019556423l0.001938144390.001932948190.0019092:5;P=Course?@AeBaCl@nD====;P==EFGarkoH=ICourseRankJ=CourseRank=CourseRank=CourseRank=KL1MSNOaerPQ.QsurHeRoPauBoAaBeSB@[e-mail]@P@N@alUnBell@DenNeReH@eV=1999=13K87127.L2MWurkeX=[e-mail]@reNB@ons@nauBoAaBeSB@[e-mail]@onalResearNO=2002=140K266280.L3M.LTM.=1999=14K2.L4M.LTM.=1998=38I6JK811.L5MWr@nS=PaDe[.?OeanaBoARoPalarDesNaleORYerBe\Bual][e-mail];eBVorks=1998=30I17JK107117.L6M^aHel@Vala?.XPP@N@[e-mail]?eNOn@NalReYorB=1999.L7MSe]erra_.Qn@nBroSuNB@onBoB@[e-mail]@onalResearNO=1985=19K151162.53KCourseRankCourseRankinthegroupingstrategyofcourseschedulingproblemsPENGTao,LIJian-guo,BAIFeng-shan(DepartmentofMathematicalSciences,TsinghuaUniversity,Beijing100084,China)Abstract:CourseschedulingisanNP-completecombinatorialoptimizationproblem,soitwouldbedifficulttofindanyefficientglobaloptimizationalgorithm.Groupingisanefficientstrategyforsolvingsuchamulti-factoroptimizationproblem.Allcoursesarepartitionedintogroupsbytheirranking.Thenthecombinatorialoptimizationalgorithmscanbeappliedtosolveeachgroupedsub-problem.Itisusuallyconsideredthatthecoursecapacityisthedominantfactorintherankingofthecourses.Theadvancedadministrationsystemallowsstudentstoselectcoursesinaconsiderablywiderange,whichmakesthisproblemmorecomplicated.AcourserankingmodelisproposedinthispaperusingMarkovchain,andtheconceptCourseRankisgiven.ResultsfromminingthecourseschedulingdataofTsinghuaUniversityof2002-2003academicyeararepresented,whichshowsthatthecoursecapacityisanimportantfactor,butnotreallythedominantone.KeyWords:courseschedulingproblem;CourseRank;Markovchain;NP-completeproblem;groupingstrategyMRSubjectClassification:90B9063A211