高校排课系统算法的研究与实现
|
摘要
课程表的编排是高校教务管理中最重要、最复杂的工作。排课过程就是根据所要开设的课程,遵守一定约束条件,将讲授课程的教师、学习课程的学生和实施教学活动的教室等资源按照时间不冲突的原则在某个时段结合起来,形成教学资源的时空调度表,即课程表。课程表编排是否合理直接影响课堂教学效果。
1976年S.Even等人已经证明了排课问题是一个NP完全类问题,尽管目前有许多关于排课算法的研究,但是仍然没有一个能够被普遍接受的最优解决方案。本论文首先对排课问题进行需求分析,研究约束条件并建立组合优化数学模型;然后分析各种排课算法的优劣;最终根据实际情况采用贪心算法并加入具体排课策略来解决排课问题。本系统采取了手动排课与自动排课相结合的方式,允许用户预先设定一些关键课程的上课时间和上课地点,然后进行自动排课,对于自动排课结果,用户也可以手动的方式进行调整。整个系统分为基本信息管理、排课功能、查询功能以及用户管理等若干个功能模块,而每个模块也有相应的子模块。
经测试证明,本系统基本实现各模块的基本功能,能够很好的满足预先规定的所有排课限制条件,简化了教师、教室、班级之间的冲突处理,提高了求解速度,最终得到合理、科学、人性化的排课结果。
In order to guarantee its advanced teaching and studying quality, every university mustdraw up a tight and standard teaching and studying plan. The arrangement of curriculumschedule is one of the key questions. Not having a rational, accurate and normal curriculumschedule, the whole university will not has a well teaching and studying order. This showsthe courses arranging is the core of teaching and studying plan. As everyone knows thecourses arranging is a mathematic difficult problem. A lot of people are attracted to study it.
Course table problem have also been known as timetable problem, it is the typicalproblem in combination planning, it is also a multi-factor optimization of decision-makingproblems, it is a practical problem that has much research value. Arranging the courses byhand and traditional ways, we have great workload, cost much time, use up many resources,but the accuracy of curriculum schedule is low. . Along with the development ofcomputer, How to use computer to assign timetable becomes a question.
Greedy Method is a simplified problem-solving complexity algorithms. Its basic ideais: from an initial solution of a problem, it applied to gradually construct the current state ofthe optimal solution in order to speed as quickly as possible and gradually approaching thegoal of a given search method. Greedy algorithm does not take into account the overall best,but the whole problem into several stages to ensure that at each stage of the optimaldecision to make the present situation, and once the decision-making is no longer changed.Eliminate the use of greedy algorithm to find the overall optimal solution for the exhaust allthe possible amount of time-consuming, and can quickly get a more satisfactory solution.
The essence of Course Scheduling algorithm followed by the appropriate curriculumfor all school hours and appropriate courses will take place. If the Course Schedulingprocess of taking class time and class location will make the presentation of Timetablehuge increase rapidly the number of programs, and even give rise to "combinatorialexplosion", in order to avoid this from happening, to simplify the algorithm complexity,Course Scheduling algorithm row Lesson task decomposition timing and place of thearrangements for the two steps. Using successively use twice a greedy selection method,first under the program specified time slice allocation scheme for the program searches thecurrent idle time, the optimal class, curriculum, after school hours to determine, and thensearch the current curriculum to meet the constraints of the optimal school classrooms.
The Course Scheduling system has the following characteristics:
1. We consulted all automatic course scheduling methods, and read many references,then analyze the mathematical model of Course Scheduling.
2. We focused on the requirement analysis in course scheduling, describes the overallstructure of the system. This paper Based on the actual situation, Greedy Method is designed based on a convenient, flexible, fast Course Scheduling System. The systemrealizes the setting of basal information by managing database, Automatically combinedcourse scheduling and manually arranging schedule, greatly increased the speed andaccuracy of Course Scheduling. Course Scheduling The results will ultimately save back tothe database, the output arranging schedule results.
3. In each semester course arrangement, it often has some very critical to studentsmust complete to ensure that these special requirements of course with the time and placeof class. In order to ensure that, to avoid re-adjusted after-school end row, you need toadvance before Course Scheduling algorithm runs into the class schedule to arrange theirclass time and class locations. This step can be completed by the Course Schedulingpersonnel manual.
4. Course Scheduling task decomposition algorithm for the timing and place ofarrangements for two steps. Using successively use twice a greedy selection method, firstunder the program specified time slice allocation scheme for the program searches thecurrent idle time, the optimal class, curriculum, after school hours to determine, and thensearch the current curriculum to meet the constraints of the optimal school classrooms.
5. Algorithm is the allocation of time to establish a program library, arrangingschedule effective way to avoid the problem of "combinatorial explosion" phenomenon,save a lot of time to solve search and to ensure the curriculum in the adjacent schoolbetween the time an appropriate time interval. Giving priority to the training course and thebest school in the course of time, and can meet the teacher's "ban" school hours and the"expectations" school hours, so that Course Scheduling results more scientific and humane.In arranging the classroom, the anxious to ensure efficient use of the classroom, but also tominimize the long-distance transfer of students between classes classrooms.
6. In the Course Scheduling process, the first presentation of the course have the mostchoice, with the increasing number of courses have been arranged, followed by row ofcourses to be less and less choice may lead to a number of key curriculum at anunreasonably the time or location. Row sequence of courses on the course schedulingsystem finally finds the optimal solution of the problem as a whole is essential. The CourseScheduling System according to certain rules to seek a priority for each course series, andthen in descending order according to priority, followed by classes for each course to solvethe time and place of class so that you can ensure that important, arranging scheduledifficult give priority to arranging schedule of courses, greatly reducing the CourseScheduling conflicts from arising.
7. In order to Course Scheduling results become more rational and scientific as well ashumane, Course Scheduling System in the Course Scheduling process need to give fullconsideration to curriculum, teachers, classes and other elements of the specialrequirements of Course Scheduling. Prior to the Course Scheduling Course SchedulingSystem then allows the user to enter the special requirements of the course arrangement offactors, such as teachers "expect class time" and "Prohibition of class time," programs are"preferred class time" and so on.
8. Colleges and Universities Course Scheduling process involves many basic data,these basic data, including faculty, classes, teachers, students, classrooms, curriculum, time,teaching, and some additional information on these basic information to be able to increasebased on the actual situation in a flexible, modify , delete, query and other operations. Basic information management, including: teacher information management, curriculuminformation management, information management, class, classroom informationmanagement.
9. After the end of the Course Scheduling, the most important thing is the results ofqueries Course Scheduling, print curriculum, the query feature is the ability to query thecurriculum used in various forms, including by class queries, queries by classroom, byteachers, query, query by time , according to the course a variety of ways to search queries.
10. In order to ensure the security of system data, for different types of users to grantpermissions to different operations, according to the different operating privileges displaydifferent information, the operation authority is divided into browsing permissions,arranging schedule entry rights and privileges of three, including browsing the lowestpermission level , then the entry permissions, arranging schedule the highest privilegelevel.
1976年S.Even等人已经证明了排课问题是一个NP完全类问题,尽管目前有许多关于排课算法的研究,但是仍然没有一个能够被普遍接受的最优解决方案。本论文首先对排课问题进行需求分析,研究约束条件并建立组合优化数学模型;然后分析各种排课算法的优劣;最终根据实际情况采用贪心算法并加入具体排课策略来解决排课问题。本系统采取了手动排课与自动排课相结合的方式,允许用户预先设定一些关键课程的上课时间和上课地点,然后进行自动排课,对于自动排课结果,用户也可以手动的方式进行调整。整个系统分为基本信息管理、排课功能、查询功能以及用户管理等若干个功能模块,而每个模块也有相应的子模块。
经测试证明,本系统基本实现各模块的基本功能,能够很好的满足预先规定的所有排课限制条件,简化了教师、教室、班级之间的冲突处理,提高了求解速度,最终得到合理、科学、人性化的排课结果。
In order to guarantee its advanced teaching and studying quality, every university mustdraw up a tight and standard teaching and studying plan. The arrangement of curriculumschedule is one of the key questions. Not having a rational, accurate and normal curriculumschedule, the whole university will not has a well teaching and studying order. This showsthe courses arranging is the core of teaching and studying plan. As everyone knows thecourses arranging is a mathematic difficult problem. A lot of people are attracted to study it.
Course table problem have also been known as timetable problem, it is the typicalproblem in combination planning, it is also a multi-factor optimization of decision-makingproblems, it is a practical problem that has much research value. Arranging the courses byhand and traditional ways, we have great workload, cost much time, use up many resources,but the accuracy of curriculum schedule is low. . Along with the development ofcomputer, How to use computer to assign timetable becomes a question.
Greedy Method is a simplified problem-solving complexity algorithms. Its basic ideais: from an initial solution of a problem, it applied to gradually construct the current state ofthe optimal solution in order to speed as quickly as possible and gradually approaching thegoal of a given search method. Greedy algorithm does not take into account the overall best,but the whole problem into several stages to ensure that at each stage of the optimaldecision to make the present situation, and once the decision-making is no longer changed.Eliminate the use of greedy algorithm to find the overall optimal solution for the exhaust allthe possible amount of time-consuming, and can quickly get a more satisfactory solution.
The essence of Course Scheduling algorithm followed by the appropriate curriculumfor all school hours and appropriate courses will take place. If the Course Schedulingprocess of taking class time and class location will make the presentation of Timetablehuge increase rapidly the number of programs, and even give rise to "combinatorialexplosion", in order to avoid this from happening, to simplify the algorithm complexity,Course Scheduling algorithm row Lesson task decomposition timing and place of thearrangements for the two steps. Using successively use twice a greedy selection method,first under the program specified time slice allocation scheme for the program searches thecurrent idle time, the optimal class, curriculum, after school hours to determine, and thensearch the current curriculum to meet the constraints of the optimal school classrooms.
The Course Scheduling system has the following characteristics:
1. We consulted all automatic course scheduling methods, and read many references,then analyze the mathematical model of Course Scheduling.
2. We focused on the requirement analysis in course scheduling, describes the overallstructure of the system. This paper Based on the actual situation, Greedy Method is designed based on a convenient, flexible, fast Course Scheduling System. The systemrealizes the setting of basal information by managing database, Automatically combinedcourse scheduling and manually arranging schedule, greatly increased the speed andaccuracy of Course Scheduling. Course Scheduling The results will ultimately save back tothe database, the output arranging schedule results.
3. In each semester course arrangement, it often has some very critical to studentsmust complete to ensure that these special requirements of course with the time and placeof class. In order to ensure that, to avoid re-adjusted after-school end row, you need toadvance before Course Scheduling algorithm runs into the class schedule to arrange theirclass time and class locations. This step can be completed by the Course Schedulingpersonnel manual.
4. Course Scheduling task decomposition algorithm for the timing and place ofarrangements for two steps. Using successively use twice a greedy selection method, firstunder the program specified time slice allocation scheme for the program searches thecurrent idle time, the optimal class, curriculum, after school hours to determine, and thensearch the current curriculum to meet the constraints of the optimal school classrooms.
5. Algorithm is the allocation of time to establish a program library, arrangingschedule effective way to avoid the problem of "combinatorial explosion" phenomenon,save a lot of time to solve search and to ensure the curriculum in the adjacent schoolbetween the time an appropriate time interval. Giving priority to the training course and thebest school in the course of time, and can meet the teacher's "ban" school hours and the"expectations" school hours, so that Course Scheduling results more scientific and humane.In arranging the classroom, the anxious to ensure efficient use of the classroom, but also tominimize the long-distance transfer of students between classes classrooms.
6. In the Course Scheduling process, the first presentation of the course have the mostchoice, with the increasing number of courses have been arranged, followed by row ofcourses to be less and less choice may lead to a number of key curriculum at anunreasonably the time or location. Row sequence of courses on the course schedulingsystem finally finds the optimal solution of the problem as a whole is essential. The CourseScheduling System according to certain rules to seek a priority for each course series, andthen in descending order according to priority, followed by classes for each course to solvethe time and place of class so that you can ensure that important, arranging scheduledifficult give priority to arranging schedule of courses, greatly reducing the CourseScheduling conflicts from arising.
7. In order to Course Scheduling results become more rational and scientific as well ashumane, Course Scheduling System in the Course Scheduling process need to give fullconsideration to curriculum, teachers, classes and other elements of the specialrequirements of Course Scheduling. Prior to the Course Scheduling Course SchedulingSystem then allows the user to enter the special requirements of the course arrangement offactors, such as teachers "expect class time" and "Prohibition of class time," programs are"preferred class time" and so on.
8. Colleges and Universities Course Scheduling process involves many basic data,these basic data, including faculty, classes, teachers, students, classrooms, curriculum, time,teaching, and some additional information on these basic information to be able to increasebased on the actual situation in a flexible, modify , delete, query and other operations. Basic information management, including: teacher information management, curriculuminformation management, information management, class, classroom informationmanagement.
9. After the end of the Course Scheduling, the most important thing is the results ofqueries Course Scheduling, print curriculum, the query feature is the ability to query thecurriculum used in various forms, including by class queries, queries by classroom, byteachers, query, query by time , according to the course a variety of ways to search queries.
10. In order to ensure the security of system data, for different types of users to grantpermissions to different operations, according to the different operating privileges displaydifferent information, the operation authority is divided into browsing permissions,arranging schedule entry rights and privileges of three, including browsing the lowestpermission level , then the entry permissions, arranging schedule the highest privilegelevel.
引文
[1] Werra D..An introduction to timetabling. European Journal of Operations Research, 1985,19:151-162
[2] Abramson D..Constructing school timetables using simulated annealing:Sequential and parallelalgorithms.Management Science,1991,37:98-113
[3] Gaspero L., SchaerfA., Tabu search techniques for examination timetabling.In Proceedings of the 3rdInternational Conference on Practice and Theory of Automated Timetabling(PATAT 2000),LNCS2079,Springer-Verlag,2001,104-117
[4] Gotlieb. The construction of Class-teacher time tables. Proeeding IFIP congress，Amsterdam，1963，73-74
[5] S.Even,Ital A Shamir A. On the complexity of timetable and multicommodity flow problems（关于时间表和多物质流问题的复杂性）.SIAM Journalon Computing，1976，4:691-703
[6] Carlson, R.C. and Nemhauser, G.L. Scheduling to minimize interaction cost, Operatons Research,1966, Vol.14, No.10, 360-364
[7] J.N.C.Brittan and F.J.M.Farley, College timetable construction by computer, The Computer Journal,1970,Vol.14,No.4,361-365
[8] E.A.Akkoyunlu, A linear algorithm for computing the optimum university timetable,The ComputerJournal,1972,Vol.16,No.4,347-350
[9]林漳希，林尧瑞．人工智能技术在课表编排中的应用[J]．清华大学学报（自然版），1984，1-8
[10]洪力奋．基于人工智能原理的大学课表编排模型[J]．合肥工业大学学报，1999(4):102-103
[11]张春梅，行飞．用自适应的遗传算法求解大学课表安排问题[J]．内蒙古大学学报(自然科学版)，2002,33(4):459-464
[12]黄干平等．使用模拟退火算法解课表问题[J]．武汉大学学报，2000，46(5):559-563
[13]王能斌，钱祥根．大学课程表调度系统-UTSS[J]．计算机学报，1994(5):383-389
[14]张清绵，徐明，王明等．智能教学组织管理与课程表调度系统[J]．大连理工大学学报，2001，31(2):227-232
[15]王迪吉．组合数学在数论中的应用实例[J]．新疆师范大学学报（自然科学版），2002，4
[16] Edward Mani. Quality of teaching at an all-time high education, Observer Newspaper. 2004, 3
[17]萨师煊．数据库系统概论[M]．高等教育出版社，2000，第三版
[18]何新贵．知识处理与专家系统[M]．国防工业出版社，1990
[19]王晓听．专家系统在自动排课中的研究应用[D]．北京理工大学，2002:12-14
[20]程国忠．三个典型问题的回溯算法[J]．四川师范学院学报,2000,vol.21 no.2
[21]吴志斌等．回溯算法与计算机排课[J]．计算机工程，1999，25(3): 79-80
[22]Safaai D,Sigeru O.Incorporating constraint propagation in genetic algorithm for university timetableplanning[J]. Engineering Applications of Artificial Intelligence, 1999: 241-253
[23]Hirsch M W. Convergent activation daynamics in continuous time networks. Neural Networks,1989: 331-349
[24] Arunkumar,S.Chockalingam,T.Genetic search algorithms and their randomized operators. CoputersMath Applic, 1993, (27): 91-100
[25] Dawid H. A Markov chain. analysis of genetic algorithms with a state dependent fitness functions.Complex Systems, 1994,(23 ): 407-417
[26]唐洪英，周敏．基于分层分次贪心算法的排课系统的设计与实现[J]．微计算机信息，2006(12):237-240
[27]王伟，余利华．基于贪心法和禁忌搜索的实用高校排课系统[J]．计算机应用，2007,11(21):2873-2876
[28]聂小东，李振坤，陈平华．基于贪婪算法的排课系统的探讨与实现[J]．现代计算机，2007,11:109-112
[2] Abramson D..Constructing school timetables using simulated annealing:Sequential and parallelalgorithms.Management Science,1991,37:98-113
[3] Gaspero L., SchaerfA., Tabu search techniques for examination timetabling.In Proceedings of the 3rdInternational Conference on Practice and Theory of Automated Timetabling(PATAT 2000),LNCS2079,Springer-Verlag,2001,104-117
[4] Gotlieb. The construction of Class-teacher time tables. Proeeding IFIP congress，Amsterdam，1963，73-74
[5] S.Even,Ital A Shamir A. On the complexity of timetable and multicommodity flow problems（关于时间表和多物质流问题的复杂性）.SIAM Journalon Computing，1976，4:691-703
[6] Carlson, R.C. and Nemhauser, G.L. Scheduling to minimize interaction cost, Operatons Research,1966, Vol.14, No.10, 360-364
[7] J.N.C.Brittan and F.J.M.Farley, College timetable construction by computer, The Computer Journal,1970,Vol.14,No.4,361-365
[8] E.A.Akkoyunlu, A linear algorithm for computing the optimum university timetable,The ComputerJournal,1972,Vol.16,No.4,347-350
[9]林漳希，林尧瑞．人工智能技术在课表编排中的应用[J]．清华大学学报（自然版），1984，1-8
[10]洪力奋．基于人工智能原理的大学课表编排模型[J]．合肥工业大学学报，1999(4):102-103
[11]张春梅，行飞．用自适应的遗传算法求解大学课表安排问题[J]．内蒙古大学学报(自然科学版)，2002,33(4):459-464
[12]黄干平等．使用模拟退火算法解课表问题[J]．武汉大学学报，2000，46(5):559-563
[13]王能斌，钱祥根．大学课程表调度系统-UTSS[J]．计算机学报，1994(5):383-389
[14]张清绵，徐明，王明等．智能教学组织管理与课程表调度系统[J]．大连理工大学学报，2001，31(2):227-232
[15]王迪吉．组合数学在数论中的应用实例[J]．新疆师范大学学报（自然科学版），2002，4
[16] Edward Mani. Quality of teaching at an all-time high education, Observer Newspaper. 2004, 3
[17]萨师煊．数据库系统概论[M]．高等教育出版社，2000，第三版
[18]何新贵．知识处理与专家系统[M]．国防工业出版社，1990
[19]王晓听．专家系统在自动排课中的研究应用[D]．北京理工大学，2002:12-14
[20]程国忠．三个典型问题的回溯算法[J]．四川师范学院学报,2000,vol.21 no.2
[21]吴志斌等．回溯算法与计算机排课[J]．计算机工程，1999，25(3): 79-80
[22]Safaai D,Sigeru O.Incorporating constraint propagation in genetic algorithm for university timetableplanning[J]. Engineering Applications of Artificial Intelligence, 1999: 241-253
[23]Hirsch M W. Convergent activation daynamics in continuous time networks. Neural Networks,1989: 331-349
[24] Arunkumar,S.Chockalingam,T.Genetic search algorithms and their randomized operators. CoputersMath Applic, 1993, (27): 91-100
[25] Dawid H. A Markov chain. analysis of genetic algorithms with a state dependent fitness functions.Complex Systems, 1994,(23 ): 407-417
[26]唐洪英，周敏．基于分层分次贪心算法的排课系统的设计与实现[J]．微计算机信息，2006(12):237-240
[27]王伟，余利华．基于贪心法和禁忌搜索的实用高校排课系统[J]．计算机应用，2007,11(21):2873-2876
[28]聂小东，李振坤，陈平华．基于贪婪算法的排课系统的探讨与实现[J]．现代计算机，2007,11:109-112