Hybrid Cuckoo Search Approach for Course Time-Table Generation Problem

1. Introduction

Course time-table generation (CTTG) problem is a famous combinatorial optimization problem that can be modelled as a member of the constraint satisfaction problem domain. CTTG aims to schedule faculty and venue or rooms, number of subjects of a course, to a specific time slots to satisfy multiple constraints. In this problem quite a few hard or rigid constrains are present which need to be satisfied by the possible solutions. Following the same the endeavour is to enforce an optimization by fulfilling the soft constraints to the maximum extent feasible. Consequently, it acts just like a scheduling problem. The quality of the feasible solution has been evaluated by extent of optimization accomplished through satisfaction of the soft constraints. Though, they are known as NP-Hard problem (Cooper and Kingston, 1996) but may vary with one algorithm to another.

This kind of optimization problem like CTTG is typically solved either by methods of operation research (OR) or using heuristic and metaheuristic local search procedures. A local search optimization method starts with a solitary candidate solution and moves about the search space for an improved solution. In local search techniques there is a possibility to get trapped at the local optima. Recently metaheuristic optimization search techniques, which are population based, are widely used for solving hard or rigid combinatorial problems. These methods commence with several initial solutions selected randomly from the solution space and generate new solutions using the evolutionary techniques. Many of these metaheuristic techniques are motivated by nature (Yang, 2010). In last decade several global search methodologies are proposed (Yang, 2010) (Shelokar, 2007). In these methods population are made to walk around in different path of the solution space so that chances to find the better solution become high. Amongst the global search methods cuckoo search (CS) (Yang and Deb, 2009) is a simple and efficient method applied to solve an extensive range of real-world problems. The Cuckoo search (CS) algorithm is motivated from the breeding procedures of cuckoos, present in some variety of them. Naturally, each cuckoo lays an egg and leaves it in an arbitrary chosen nest of any other bird. If that bird identifies the cuckoo egg, then it either destroys the egg or abandons the nest with an aim to build a new nest. The best nests, where the eggs have not been identified and at the same time the eggs are of good quality will be inherited to the subsequent generation.