A Hybrid Multi-objective Genetic Algorithm with a New Local Search Approach for Solving the Post Enrolment Based Course
The post enrolment based course timetabling problem (PECTP) is one type of university course timetabling problem which a set of events has to be scheduled into time slots and suitable rooms according to students’ enrolment data. This problem is classified
- PDF / 196,196 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 36 Downloads / 176 Views
Abstract The post enrolment based course timetabling problem (PECTP) is one type of university course timetabling problem which a set of events has to be scheduled into time slots and suitable rooms according to students’ enrolment data. This problem is classified as a NP-complete combinatorial optimization problem and hence it is very hard and highly time-consuming to solve the problem to find an optimal timetable. In this paper we have developed a non-dominated sorting genetic algorithm (NSGA-II) hybridized with two local search technique and a tabu search heuristic for solving the multi-objective PECTP. In addition to the original LS technique will be used in NSGA-II, a new LS technique is also used in NSGA-II in order to further improve the performance of NSGA-II, especially reducing violation of the first soft constraint. The algorithm takes advantage of the exploitation ability of two local search techniques and a tabu search heuristic to improve the results obtained in the exploration phase of the NSGA-II. The proposed hybrid approach is tested on a set of standard benchmark problem in comparison with other methods from the literature, and experimental results show that the proposed hybrid approach is able to find promising solutions for solving the multi-objective PECTP.
⋅
Keywords Multi-objective optimization problem Non-dominated sorting genetic algorithm Local search Tabu search Post enrolment based course timetabling problem
⋅
⋅
⋅
D. Lohpetch (✉) ⋅ S. Jaengchuea Faculty of Applied Science, Department of Mathematics, King Mongkut’s University of Technology North Bangkok, Bangkok, Thailand e-mail: [email protected] S. Jaengchuea e-mail: [email protected] © Springer International Publishing Switzerland 2016 P. Meesad et al. (eds.), Recent Advances in Information and Communication Technology 2016, Advances in Intelligent Systems and Computing 463, DOI 10.1007/978-3-319-40415-8_19
195
196
D. Lohpetch and S. Jaengchuea
1 Introduction The post enrolment based course timetabling problem (PECTP) is a one type of university course timetabling problem (UCTP), and it is the assignment of university courses to suitable room and time slots according to students’ enrolment data. The timetable is constructed after student enrolment in a way that all students can attend the events which they want to enroll. The PECTP is based on real world situation where students are given choices of events that they want to attend and a timetable is produced according to these choices. Usually, the UCTP is a NP-complete [1] and is classified as a combinatorial optimization (CO) problem [2]. As a result, this problem is very difficult to find the optimal solution which often leads to too high computational times. Many works have taken the PECTP as a single objective optimization problem by combining multiple criteria into a single scalar value and then minimizing the weighted sum of constraint violations as the only one objective function [3]. On the other hand, few works have tackled the PECTP as a multi-objective optimi
Data Loading...
