Research And Application Of TTP In Arranging Courses In Colleges And Universities

Timetable Problem (TTP) is a typical combination optimization problem and uncertain management problem, which is applied widely. TTP has been proved a NP-completion problem, and the course arrangement is a typical instance of TTP. Course arrangement is one of the basest, the most important and the most complicated tasks of college, of which the essential is to distribute time and space to courses to make the work in order according to the teaching plan. Dynamic Programming is one of methods to the Multistage Decision-making Problem. It partitions the complex problem into several phases, and gets the whole solution by resolving each phase of the problem.In this paper, we applied the technology of Multistage Decision-making and Dynamic Programming, analyzed many algorithms of recent software systems, (?)roposed a new algorithm, MACA(Multistage Auto-arranging Course Algorithm), and built a general Course Arrangement System, which can realize all kinds of requirements.From January of 2005, the system has been put into use in Shanghai Vocational and Technical College of Agriculture and Forestry, and the performance is good, so far. In July of 2005, the system passed the application of the Software Copyright. At the beginning of 2006, a new project based on this system, Study of a General System based on Course Arrangement & Examination Arrangement & Expenses Calculation, was applied and approved by the Shanghai Municipal Education Commission.The main work of this paper:(1) Analyzed the main factors and all kinds of constraints of course arrangement in detail.(2) Discussed the design process of Course Arrangement System using the Design Theory of Database System, including the concept design, the logical design, the physical design and the implementation.(3) Analyzed all collisions in the course arrangement process, and proposed different solutions.(4) Designed algorithms of teacher distribution: Distribute Algorithm of Equal Probability(EPDA) and Distribute Algorithm of First Matching (FMDA) .Compared the advantage and disadvantage of the two algorithms, proposed an optimization of...