제약 프로그래밍 기반 자동화된 수업 시간표 작성 시스템
A Constraint Programming-based Automated Course Timetabling System
1
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
The course timetabling problem is a kind of very complex combinatorial optimization problems, which is known as an NP-complete problem. Sometimes a given course timetabling problem can be accompanied by many constraints. At this time, even if only one constraint is violated, it can be an infeasible timetable. Therefore, it is very difficult to make an automated course timetabling system for a complex real-world course timetabling problem. This paper introduces an automated course timetabling system using constraint programming. The target problem has 26 constraints in total, and they are expressed as 24 constraints and an objective function in constraint programming. Currently, we are making a timetable through this system and applying the result to the actual class. Members’ satisfaction is also much higher than manual results. We expect this paper can be a guide for making an automated course timetabling system.
Abstract
The course timetabling problem is a kind of very complex combinatorial optimization problems, which is known as an NP-complete problem. Sometimes a given course timetabling problem can be accompanied by many constraints. At this time, even if only one constraint is violated, it can be an infeasible timetable. Therefore, it is very difficult to make an automated course timetabling system for a complex real-world course timetabling problem. This paper introduces an automated course timetabling system using constraint programming. The target problem has 26 constraints in total, and they are expressed as 24 constraints and an objective function in constraint programming. Currently, we are making a timetable through this system and applying the result to the actual class. Members’ satisfaction is also much higher than manual results. We expect this paper can be a guide for making an automated course timetabling system.
참고문헌 (11)
- E. Tsang, "Foundations of Constraint Satisfaction" (1993), Academic Press
- H. Babaei, "A Survey of Approaches for University Course Timetabling Problem", Computers & Industrial Engineering, 86, pp.43~59 (2015)
- "International Timetabling Competition" (2001)[URL]
- The Second International Timetabling Competition: Curriculum-based Course Timetabling (Track 3), "L. di Gaspero", Queen's University, ~ (2007)
- S. Abdullah, "On the Use of Multi Neighbourhood Structures within a Tabu-based Memetic Approach to University Timetabling Problems", Information Sciences, 191, pp.146~168 (2012)
- R. Bellio, "Feature-based Tuning of Simulated Annealing Applied to the Curriculum-based Course Timetabling Problem", Computers & Operations Research, 65, pp.83~92 (2016)
- A. Bettinelli, "An Overview of Curriculum-based Course Timetabling", TOP, 23(2), pp.2~37 (2015)
- H. H. Kim, "An University Timetabling System Using Genetic Algorithm", Journal of Science &Culture, 2(1), pp.333~342 (2005)
- 안남수, "수리적 모델링을 통한 강의실 배정문제 해법에 관한 연구", 한국산학기술학회논문지, 18(10), pp.580~587 (2017), 한국산학기술학회[DOI]
- 김춘식, "수업 시간표 작성을 위한 제약 프로그래밍 접근법", 한국컴퓨터정보학회논문지, 22(9), pp.9~16 (2017), 한국컴퓨터정보학회[DOI]
- "IBM Decision Optimization CPLEX Modeling for Python, V2.9", IBM Corporation, ~ (2019)