An Integer Program and a Hybrid Genetic Algorithm for the University Timetabling Problem

DC Field Value Language
dc.description학위논문 (석사)-- 서울대학교 대학원 : 산업공학과, 2014. 8. 문일경.-
dc.description.abstract대학교 강의 시간표 작성문제는 오랜 기간 동안 많은 연구자들에 의해 꾸준히 연구되어 왔다. 이 문제를 풀기 위해 선형 알고리즘과 수리적 모델, 휴리스틱, 메타휴리스틱 등의 다양한 접근 방법들이 제시되어왔다. 본 연구에서는 주기성제약과 연속성제약을 고려한 대학교 강의 시간표 작성문제를 풀기 위해서 정수 계획법을 이용한 수리적 모렐링과 휴리스틱 알고리즘, 복합 유전 알고리즘을 제시한다. 정수 계획법의 사용은 제약식의 추가가 쉬우며 그 해의 정확성이 높은 장점을 가지지만, 대학교 강의 시간표 문제가 NP- hard 이므로 문제의 크기가 커질 경우 해를 찾는 데에 비효율성을 보인다. 따라서 큰 문제를 효율적으로 풀기 위해서 좌상배치전략을 포함한 휴리스틱 알고리즘 및 복합 유전 알고리즘을 개발하였다. 본 연구에서 설행한 두 가지 설험의 목적은 각각 주기성제약과 연속성제약을 갖는 수엽 비율에 따른 강의 배치 효율의 비교와 정수 계획법, 휴리스틱 알고리즘, 복합 유전 알고리즘의 성능 비교이다. 실험에서 정수 계획법은 FICO사의 Xpress-IVI 7.3버전으로 구현하였고, 휴리스틱 알고리즘 빛 복합 유전 알고리즘은 자바 프로그래밍 언어로 구현하였다. 첫 번째 실험을 통해서는 정수 계획법으로 도출한 최적해의 비교를 통해서 연속성제약을 갖는 수업의 비율이 높을수록 배치되지 못한 강의의 수가 작아지는 것을 확인할 수 있다. 두 번째 실험에서는 문제의 크기가 커지더라도 복합 유전 알고리즘의 해 성능은 좋게 나타나는 것을 불 수 있다.-
dc.description.abstractThe university timetabling problem (UTP) has been studied by numerous research groups for decades. The studies were conducted through various methods including linear algorithms, mathematical models, heuristics, and metaheuristics. In this paper, an integer program, a heuristic algorithm, and a hybrid genetic algorithm are used to solve the UTP characterized by real-world constraints such as periodicity and consecutiveness. The integer program can be used to efficiently alter constraints and improve accuracy. However, it is inefficient with large problems, because the UTP is NP-hard problem, so a heuristic algorithm with left upper strategy and a hybrid genetic algorithm were developed. The first experiment showed the effects of the periodicity and consecutiveness constraints ratio and the second experiment compared the performances of the heuristic and hybrid genetic algorithms with small, medium, and large problems. The integer program was coded in FICO Xpress-IVE version 7.3, and the heuristic and the hybrid genetic algorithm were implemented in Java programming language. The results illustrate that the higher ratio of the lectures with consecutiveness constraints deducted the better objectives. For larger problems, the IP could not reach the optimum within 7200 seconds, and the hybrid genetic algorithm yielded better solutions than the heuristic algorithm.-
dc.description.tableofcontentsChapter 1. Introduction
1.1 Background and purpose
1.2 Related works

Chapter 2. A Mathematical Model
2.1 Problem description
2.1.1 General features of the university timetabling problem
2.1.2 Rules for timetabling in the university
2.2 Integer program formulation

Chapter 3. Heuristic Algorithm
3.1 Left upper strategy
3.2 Flow of the heuristic algorithm

Chapter 4. A Hybrid Genetic Algorithm
4.1 Chromosome representation
4.2 Population initialization
4.3 Chromosome decoding
4.4 Genetic operator
4.4.1 Chromosome selection
4.4.2 Crossover and mutation
4.5 Updating the population and stopping criteria

Chapter 5. Computational Experiments
5.1 Experiment setting
5.2 Experiment 1
5.3 Experiment 2

Chapter 6. Conclusions


dc.format.extent8520248 bytes-
dc.publisher서울대학교 대학원-
dc.subjectUniversity timetabling problem-
dc.subjectInteger program-
dc.subjectHeuristic algorithm-
dc.subjectHybrid genetic algorithm-
dc.subject대학교 강의시간표 작성문제-
dc.subject정수 계획법-
dc.subject휴리스틱 알고리즘-
dc.subject복합 유전 알고리즘-
dc.titleAn Integer Program and a Hybrid Genetic Algorithm for the University Timetabling Problem-
dc.citation.pagesvi, 48-
dc.contributor.affiliation공과대학 산업공학과-
Appears in Collections:
College of Engineering/Engineering Practice School (공과대학/대학원)Dept. of Industrial Engineering (산업공학과)Theses (Master's Degree_산업공학과)
Files in This Item:
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.