An introduction of preference based stepping ahead firefly algorithm for the uncapacitated examination timetabling

Abstract

In recent times, there has been a growing attention to intelligent optimization algorithms centred on swarm principles such as the firefly algorithm (FA). It was proposed for the continuous domain that mimics the attraction of fireflies to flashing light and has been used in discrete domains via modification. A discrete domain that is a major challenge in most higher education institutes (HEI) is examination timetabling. This article presents a new methodology based on FA for uncapacitated examination timetabling problems (UETP) where the proposed method is an extension of earlier work by the authors on the continuous domain. UETP is considered in this article as it is a university examination timetabling problem, which is still an active research area and has not been solved by FA algorithm as per authors knowledge. The proposed method concentrates on solving the initial solution using discrete FA where it consolidates the reordering of examinations and slots through a heuristic ordering known as neighborhood search. Three neighborhoods are employed in this research, where one is used during the initialization phase while two are utilized during solution improvement phase. Later, through preference parameters, a novel stepping ahead mechanism is used, which employs neighborhood searches built on previous searches. The proposed method is tested with 12 UETP problems where the preference based stepping ahead FA creates comparative results to the best ones available in the literature for the Toronto exam timetabling dataset. The results obtained are proof of concept at the preliminary stage and require further experiments on other educational datasets such as the second international timetable competition benchmark sets. The newly introduced preference based stepping ahead mechanism takes advantage of the current best solution space where it exploits the solution space for better solutions. This paves the way for researchers to utilize the mechanism in other domains such as robotics, etc.

Keywords

• Optimization
• Swarm intelligence
• Meta-heuristic algorithm
• Stepping-ahead
• Preference
• Uncapicitated exam timetabling problem