摘要：技术主要解决中学新课改及大学的选修课排课问题，根据学生选课弹性机制分班，统筹合理分解出独立的小模块（排序、排课、计算），将排课用线性思想、工程化方法解决。排课时，先按要求将任务自动排序，以便自动排课或辅助手工排课，将海量的计算交给计算机来完成，这样既能高效自动化排课，又能兼顾人性化排课的特殊要求。最后采用少量计算机辅助人工排课或调课得到满意的课表。另外本技术兼顾安排考试。对{{@@@keyword0@@@}}发明专利技术的情况作了说明。
关键词：课表问题；计算机自动排课；NP完全问题；组合优化；高校排课问题
中图分类号：G639.1文献标识码：A 文章编号：1007-9599 (2011) 18-0000-02
High School New Curriculum and University Senate Timetable Research and Implementation
Gu Yongxin1,Qi Xiuhua2
Abstract:New technology mainly to solve the high school curriculum and elective University Course Scheduling problem,the student elective placement flexibility mechanisms to co-ordinate a reasonable decomposition of small independent modules(sort,arrange more terms),the linear Timetable thinking,engineering solutions.Scheduling,the press automatically sort the tasks required to assist manual or automatic Timetable Timetable,the calculation of the mass to the computer to complete,so that both high-automation Timetable,but also take into account the special requirements of human Scheduling.Finally,using a small amount of computer-aided manual Timetable or transfer courses to be satisfied with the curriculum.Also take into account the technical arrangements for the examination.For the case of applications for invention patents described.
Keywords:Curriculum issues;Computer Automated Course Scheduling;NP-complete problem;Combinatorial optimization;University Course Scheduling problem
一、背景技术与目标
1975年，S.Even等人论证了课程表问题是NP完全问题。由于课程表问题所涉及的信息较多，并且求解课程表问题最优解的时间复杂性是课程表规模的指数级，所以一般采用求近似最优解的算法。
二、技术的先进性和可行性
排课问题是一个典型的组合优化和不确定性调度问题。选修课排课解决方案，特别是学分制中学生自由选课后的排课问题没有办法解决。尽管目前有许多关于排课算法的研究，但是仍然没有一个能够被普遍接受的最优解决方案。各省新课程管理平台即测试学生选课对排课的影响是本技术的关键。该技术在全自动、半自动、手动排课、手动调课、自动调课中都要用到。（图2右图就是图2左图中的F模块的详细步骤）。模块F的具体步骤如下：1）在学生的选课和分班记录中，将学生前面的课元设为第i个，后面一个课元设为第j个，i值初始为1，j初始值比i大1，其中课元就是对应选课和其分班的组合；2）学生的第i个课元和第j个课元是否有冲突，有冲突说明这个位置不能排课；没有冲突则j自增加1，然后执行3）；3）j是否超出实际范围n，其中n代表1个学生选课的最大数量，没有超出，执行步骤2）；超出则执行步骤4）；4）i自增加1，然后将i的值再加1赋值给j，j是否超出实际范围，没有超出则执行步骤2）；超出就执行步骤5）；5）学生选课及分班记录向下移动一个记录，检测是否有这样的纪录，有则执行步骤1），没有就表示没有冲突。
（五）编码、测试方法、过程及结果
用Delphi作为开发工具。以古浪一中150位老师排课的情况和要求设计，设计过程就是一个测试的过程，各图、表就是在设计和测试中形成的。测试方法是从简单到难，从数据少到数据多。
（六）关键技术已经提交发明专利申请
一种在多约束条件下高效分班、排课的方法，2010年10月申请，方法已被中华人民共和国国家知识产权局受理，发文序号30，现已经进入实质审查阶段，专利申请号或专利号：.0。
参考文献：
[1]Arunkumar S,Chockalingam T.Genetic search algorithms and their randomized operators.Computers Math Applic,1993
[2]方世昌.离散数学[M].西安电子科技大学出版社
[3]罗星凯.学校课程管理系统及运行方法.中国,CN,2005-03-23.未授权
[4]盛骤.概率论与数理统计[J].浙江大学,第三版
[5]王健,董改芳,许道云.基于遗传算法的自动排课系统[J].贵州大学计算机科学系
[6]李锐.高校排课系统算法的研究与实现[J].吉林大学
[作者简介]贾永鑫（1977&#;），男，甘肃省古浪县人，本科，主要从事学年制和学分制教务课程表排课方面的研究；祁秀花（1978&#;），女，甘肃省古浪县人，本科，学士，主要从事高中新课程改革及教务管理方面的研究。
查看全文
false