Application of Quantum Evolutionary Algorithm to Complex Timetabling Problem

by Open Science Repository Computer and Information Sciences
(April 2013)

Abstract


Organizations like universities and schools use timetables to schedule lectures and lab sessions in a way that makes best use of resources available. Making a good timetable is a scheduling problem. It is NP-hard, multi-constrained, complex and a combinatorial optimization problem. The solution of this problem cannot be obtained in polynomial time. Therefore, this problem has captured great attention of researchers for last more than four decades.

Researchers have tried to develop an automated system to solve this problem using various heuristics (e.g. Graph Colouring etc.), local search techniques (e.g. Simulated Annealing and Tabu Search) etc. Some researchers have also employed Evolutionary Algorithms (mainly Genetic Algorithms and its variants) which is a good technique for solving complex problems having very large search space. This paper implements a novel quantum evolutionary algorithm(QEA) to solve the time tabling problem of Dayalbagh Educational Institute (Deemed University).

Keywords: scheduling problem, evolutionary algorithm, quantum evolutionary algorithm.

Full text


Application of Quantum Evolutionary Algorithm to Complex Timetabling Problem


Click here to post comments

Return to journal abstracts.