정수계획법을 이용한 대학강의 시험시간 및 강의실 배정 문제의 풀이
The University Examination And Course Timetabling Problem With Integer Programming
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In this paper, we study the university timetabling problem, which consists of two subproblems, the university course timetabling problem and the examination timetabling problem. Given a set of classrooms, students, teachers, and lectures, the problem is to assign a number of courses (and examinations) to suitable timeslots and classrooms while satisfying the given set of constraints. We discuss the modeling and solution approaches to construct course and examination timetables for one of the largest Korean university. By using binary integer programming formulations, we describe these two complex real-world problems. Then, we propose a solution method, called NOGOOD, to solve the examination timetabling model. The computation results show that NOGOOD finds the optimal examination schedule for the given instance. Although we consider a specific instance of the university timetabling problem, the methods we use can be applicable to modeling and solving other timetabling problems.
Abstract
In this paper, we study the university timetabling problem, which consists of two subproblems, the university course timetabling problem and the examination timetabling problem. Given a set of classrooms, students, teachers, and lectures, the problem is to assign a number of courses (and examinations) to suitable timeslots and classrooms while satisfying the given set of constraints. We discuss the modeling and solution approaches to construct course and examination timetables for one of the largest Korean university. By using binary integer programming formulations, we describe these two complex real-world problems. Then, we propose a solution method, called NOGOOD, to solve the examination timetabling model. The computation results show that NOGOOD finds the optimal examination schedule for the given instance. Although we consider a specific instance of the university timetabling problem, the methods we use can be applicable to modeling and solving other timetabling problems.
참고문헌 (26)
- M. W. Carter, "A Survey of Practical Applications of Examination Timetabling Algorithms", Operations Research, 34(2), pp.193~202 (1986)
- A. Schaerf, "A Survey of Automated Timetabling", Artificial Intelligence Review, 13(2), pp.87~127 (1999)
- H. Babaei, "A Survey of Approaches for University Course Timetabling Problem", Computers & Industrial Engineering, 86, pp.43~59 (2015)
- M. Dimopoulou, "Implementation of a University Course and Examination Timetabling System", European Journal of Operational Research, 130(1), pp.202~213 (2001)
- M. R. Garey, "Computers and Intractability-A Guide to the Theory of NP-compleness" (1979), Freeman
- M. Cangalovic, "Exact Coloring Algorithms for Weighted Graphs Applied to Timetabling Problems with Lectures of Different Lengths", European Journal of Operational Research, 51(2), pp.248~258 (1991)
- D. De Werra, "Practice and Theory of Automated Timetabling", pp.296~308 (1996), Springer
- D. De Werra, "The Combinatorics of Timetabling", European Journal of Operational Research, 96(3), pp.504~513 (1997)
- S. Daskalaki, "Efficient Solutions for University Timetabling Problem through Integer Programming", European Journal of Operational Research, 160(1), pp.106~120 (2005)
- N. Boland, "New Integer Linear Programming Approaches for Course Timetabling", Computers and Operations Research, 35(7), pp.2209~2233 (2008)
- S. A. MirHassani, "A Computational Approach to Enhancing Course Timetabling with Integer Programming", Applied Mathematics and Computation, 175(1), pp.814~822 (2006)
- K. Schimmelpfeng, "Application of a Real-world University Course Timetabling Model Solved by Integer Programming", OR Spectrum, 29(4), pp.783~803 (2007)
- S. M. Al-Yakoob, "Mathematical Models and Algorithms for a High School Timetabling Problem", Computers and Operations Research, 61, pp.56~68 (2015)
- A. Hertz, "Tabu Search for Large Scale Timetabling Problems", European Journal of Operational Research, 54(1), pp.39~47 (1991)
- J. Aubin, "A Large Scale Timetabling Problem", Computers and Operations Research, 16(1), pp.67~77 (1989)
- A. M. Barham, "A Simple Heuristic to Facilitate Course Timetabling", Journal of the Operational Research Society, 29(11), pp.1055~1060 (1978)
- D. Johnson, "Timetabling University Examinations", Journal of the Operational Research Society, 41(1), pp.39~47 (1990)
- M. Wright, "School Timetabling Using Heuristic Search", Journal of the Operational Research Society, 47(3), pp.347~357 (1996)
- I. V. Katasaragkis, "A Comparative Study of Modern Heuristics on The School Timetabling Problem", Algorithms, 8(3), pp.723~742 (2015)
- A. L Bolaji, "University Course Timetabling Using Hybridized Artificial Bee Colony with Hill Climbing Optimizer", Journal of Computational Science, 5(5), pp.809~818 (2014)
- B. Naderi, "Modeling and Scheduling University Course Timetabling Problems", International Journal of Research in Industrial Engineering, 5(1-4), pp.1~15 (2016)
- E. K. Burke, "A Graph-based Hyper-heuristic for Educational Timetabling Problems", European Journal of Operational Research, 176(1), pp.177~192 (2007)
- P. De Causmaecker, "A Decomposed Metaheuristic Approach for a Real-world University Timetabling Problem", European Journal of Operational Research, 195(1), pp.307~318 (2008)
- L. Zhang, "Constructing university timetable using constraint satisfaction programming approach", Proceedings of the 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)
- M. W. Carter, "Practice and Theory of Automated Timetabling", pp.1~21 (1996), Springer
- A. Akbulut, "University Exam Scheduling System Using Graph Coloring Algorithm and RFID Technology", International Journal of Innovation, Management and Technology, 4(1), pp.66~72 (2013)