Artificial Bee Colony Algorithm for Solving Educational Timetabling Problems

Artificial Bee Colony Algorithm for Solving Educational Timetabling Problems

Asaju La’aro Bolaji (Universiti Sains Malaysia, Malaysia, & University of Ilorin, Nigeria), Ahamad Tajudin Khader (Universiti Sains Malaysia, Malaysia), Mohammed Azmi Al-Betar (Universiti Sains Malaysia, Malaysia, & Jadara University, Jordan) and Mohammed A. Awadallah (Universiti Sains Malaysia, Malaysia)
Copyright: © 2012 |Pages: 21
DOI: 10.4018/jncr.2012040101
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

This paper presents an artificial bee colony algorithm (ABC) for Education Timetabling Problem (ETP). It is aimed at developing a good-quality solution for the problem. The initial population of solutions was generated using Saturation Degree (SD) and Backtracking Algorithm (BA) to ensure the feasibility of the solutions. At the improvement stage in the solution method, ABC uses neighbourhood structures iteratively within the employed and onlooker bee operators, in order to rigorously navigate the UTP search space. The technique was evaluated using curriculum-based course timetabling (CB-CTT) and Uncapacitated Examination Timetabling Problem (UETP) problem instances. The experimental results on UETP showed that the technique is comparable with other state-of-the-art techniques and provides encouraging results on CB-CTT.
Article Preview

Introduction

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).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 6: 2 Issues (2017): 1 Released, 1 Forthcoming
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing