An improved event selection technique in a modified PSO algorithm to solve class scheduling problems

摘要

In solving class scheduling problems, among the initial steps taken by optimization algorithms is to generate initial solutions. These initial solutions which are random or feasible will be improved iteratively to obtain better solutions. In this iterative process, the re-assignment of events to a new time slot and the selection of event to be reassigned plays an important role in assuring the reassignment process is able to improve the quality of the timetable. This paper proposes an event selection technique namely Event Selection based on Selection Limit (ESSL) applied in a modified PSO algorithm to solve class scheduling problems. This technique was based on Tabu List used in Tabu Search Algorithm. Using this technique, the selection of event in each iteration step will be limited based on percentage selection limit. Five percentage selection limits plus adaptive limit were tested in order to see their effect towards the final penalty of the solution. The performance of the proposed technique was measured based on percentage penalty reduction (%PR) and execution time. Five sets of data from International Timetabling Competition were used in the experiment. The experimental results shows that ESSL with adaptive limit managed to produce the highest percentage of penalty reduction. Furthermore, this technique also managed to reduce the effect of early convergence which is known to be one of the weaknesses of the original PSO.