At the forefront of Artificial Intelligence

Home » Articles » Genetic Algorithms » Timetabling

Using GA for the Timetabling Problem

By Jasni Ahmad

Faculty of Information Technology

Universiti Utara Malaysia, 06010 UUM Sintok, Kedah, Malaysia

Tel.: +(604) 9284785, Fax: +(604) 04-9284753

E-mail: jasni@uum.edu.my

Introduction

The study examines the Genetic Algorithms (GA) approach in solving the examination time tabling problem in examination dataset. The methodology is concerned with the classification analysis of imprecise, uncertain or incomplete information or knowledge expressed in terms of data extract from student and examination. The algorithm is experimented with three examination datasets i.e. Course, Examination and Student datasets. The experimental results are compared with traditional or manually approach. It is shows that good capability to rearrange the position of clusters in the sequence to derive the highest score and presents the process of well organized method on how to list the number of courses registered for the examination efficiently. The optimal sequencing clustering is found by using the GA method. GA is capable to find better solutions to this problem, to represent a single solution to the problem in a single data structure, to create a population of solutions based on a sample data structure and to operate on the population to evolve the best solution. The system is able to find a good solution to this problem by rapidly computes and quickly converges to a realistic solution.

Purpose of Clustering

Student’s data clustering is a technique for automatically discovering a set of data and grouping the data by those courses. The ultimate goal of clustering is to find exactly information about the student’s course. Clustering operates by analyzing a data set and groups them into clusters, so that data set within a cluster is similar to each other [4]. For example, course (title, code, unit, type), student (name, number, IC number), year, address, school name and etc. Student’s data can be integrated with examination’s data, in order to get the sequence of clusters of examination. Here is an example of examination’s data; i.e. date of examinations, course title, course code, place, list of course registered, list of student’s information and etc. The purpose of clustering is to ease sequencing in the next process. Every component in the same cluster has some similarities, so could be grouped. The number of clusters then will queue in certain order form, subjected to specific criteria.

Problem Statement

The objective of this research is to develop one algorithm or methodology to select the best sequence of clusters for examinations. In order to represent this, the algorithm must be able to rearrange the position of clusters in the sequence to derive the highest score. A set of cluster consists of the courses registered for the examinations. Each cluster may contain different numbers of courses. Each course is identified by a unique number i.e. the cluster, which is provided in the input database. The number of student are registered for every course. So, each course has different number of students as shown in Figure 1.

Figure 1 Course and Cluster

It is assumed that the examination, course and student data information to be used, have been selected. The period of examination, date and location are known, but the appropriate sequence of clustering is unknown. The number of clusters has been chosen. The algorithm developed should rapidly compute and quickly converge to realistic solutions.

The algorithm must provide a set of sequence of clusters and choose the best among them. The score or penalty will be given for each sequence of clusters based on this. The highest score for a certain sequence of clusters will be declared as the winner (best) as shown in Figure 2.

Operators and Parameters. From the GA outline, crossover and mutation are the most important part of the genetic algorithm. The performance is influenced mainly by these two operators.

Figure 2 Sequence of clusters

Materials and Methods

Input Data Form

The input database (provided) consists of, Examination’s data (different number of courses with code number, different number of students registered for the exam, for each course, list of the same courses (same syllabus) with different code number), Student’s data (student’s information such as IC number, different courses that have been registered by each student), Course’s data (the list of all courses that have been registered by student, the unique number of cluster given for each course).

Output Data Form

The output produced by the system is a list of numbers of clusters arranged linearly. It is based on a certain criteria during the processing stage as shown in Figure 3. This sequence of cluster is the best among all because it carries the highest penalty. The location for each cluster depends on the criteria for the examinations.

Figure 3 Sequence of clusters

Genetic Algorithms (GA)

The algorithm is started with a set of solutions (represented by chromosomes) called population. Solutions from one population are taken and used to form a new population. This is motivated by a hope that the new population will be better than the old. Reforming solutions are subjected to their fitness – the more suitable they are the more chances they have to produce [11]. This is repeated until some conditions (for example number of population or improvement of the best solution) are satisfied.

