Hybrid Cuckoo Search Approach for Course Time-Table Generation Problem

Hybrid Cuckoo Search Approach for Course Time-Table Generation Problem

Subhasis Mallick (B.P. Poddar Institute of Management and Technology, India), Dipankar Majumdar (RCC Institute of Information Technology, India), Soumen Mukherjee (RCC Institute of Information Technology, India) and Arup Kumar Bhattacharjee (RCC Institute of Information Technology, India)
Copyright: © 2020 |Pages: 17
DOI: 10.4018/IJAMC.2020100110

Abstract

Course time-table generation (CTTG) is a combinatorial optimization problem which largely fits into the family of scheduling problems. It attempts to schedule a number of subjects to particular time slots in an order to satisfy multiple numbers of constraints. A solution of CTTG generates a weekly schedule for each course satisfying several constraints regarding the order of classes, preference of teachers, and other institutional constraints. Automated generation of the course timetable is a problem of optimization that requires satisfying maximum constraints and can be solved with a search-based optimization technique. This article proposes a novel hybrid Cuckoo search approach for solving the Course Time-Table Generation (CTTG) problem for high schools affiliated to the West Bengal Board of Secondary Education (WBBSE), India. The authors investigate the performance of local search Hill climbing against the population-based basic Cuckoo search algorithm on the problem. Thereafter they propose a hybrid Cuckoo search technique that improves the performance significantly showed by ANOVA.
Article Preview
Top

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2021): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing