Journal of the Korea Society of Computer and Information (한국컴퓨터정보학회논문지)

Korean Society of Computer Information (한국컴퓨터정보학회)
권호 표지
DOI QR코드

DOI QR Code

Constraint Programming Approach for a Course Timetabling Problem

  • Kim, Chun-Sik (Dept. of Computer Engineering, Kumoh National Institute of Technology) ;
  • Hwang, Junha (Dept. of Computer Engineering, Kumoh National Institute of Technology)
  • Received : 2017.07.11
  • Accepted : 2017.08.18
  • Published : 2017.09.30
Download PDF
⟨ Previous Next ⟩

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.

Keywords

References

  1. H. Babaei, J. Karimpour, and A. Hadidi, "A Survey of Approaches for University Course Timetabling Problem," Computers & Industrial Engineering, Vol. 86, pp.43-59, Aug. 2015. https://doi.org/10.1016/j.cie.2014.11.010
  2. T. B. Cooper, and J. H. Kingston, "The Complexity of Timetable Construction Problems," Proceedings of the 1st International Conference on the Practice and Theory of Automated Timetabling (PATAT 1995), LNCS 1153, pp.281-295, 1996.
  3. C. C. Gotlieb, "The Construction of Class-teacher Timetables," Proceedings of IFIP Congress, pp.73-77, 1962.
  4. S Daskalaki, T. Birbas, and E. Housos, "An Integer Programming Formulation for a Case Study in University Timetabling," European Journal of Operational Research, Vol. 153, No. 1, pp.117-135, Feb. 2004. https://doi.org/10.1016/S0377-2217(03)00103-6
  5. E. K. Burke, J. Marecek, A. J. Parkes, and H. Rudova, "A Branch-and-cut Procedure for the Udine Course Timetabling Problem," Annals of Operations Research, Vol. 194, No. 1, pp.71-87, April 2012. https://doi.org/10.1007/s10479-010-0828-5
  6. S. Yang, and S. N. Jat, "Genetic Algorithms with Guided and Local Search Strategies for University Course timetabling," IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), Vol. 41, No. 1, pp.93-106, Jan. 2011. https://doi.org/10.1109/TSMCC.2010.2049200
  7. Z. Lu, and J. K. Hao, "Adaptive Tabu Search for Course Timetabling," European Journal of Operational Research, Vol. 200, No. 1, pp.235-244, Jan. 2010. https://doi.org/10.1016/j.ejor.2008.12.007
  8. C. Nothegger, A. Mayer, A. Chwatal, and G. R. Raidl, "Solving the Post Enrolment Course Timetabling Problem by Ant Colony Optimization," Annals of Operations Research, Vol. 194, No. 1, pp.325-339. April 2012. https://doi.org/10.1007/s10479-012-1078-5
  9. R. Lewis, "A Survey of Metaheuristic-based Techniques for University Timetabling Problems," OR Spectrum, Vol. 30, No. 1, pp.167-190, Jan. 2008.
  10. R. Dechter, "Constraint Processing," Morgan Kaufmann, 2003.
  11. L. Zhang, and S. Lau, "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, No. 2, pp.55-60, IEEE. Nov. 2005.
  12. C. S. Kim, J. Hwang, G. Yoo, H. Lee, and J. Yoon, "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.
  13. T. A. Duong, and K. H. Lam, "Combining Constraint Programming and Simulated Annealing on University Exam Timetabling," Proceedings of RIVF Conference, pp.205-210, Feb. 2004
  14. L. T. Merlot, N. Boland, B. D. Hughes, and P. J. Stuckey, "A Hybrid Algorithm for the Examination Timetabling Problem," Proceedings of the 4th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2002), LNCS 2740, pp.207-231, 2002.
  15. C. Valouxis, and E. Housos, "Constraint Programming Approach for School Timetabling," Computers & Operations Research, Vol. 30, No. 10, pp.1555-1572, Sep. 2003. https://doi.org/10.1016/S0305-0548(02)00083-7
  16. C. S. Kim, and J. Hwang, "A Constraint Programming Model for Lecture Timetable Optimization," Proceedings of the Korean Society of Computer Information Conference, Vol. 25, No. 1, pp.13-14, 2017.
  17. "ILOG CPLEX Optimization Studio: CP Optimizer User's Manual," V12.6.2, IBM Corporation, 2014.