Article Preview
TopIntroduction
Bio-inspired algorithms are general-purpose stochastic search techniques mimicking natural evolution phenomena. One important reason for the success of bio-inspired algorithms is the ability to navigate the problem search space using different operators which prevents them from getting stuck in the local optima and therefore increases the possibility of finding global optima. As a result, bio-inspired algorithms could be viewed as global search techniques which are successfully applied by researchers to solve a wide range of timetabling problems. Some examples of commonly used bio-inspired algorithms include: Artificial Immune System (AIS) (Malim, Khader, & Mustafa, 2006), Ant Colony Optimisation (ACO) (Socha, Sampels, & Manfrin, 2003), Firefly Algorithm (Yang, 2009), Genetic Algorithm (GA) (Abdullah, Turabieh, McCollum, & Burke, 2010), Harmony Search Algorithm (Al-Betar & Khader, 2008) and Particle Swarm Optimisation (Sheau Fen Ho, Safaai, & Hashim, 2009). Artificial Bee Colony Algorithm (ABC) is a search method motivated by the foraging behavior of honeybee swarm, and target complex optimization problems. The ABC algorithm that was developed by Karaboga in 2005 is a population-based heuristic algorithm.
One of the most common example of scheduling problems is Educational Timetabling Problem (ETP), which could be described as the scheduling of resources for assignments under predefined constraints, such that it enhances the possibility of allocation or reduces the violation of such constraints (Thanh, 2007). ETP is a difficult administrative process, which needs to be repeated every semester in academic institutions such as universities and colleges. ETP has also been reported to be a hard combinatorial optimisation problem (Johnson & Garey, 1979), and was tackled using different approaches by workers of operational research and artificial intelligence. Generally, operation of ETP could be defined as the assignment of a set of events (courses or exams) to given timeslots and rooms, based on some given constraints. Two types of constraints peculiar to timetabling problems are hard and soft constraints; the hard constraints must be strictly satisfied in the solution to be feasible yet, the quality of the solution is determined by satisfying the soft constraints satisfaction. Furthermore, ETP can be classified into three categories: course timetabling problem, examination timetabling problem and school timetabling problem. Therefore, this study considered both course and examination timetabling problems. In order to tackle the problems, two neighbourhood structure mechanisms are incorporated within the operators of ABC for CB-CTT while three neighbourhood structures are used for UETP. For the purpose of evaluation, a dataset established by ITC-2007 is used for the course timetabling problem whereas the Carter Dataset is used for the examination timetabling problem.
The last three decades have witnessed tremendous application of techniques to educational timetabling problem. These techniques range from constraints and mathematical programming techniques (Cambazard et al., 2012; De Causmaecker et al., 2009; Goltz & Matzke, 1998); local search based techniques such as simulated annealing (Abdullah et al., 2010; Burke et al., 2004; McCollum, 2010; Thompson & Dowsland, 1998), great deluge (Burke & Bykov, 2006; Landa-Silva & Obit, 2009), Tabu search (White & Xie, 2001; White et al., 2004), hybrid techniques such as (Abdullah et al., 2007; Burke et al., 2005; Turabieh & Abdullah, 2011), population and nature-inspired based techniques (Eley, 2006; Nothegger et al., 2012; Al-Betar et al., 2010; Al-Betar & Khader, 2008), and so on. The comprehensive survey of methodologies used in educational timetabling problem can be found in Burke and Petrovic (2002), Lewis (2008), Qu et al. (2009), and Schaerf (1999).