수업 시간표 작성을 위한 제약 프로그래밍 접근법
Constraint Programming Approach for a Course Timetabling Problem
1
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
The course timetabling problem is a problem assigning a set of subjects to the given classrooms and different timeslots, while satisfying various hard constraints and soft constraints. This problem is defined as a constraint satisfaction optimization problem and is known as an NP-complete problem. Various methods has been proposed such as integer programming, constraint programming and local search methods to solve a variety of course timetabling problems. In this paper, we propose an iterative improvement search method to solve the problem based on constraint programming. First, an initial solution satisfying all the hard constraints is obtained by constraint programming, and then the solution is repeatedly improved using constraint programming again by adding new constraints to improve the quality of the soft constraints. Through experimental results, we confirmed that the proposed method can find far better solutions in a shorter time than the manual method.
Abstract
The course timetabling problem is a problem assigning a set of subjects to the given classrooms and different timeslots, while satisfying various hard constraints and soft constraints. This problem is defined as a constraint satisfaction optimization problem and is known as an NP-complete problem. Various methods has been proposed such as integer programming, constraint programming and local search methods to solve a variety of course timetabling problems. In this paper, we propose an iterative improvement search method to solve the problem based on constraint programming. First, an initial solution satisfying all the hard constraints is obtained by constraint programming, and then the solution is repeatedly improved using constraint programming again by adding new constraints to improve the quality of the soft constraints. Through experimental results, we confirmed that the proposed method can find far better solutions in a shorter time than the manual method.
참고문헌 (17)
- H. Babaei, "A Survey of Approaches for University Course Timetabling Problem", Computers & Industrial Engineering, 86, pp.43~59 (2015)
- T. B. Cooper, "The Complexity of Timetable Construction Problems", Proceedings of the 1st International Conference on the Practice and Theory of Automated Timetabling (PATAT 1995), pp.281~295 (1996)
- C. C. Gotlieb, "The Construction of Class-teacher Timetables", Proceedings of IFIP Congress, pp.73~77 (1962)
- S Daskalaki, "An Integer Programming Formulation for a Case Study in University Timetabling", European Journal of Operational Research, 153(1), pp.117~135 (2004)
- E. K. Burke, "A Branch-and-cut Procedure for the Udine Course Timetabling Problem", Annals of Operations Research, 194(1), pp.71~87 (2012)
- S. Yang, "Genetic Algorithms with Guided and Local Search Strategies for University Course timetabling", IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 41(1), pp.93~106 (2011)
- Z. Lü, "Adaptive Tabu Search for Course Timetabling", European Journal of Operational Research, 200(1), pp.235~244 (2010)
- C. Nothegger, "Solving the Post Enrolment Course Timetabling Problem by Ant Colony Optimization", Annals of Operations Research, 194(1), pp.325~339 (2012)
- R. Lewis, "A Survey of Metaheuristic-based Techniques for University Timetabling Problems", OR Spectrum, 30(1), pp.167~190 (2008)
- R. Dechter, "Constraint Processing" (2003), Morgan Kaufmann
- L. Zhang, "Constructing University Timetable using Constraint Satisfaction Programming Approach", IEEE Proceedings of the 2005 International Conference on Computational Intelligence for Modelling, Control and Automation, and International Conference on Intelligent Agents, Web Technologies and Internet Commerce, (2), pp.55~60 (2005), IEEE
- C. S. Kim, "Automatic Generation of Lecture Timetable Using Constraint Programming", Proceedings of the 2015 KIISE Symposium on Ubiquitous Computing and Web Information Technology, pp.137~140 (2015)
- T. A. Duong, "Combining Constraint Programming and Simulated Annealing on University Exam Timetabling", Proceedings of RIVF Conference, pp.205~210 (2004)
- L. T. Merlot, "A Hybrid Algorithm for the Examination Timetabling Problem", Proceedings of the 4th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2002), pp.207~231 (2002)
- C. Valouxis, "Constraint Programming Approach for School Timetabling", Computers & Operations Research, 30(10), pp.1555~1572 (2003)
- C. S. Kim, "A Constraint Programming Model for Lecture Timetable Optimization", Proceedings of the Korean Society of Computer Information Conference, 25(1), pp.13~14 (2017)
- "ILOG CPLEX Optimization Studio: CP Optimizer User's Manual, V12.6.2", IBM Corporation, ~ (2014)