Open AccessHeuristic and genetic algorithm approaches to the real-world university examination timetabling problem
Author(s) -
İlker Küçükoğlu,
Alkın Yurtkuran
Publication year - 2017
Publication title -
global journal of business, economics and management
Language(s) - English
Resource type - Journals
ISSN - 2301-2579
DOI - 10.18844/gjbem.v7i1.1409
Subject(s) - computer science , genetic algorithm , mathematical optimization , constructive , heuristic , scheduling (production processes) , set (abstract data type) , job shop scheduling , algorithm , artificial intelligence , machine learning , mathematics , process (computing) , schedule , programming language , operating system
Timetabling is one of the computationally difficult problems in scheduling and aims to find best time slots for a number of tasks which require limited resources. In this paper, we examine different solution approaches for the real-world examination timetabling problem (ETP) for university courses. The problem has unique hard and soft constraints, when compared to previous efforts, i.e. consecutive exams, sharing of rooms, room preferences, room capacity and number of empty slots. The aim of the problem is to achieve a timetable, which minimizes the total number of the examination slots without any conflicts. First, the real-world problem is formally defined and a mixed integer linear model is presented. Then, a constructive heuristic and a genetic algorithm based meta-heuristic are proposed in order to solve the ETP. Proposed approaches are tested on a problem set formed by using a real-life data. Results reveal that, proposed approaches are able to produce superior solutions in a limited time. Keywords: Timetabling, constructive heuristic, genetic algorithm;