Performance Comparison of Linear and Non-Linear Great Deluge Algorithms in Solving University Course Timetabling Problems

摘要

Different institutions may have their own requirements in course timetabling for every semester and thus it is difficult to produce a general methodology to solve all the problems in every institution. This research compares both linear and non-linear Great Deluge (GD) algorithms insolving university course timetabling problem (UCTP) and the sample dataset is obtained from the Universiti Malaysia Sabah, Labuan International Campus (UMSLIC), Malaysia. In this paper, the violation of soft constraints is minimized and the performances of both linear and non-linear GD arecompared. This research does not focus on hard constraints involved as the initial solution is solved based on Constraint Programming algorithm. The GD algorithm is tested over three benchmark datasets: testing dataset; semester 2 session 2014/2015 test set; semester 1 session 2015/2016 testset. Based on the experiment’s results obtained, it shows that linear GD is able to produce better solutions in one of the datasets and the same applies to non-linear GD. Hence, it can be deduced that these results able to satisfy the “No Free Lunch (NFL)” theorem, whereexisting optimization algorithms might not be able to perform well in all datasets. The reason may be due to the constraints involved varied for each dataset as the optimization problems solved by any algorithms are uniformed in relation to the NFL theorems.