본문 바로가기
  • Home

Constraint Programming Approach for a Course Timetabling Problem

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2017, 22(9), pp.9-16
  • DOI : 10.9708/jksci.2017.22.09.009
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science
  • Received : July 11, 2017
  • Accepted : August 18, 2017
  • Published : September 29, 2017

Chun-Sik Kim 1 Junha Hwang ORD ID 1

1금오공과대학교

Accredited

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.

Citation status

* References for papers published after 2022 are currently being built.