CHAPTER 1
INTRODUCTION
1.1 Introduction:
In a university or in a college exam timetabling is a difficult problem. Exam timetabling should be done three times an academic year in a university. We should consider lots of rules to develop an exam timetable for a particular department such as Computing.
In this project "Exam timetabling using constraint satisfaction", we consider Computing department to create a time table by keeping all the constraints in mind. We need to develop user friendly software to produce exam timetables for Computing department. The software which we are going to develop should satisfy all the possible constraints and it should be user friendly.
In the system which we are going to develop, users do not need to type the full name of the cohorts and modules. There will be some dropdown lists by which user can easily select the particular cohorts and modules. For this we should use java programming with a constraint satisfaction java library.
1.2 Constraint satisfaction Definition:
"Constraint satisfaction is the logical problem solving language which is used in conjunction with any programming language, to find a solution to a particular problem by solving some conditions". These conditions are which the variables we used should satisfy, and they are called as constraints. Here we should consider the constraints like, a student who is studying a particular cohort should not have exams on successive days, a common module which is studied by students of different cohorts should be scheduled at the same time, and two modules of the same cohort should not be scheduled on the same day. The delivered system should satisfy all these constraints and create an exam timetable.
Problems based on constraints of a finite domain are generally solved by using search criteria. The general forms of search criteria which we use in constraint satisfaction problems are backtracking and local search.
The constraint propagation method may solve the problem or may prove it as unsolvable. To make the given problem simple to solve we can use the constraint propagation method combined with search criteria.
There are several types of constraint programming libraries which we can use in the project. Since we are using java programming for user interface we need a constraint solving java library. Chocó is the appropriate constraint java library which is easy to use with java programming. We are going to discuss Chocó in detail in a later section.
1.3 What is Backtracking?
Backtracking is the process of finding a solution to a problem by trying all possible choices. In this process if a choice is incorrect, the process will be abandoned and starts from another possible choice. [5]
The best example for this backtracking process is n queens' puzzle. In this example n queens should be arranged such that no queen attacks any other queen.
In this n-queens problem, if we consider n=4, the 4-queens should be arranged on a 4*4 chess board such that no queen attacks the other one. This problem can be easily solved by using Back tracking method.
In this problem the constraints are:
No two queens should be in the same column.
No two queens should be in the same row.
No two queens should be in the same diagonal.
Make a chart with all possible solutions.
Test the solution one by one.
If the path is not fruitful then mark it as a dead end.
Then undo last trial, and then test the next solution.
By using the back tracking method, first we should arrange one queen in the first column in all possible ways, that is 1st row of 1st column, 2nd row of 1st column, 3rd row of 1st column and 4th row of 1st column.
Later we should arrange second queen in the next column by solving all the constraints. If the trial is not fruitful then we should terminate that and make another possible trial.
So that by solving all the constraints, and terminating unfruitful trials, one solution will be achieved.
CHAPTER 2
2.1 Aims and Objectives
The manual process of exam timetabling in a university is very much time consuming. So the main aim of this project is to build a software tool to create exam timetables for a university and the application should be user friendly. This is explained briefly below.
To analyse the process of exam timetabling which the university was originally following, because it is a manual process. This analysis of existing manual process will help us in developing software.
We should make a list of all possible constraints which should be satisfied by the developed system.
The study of constraint satisfaction programming and analyse it, which is helpful in developing the exam timetabling tool.[4]
To gain an understanding of constraint satisfaction tool like choco which we are using in the development process.[4]
The delivered system should be user friendly, so that user can use the system easily. Here in exam timetabling tool, the user should input cohort name and module name. Instead of typing complete name of the cohort and module we put a dropdown list of all cohorts and modules by which the user can easily select them. By this the chance of a manual error like incorrect typing will be restricted.
2.2 MOTIVATION:
I am very much interested in solving logical puzzles like SUDOKU. By solving logical puzzles we can improve concentration power. I always think about creating code to solve this type of logical puzzle. To solve this type of logical puzzle constraint satisfaction programming is used. It allows us to solve puzzles like this easily. It is an interesting part of artificial intelligence.
2.3 Features:
User allowed adding modules to a cohort by using dropdown menus.
User can make changes to the selected modules and cohorts.
User can choose the starting date of the examination.
User can save the selected data as we are using a database. So that user can view his data after reopening the application as well.
2.4 KEY TECHNIQUES:
Java programming.
Constraint satisfaction programming using Chocó.
Oracle database for data storage and retrieval.
2.5 SYSTEM REQUIREMENTS:
HARDWARE REQUIREMENTS:
Pentium III processor with 800MHz.
1GB RAM. Because oracle 10g database and java code developing tool must be on the run mode at the same time.
20 GB HDD.
These are all minimum hardware requirements for this project.
SOFTWARE REQUIREMENTS:
Windows XP operating system.
Oracle 10g relational database management system.
My Eclipse tool for developing the java code.
Chocó 2.1.0 version for constraint satisfaction programming.
These are all minimum software requirements for this project.
CHAPTER 3
SYSTEM ANALYSIS
3.1 Existing system:-
The existing system of creating exam timetable in a university takes three months or more time. This existing process has much manual effort. Exam timetabling department issues the timetables for every exam of every student in the whole university. The Exam timetabling department should send a draft to the entire departments in the university at least one month before the starting date of examination to receive there assurance.
It should consider some constraints like:
- We should schedule the exams for modules which have a large number of students in first week. Because if higher number of students writing the same exam which held on end of the week, there will be problem of delay of correction.
- We should create afternoon schedules to make proper use of invigilation. That is according to the availability of Invigilators we can use some of the Invigilators in afternoon schedule.
- We should consider the students with special needs; they may be allowed extra time to complete an exam.
- A student should have an exam with at least a day gap, so that the student has time to revision.
3.2 Proposed system:-
The software which we are going to develop should solve all possible constraints and create a proper timetable.
Software allows the user to add modules to a cohort by using drop down menus. The user can also make changes to the selected modules list.
User is allowed to select a date from when the examination should start. According to the selected list of cohorts, modules and starting date of exams the timetable will create.
CHAPTER 4
SOFTWARE TOOLS DISCUSSION
4.1 Constraint programming:
"Constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that satisfies all constraints". [1]
A constraint satisfaction problem (CSP) is defined by a set of variables each having a specific domain and a set of constraints each involving a set of variables and restricting the values that the variables can take simultaneously. The solution to a CSP is an assignment that maps every variable to a value. We may want to find just one solution, all possible solutions or an optimal solution given some objective function defined in terms of some or all variables.[8]
A general constraint problem consists of:
A set of variables X={x1, x2… xn}.
For each variable xi a finite set Di of its possible values (its domain). D= {D(x1), D(x2) …D(xn)}.
A set of constraints restricting the values that the variables can take. C= {C1, C2… Cj}. [9]
4.2 Constraints solver:
To solve the considered Constraints we need a constraint satisfaction tool which can combine with the programming language like java. Lots of constraint satisfaction java libraries are available. Some of those are:
Choco
JCL
Koalog
JCHR
CREAM
JaCop.
Among these constrain satisfaction java libraries we are using choco in this project.
Choco is built on an event-based propagation mechanism with backtracking structures.
Choco involves three types of domain variables:
Integer variable.
Set variable.
Real variable.
According to our requirement we can use any of these domain variables.
Choco gives clear separation between the modelling and solving a problem.
4.3 JAVA:
To create a software tool to produce exam timetable by constraint satisfaction problem, we are using choco constraint java library. By embedding choco java library with the java programming we can create exam timetabling tool.
Java was designed such that we can easily write the code, debug the code. Java uses automatic memory allocation and garbage collection.
Java is object-oriented because it includes creating objects, manipulating objects. It allows the objects to work together. So that the code written in java was reusable.
Java is platform independent. The code written in java can run on any computer system.
The compiler, interpreter and java developing environment are developed by keeping security in mind.
Because of these advantages, we selected java programming language to develop this application.
To develop a java application we need an Integrated Development Environment (IDE). Lots of Integrated Development Environments are there to develop a java application. In this project "EXAM TIMETABLING with CONSTRAINT SATISFACTION" we are using My Eclipse IDE.
4.4 MyEclipse IDE:
"MyEclipse incorporates today's most innovative open standard technologies to provide a development environment for J2EE WEB, XML, UML and databases."[4]
With MyEclipse you don't need to spend valuable time on debugging environment. It is easy to edit and debug the environment by using MyEclipse. It is an open source IDE to which we can add external jars.
CHAPTER 5
SYSTEM DESIGN
In process of developing the Exam timetabling tool for a university, Choco 2.1.0 version which is been used with Java Applets.
The different classes which are going to be used in the process of developing this application are ApplicationGUI.java, DataCal.java, TimeTable.java, ChocoSolver.java and Uitility.java.
ApplicationGUI.java: This class consists of code for displaying buttons like "Add Module To cohort", "Remove Module from cohort". All the graphical interface part is included in this class.
DataCal.java: This class consists of code for which we should get in the final screen. Mainly the code includes the logic works like selecting of alternate days of exams.
TimeTable.java: This class is the main class in the total application. It is first java class which is going to execute in the application. By executing this file, the first screen with list of buttons will be displayed if the application runs with out any error.
ChocoSolver.java: This class consists of code for constraint satisfaction.
This class solves all the constraints which we are going to use in this project.
Each class consists of different set of classes which interim consists of methods and fields to make the application be running.
CHAPTER 6
6.1 PROBLEMS IDENTIFIED AND THEIR PROPOSED SOLUTIONS
By this Exam timetabling application we are going to save a lot of time, as the manual process will take a lot of time to create an exam timetable for a university. We are going to create a user friendly application. In this project user can add any module to any cohort by using dropdown menus.
But we have some problems in this project.
Mostly we are not sure about the examination starting date. But in this application user has chance to select the starting date of examinations.
Some students with special need may be allowed extra time to finish their exam. As they are less number we are going to ignore them. For this kind of students we can add extra time manually.
Some cohorts may share same module. We are going to create timetable for the module which is shared by different cohorts on the same day. So that we can save time and can reduce the number of invigilators.
We should consider the students who have resit exams. A student should not have his resit exam and regular exam on the same day or on consecutive days. For this resit examinations should held with the next intake students or should create a special timetable for resit exams.
6.2 CONCLUSION:
I conclude that for this project I am investigated different ways to create an exam time tabling tool for a university.
I tried different types of tools to develop this application. I searched internet for an appropriate tool which makes this application user friendly.
This application offers different features to the users which are user friendly.
By the user guide which is attached to the application user can easily use this application.
CHAPTER 7