Encoding of a Chromosome The chromosome should in some way contain information about solution where it represents. The most popular way of encoding is a binary string as shown in Figure 4. Each chromosome has one binary string. Each bit in this string can represent some characteristic of the solution.

Figure 4 The binary string of chromosome

Crossover Crossover selects genes from parent chromosomes and creates a new offspring. The simplest way on how to do this is to choose some crossover point randomly and everything before this point copies from the first parent and then everything after the crossover copies from the second parent [11]. Mutation This is to prevent fall all solutions in population into a local optimum of solved problem. Mutation changes randomly the new offspring. For binary encoding we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. Mutation depends on the encoding as well as the crossover.

Constraint & Criteria

The basic problem that was faced by the author consists of a few constraints and two criteria. The author tried to consider this constraint during the process of implementations.

Constraint The hall capacity for any period should not be exceed, two exams may need to be rescheduled at the same time, as they contain similar material, an exam may need to be rescheduled in a particular period, or within a limited set of period and an exam may require a particular room.

Criteria In this system, the author highlights two important criterias that can be used for evaluating the fitness of each cluster in the population (sequence of clusters). The evaluation is based on the single population and gives the score for each of them. In order to fit for each population, the system must give the score or penalty based on these 2 criterias:

First criteriaThe large number of courses registered for examinations by student must be located in cluster 1, and followed by cluster 2 and so on. The number of courses in cluster 2 is less than cluster1 and followed by cluster 3. The clusters are located in sequence order. The last cluster (n) of the population has small number of courses registered among that population as shown in Figure 5.

Figure 5 Clusters of population

Second criteria Calculate the number of rows for each student located in each cluster in the population. Every student in one population must have a gap between the courses in sequence order. If one student in that population is located close clusters without any gap (many in the rows), the system assumes that this population is bad and gives low score. The best population must have less than (< 3 rows) number of rows that the students locate at each cluster in the population as shown in Figure 6.

Conclusions

Sequencing clusters system can present the process of well organized on how to list the number of courses registered for the examination more efficiently as compared to traditional methods. The optimal sequencing clustering is found by using Genetic Algorithms (GA) approach. GA is able to find good solution to the problem by rapidly compute and quickly converges to realistic solutions.

References

[1] Rudi von Varendorff © KBE Optimization in Scheduling Using Genetic Algorithms URL: /http://www.kbe.co.za/usergrps/usergrp1997/rudi-ga/ga-intro.htm

[2] Dr. Steffen Schulze-Kremer. Genetic Algorithms and Protein Folding Westfälische Strasse 56, D-10711 Berlin, FRG

[3] “GAlib: A C++ Library of Genetic Algorithm Components” version 2.4, Documentation Revision B, August 1996, Matthew Wall Mechanical Engineering Department.

[4] SEARCH'97 Developer's Kit Advanced Features Guide V2.1.3, Part Number DM0233, February 26, 1997. URL: /http://www.verity.com/support/documentation/s97dk/adv213/advcover.htm

[5] Mark H. Noschang. The Traveling Salesman Problem - a Review of Theory and Current Research, University of Cincinnati.

[6] Matthew's Portfolio. Introduction to Genetic Algorithms

[7] Teorey, T.J. / G. Wei / D.L. Bolton / J.A. Koenig. ER Model Clustering as an Aid for User Communication and Documentation in Database Design, Communications of the ACM, 32. 1989.

[8] Vermeir, D.: Semantic Hierarchies and Abstractions in Conceptual Schemata, Information Systems, 8/2. 1983.

[9] Feldman, P. / D. Miller. Entity Model Clustering: Structuring a Data Model by Abstraction. The Computer Journal, 29.1986.

[10] E.K. Burke, J.P. Newall, R.F. Weare A Simple Heuristically Guided Search for the Timetable Problem, Automated Scheduling and Planning Group, Department of Computer Science, University of Nottingham, Nottingham NG7, 2RD, UK.

[11] Marek Obitko. URL: /http://cs.felk.cvut/~xobitko/ga. 1998.

Submitted: 29/05/2005

Article Toolbar

BibTeX entry