The Course Assignment Model And Its Application With Diversity Constraints

Time tabling problem has a long history. When the human society entered the industrial production, the study of the problem becomes particularly urgent. How to find the optimal solution to meet the diversity of constraints is the core problem in the field of schedule. In 1975, S.Evens et al proved schedule problem is NP-complete problem, efforts to find a global optimum bankruptcy. The next best thing, people began to study heuristics given local optimal solution, these algorithms in real life production have been widely used.Course assignment problem as a classical issue in the field of time tabling has been much scholarly attention. Especially for the course scheduling problems which have huge sample size and significant individual differences. The industry has developed a lot of good heuristics to help educational institutions to solve practical problems. For example, simulated annealing, tabu search, genetic algorithm and ant colony algorithm and so on. However, with rising levels of education, customization program has become increasingly important. How to meet the same curriculum of schools, teachers and students of various demands, traditional heuristic algorithm already fail under these diversity constraints, we need to explore new ways to solve new problems.David Gale and Lloyd Shapley proposed the concept of a stable match in 1962.Because this work, 50 years later, they were awarded the Nobel Prize in economics. Course assignment issues relate to the match of campus teachers, students and classrooms, and a successful schedule means that matching is stable. Inspired by this, we will stabilize the matching model into the Arranging Course System. After a simple preprocessing, the teachers’ course requirements and the students’ course requirements can be converted to the preference list, using Gale-Shapley algorithm can accurately calculate a steady schedule. By Gale-Shapley algorithm, the stable schedule has some interesting properties, these will be involved in the text.In addition, the course arrangement can also be resolved through auction model. In the case of no ask from teachers, we may be able to refer the student’s enrollment will to decide whether to let him choose this course. In this model, the courses are seen as merchandise, elective behavior of each student is the bidding, and only bidding in front of a group of students on this course can be selected. Market economy is not necessarily fair, so "auction" course will also have some drawbacks. Recent research results show that, Eric Budish, who successfully improved the auction algorithm, making arranging the results to ensure a degree of fairness, we will continue to explore in the text.In the "laboratory investigation" of these courses, teachers often desire to have a certain group of students’ enrollment of continuity, that is, in different courses to have a core team always participation, to strengthen teaching achievements, and to improve quality of the course. Although the Gale-Shapley algorithm and Budish model can effectively solve the problem of bilateral constraint and unilateral constraints, but for the "core team" of the new requirements, these two types of algorithm cannot achieve good results. Therefore, this article will introduce clustering algorithm to solve this kind of problem.