The process of time-table construction can prove to be a hectic task considering the number of cohorts [courses] and the modules [subjects] offered by a specific university. This is mainly because, there could be a deadlock in allotment of the schedule considering all the constraints to be satisfied . This requires logical thinking which definitely consumes a large amount of time. Moreover, identification of the inconsistencies and their respective solutions can prove to be disastrous.
Initially , the task of time – table scheduling was done manually . This proved to be troublesome , error-prone and time consuming . To overcome these problems , automated exam time-table generation has come to light. With a wider range of choices available to the students in the selection of modules [ subjects ] and cohorts [ courses] of their choice , the flexibility of the University improves but at the same time , the task of time-table creation becomes merely complicated . However , a software which can consider all the constraints and cross faculty modules [latter includes the modules taken by students from various faculties]as well , is of immense help. Thus , the scientific society has given considerable attention to automated time-table generation from the last four decades . One of the most primitive ones used the concepts of one or more of the following operational methodologies
network flow techniques
reduction to graph coloring
integer programming
direct heuristics and more
The latest technology uses advanced techniques like expert systems which work on the concept of artificial intelligence, logic programming which uses languages like Prolog, constraint logic programming and generic evolutionary algorithms . However , there is no universally accepted language for time-table creation. Several attempts have been made to formulate one but these are left incomplete.
In this software , the constraint satisfaction is 99% . Moreover , the interface developed is use friendly where in the user doesn’t have to enter the names of the cohorts and modules which he wishes to opt for as he can just select the same from the drop down lists .
WHAT IS CONSTRAINT SATISFACTION?
Constraint satisfaction was first introduced in artificial intelligence . This is a logical problem solving language merged with a programming language which is used to solve a given problem with a specific set of constraints. This deals with the assignment of certain values to the variables while meeting certain conditions. It is represented as a set of variables Xi and a set of constraints Ci where each constraint specifies a subset of variables and an allowable combination of these.
In this project some of the main constraints which are to be considered are as below:
Students belonging to different cohorts but studying a common module must have the exam on the same day.
No two modules of the same cohorts can have their respective exams on the same day
One of the soft constraints is that no two exams of the same cohort must be on the same day
Thus, these are satisfied before the software is deployed . The techniques used in constraint satisfaction are purely dependent on the constraints. Constraints specific to a finite domain are solved using search strategies in the form of backtracking or local search. Constraint propagation is yet another technique which is used but however is sometimes incomplete. That is it either solves the problem or proves and declares it unsatisfiable . These methods are combined with the search strategies to simplify the process.
There are many constraint programming libraries which can be included in this project. Since Java is the platform we develop the project on, Choco is an appropriate library which can be easily used with Java programming . it is an event based propagating system with backtrack structures. More on Choco is discussed in the later sections on the report.
BRUTE FORCE TECHNIQUE:
Brute force technique is a process of finding the result by taking all the possible inputs i. e., a trial and error process. If a taken Input yields the correct result then it is treated as the correct input. If not then it goes for the next input until we get the correct result.
We can consider knapsack problem as an example of a brute force technique. Knapsack problem generally means a bag which should be filled with weights that should yield maximum profit. The most implicit constraint of knapsack problem is to maximize profit with minimum weight.
Let us say there a four types of materials as follows gold , silver , platinum and bronze with profit values of 1000, 10, 2000 and 5 and weights of 2, 3, 4, 5 . Thief want more profit with his minimum capacity bag let us say it can fit 5. So he applies the brute force technique to get maximum profit. First he fills the bag with gold which weights 2 and then goes for silver which weights 3 here the bag is full and yielding the profit of 1000+10= 1010.
Now he tries of another combination i. e., he selects platinum which weights 4 and now the rest of the bag is only one so he can select the ? part of gold which weights 1 thus the bag is filled with yielding 2000+500= 2500 . In this manner different combinations are tried until the max profit is yielded.
CHAPTER 2Aims and Objectives
The manual process of generating exam timetable by taking all constraints into consideration is very much time taking and difficult process. So the main aim of this project is to build a software tool to create exam timetables for a university or a school and the application should be user friendly and should satisfy all the constraints.
The brief explanation of this is as follows:
First analyze the manual process in developing exam time table that is following in schools and universities.
This analysis helps us in developing the software tool.
After analyzing the manual process we should make a list of all possible constraints which should be satisfied by the developed system.
We should identify all the constraints that should be satisfied by our developed system and we should analyze them which is helpful in developing the software product.
To gain an understanding of constraint satisfaction tool like choco which we are using in the development process.
The developed product should be user friendly, so that user can use the system easily.
In AUTOMATED EXAM TIME TABLE product the user should input the cohort name and module name.
Instead of typing the entire cohort and module name we should put a dropdown list where user selects from it. By this we can eliminate the incorrect typing.
The developed product should satisfy constraints like two exams of the same year of both semesters should not be on the same day.
Every student should get their exams on alternate days only.
All such type of major constraints should be satisfied by our product.
MOTIVATION:
Most of the people are interested in playing chess. By playing chess we can improve our concentration power. We have an idea of creating code for playing chess. As chess is played by two players one player is automated and another player plays manually. Here constraint satisfaction is used because there are certain conditions like elephant should have only straight moves, soldier should have one step straight move etc., we have to design our code by satisfying these conditions.
Our program is used by the player in the absence of his partner. This player makes use of graphical user interface to opt his plots against other player which makes use of our code. So here artificial intelligence is used. This idea motivated us for designing automated examination time tabling software.
FEATURES:
Exams are scheduled such that no two exams are overlapped for the same student.
Students are informed in case of any changes in the examination schedule like postponement, or preponement etc.
User can save data so that he can view the application if he reopens it again.
Students are allotted examination halls in a proper way so that a single student is not allotted in two different rooms.
Proper allotment of staff in examination halls.
Student can post his problems regarding exams.
User can add modules to this software if they are relevant to this software.
KEY TECHNIQUES
JAVA PROGRAMMING
JAVA is the language which has many features like multithreading, platform dependent, simple, robust, object oriented etc. Java is portable and performance levels of it are too high.
Java concepts are very simple and understandable.
Exceptions are also perfectly managed by Java.
Database connectivity, GUI, IO packages is the main concepts due to which we go for java programming.
CONSTRAINT SATISFACTION PROGRAMMING USING CHOCO
CHOCO is a java library which is mainly used for constraint satisfaction.
CHOCO is based on events which have the capability of backtracking. It can be used for many purposes like teaching, researching etc. So by using this constraint satisfaction programming we can develop the exam time table perfectly.
ORACLE DATABASE FOR DATA STORAGE AND RETRIEVAL
Database is a collection of entities. Data is a collection of similar raw information. Data is represented with the help of views or tables. View is not a physical entity. It is the representation for shadow of tables.
Oracle database is mainly used for data storage and retrieval. That is data is stored in a place and in future if we want that data we can easily retrieve it.
For developing the exam timetable in a university the above three key techniques are very very important and by using these techniques only the development processing of timetable can be done perfectly.
SYSTEM REQUIREMENTS
There are two types of system requirements software and hardware.
SOFTWARE REQUIREMENTS
Based on the operating system many things may depend. So selection of operating system plays very important role. WINDOWS XP operating system is the most appropriate operating system for software requirements of developing exam timetable.
Oracle 10g relational database management system is also one of the software requirements.
For developing the JAVA code My Eclipse Tool is the most suitable software requirement.
For constraint satisfaction programming the preferred version is CHOCO 2. 1. 0.
These are the minimum and most important software requirements for developing exam time table.
HARDWARE REQUIREMENTS
The processor required is Pentium 111 processor with 800MHz.
Oracle database 10g and Java code developing tool must be on run mode at the same time so 1GB RAM is required.
20GB HDD also required as hardware requirement.
These are the minimum and most important hardware requirements for developing exam time table.
CHAPTER 3SYSTEM ANALYSISExisting System:
The timetable management of a university was initially done normally by using some primitive methods and algorithms. The planning is made by a group of people and the timetable is fixed after certain negotiations. The university needs to set the timetable for each and every student separately and then finalize the whole timetable. The Timetable that is prepared by the Examination department of that institution needs to be sent in atleast 45 days advance to all the departments of the university and concerned affiliated colleges also. There are some issues regarding the timetable preparation. They are
The students belonging to different departments will have the subjects related to their course. The subjects may be in common for certain branches. So the timetable designer needs to have a proper idea regarding the date and time of the examinations making sure that the same subject to different departments is conducted on the same day and at the same time. This reduces the extra effort for preparing different sets of question papers and ensuring the same complexity of the paper.
A subject may be completed in advance by certain departments and there might be certain students who had failed that certain subject. The students who have failed in the regular examinations are given a chance for writing the supplementary examinations in the next semester. There is a chance of anomaly that the regular examination of the current semester and the supplementary examination for the previous semester may fall on the same day and same time. So the timetable adjustment must be flexible in such a way that no student misses any of the examinations.
The regular student needs to have at least a day gap in between the examinations so that he can get ample amount of time for preparation for the next examination.
The availability of the invigilators also needs to be checked before scheduling a particular examination. The staff members who are not assigned any class work at that time are to be taken and the schedule for a particular staff is to be prepared.
The subject that is opted by maximum number of students is to be held as the first examination itself. The reason behind this is that, if the subject that is opted by maximum number of students is conducted at the last then there would be a problem in validating the answer scripts.
So overcoming all the above mentioned issues is a hectic task. The timetable designer needs to have an idea regarding all those issues. The time taken by an individual to overcome all the above issues may take a few months of time.
Proposed System:
The proposed system of timetable management is rather a key solution for all the above mentioned issues. It gains its importance in eliminating the potential risks that are involved in the process.
We can give certain number of constraints as the input and the schedule is prepared considering the constraints.
The software is flexible enough for the users to enter the starting and the ending date of the examinations, the names of the students and their respective departments are present in the database and the details are retrieved accordingly. The result of the examination is automatically stored in the database for the preparation of the next semester’s timetable.
The proposed system is considerably quicker and more efficient.
CHAPTER 4SOFTWARE TOOLS DISCUSSION1. CONSTRAINT SATISFACTION:
We have a lot of constraints which need to be imposed and satisfied in our project. Basically “ CONSTRAINT SATISFACTION” can be defined as the process of finding a solution to a set of constraints that impose conditions for which the variables must satisfy.
In general terms, a solution is the set of variables that satisfies all the constraints. This can also be defined as the outcome of constraint satisfaction
2. CONSTRAINT SATISFACTION PROBLEM(CSP):
A CONSTRAINT SATISFACTION PROBLEM(CSP) is defined by a set of variables each having a specific domain and also a set of constraints each involving a set of variables. These constraints restrict the values that the variables can take. A CSP performs these two tasks simultaneously. Now coming to the solution to CSP, it is just an assignment that maps every defined variable to a value.
There may be cases where you may want to find just one solution, all possible solutions or an optimal solution based on the given objective function in terms of variables.
A general constraint problem consists of the following:
A set of variables A={a1, a2, aˆ¦aˆ¦. an}
For each variable ai, a finite domain set Di of its possible values. D={D(a1), D(a2), aˆ¦aˆ¦aˆ¦. D(an)}.
A set of constraints to restrict the values that the variables can take. C={C1, C2, aˆ¦aˆ¦aˆ¦aˆ¦aˆ¦Cj}.
3. CONSTRAINTS SOLVER:
Now we need a constraint satisfaction tool to solve the considered constraints. This tool can be combined with any other programming languages like C, C++, JAVA etc. This tool is nothing but the constraint satisfaction libraries . As we move on with the java programming in our project, different constraint satisfaction java libraries available are given below:
Choco
JaCop
Qstudio
Avaya
Aptana
JCL
Koalog
From above mentioned java libraries, we use choco in this project. Choco is based on an event based propagation mechanism with an additional feature of backtracking structures which adds to its supremacy. This gives clear difference between modeling and solving a problem.
4. CHOCO:
Choco is an open source software implemented in java program that is widely used for constraint programming and constraint satisfaction.
General Features:
Choco provides problem modeler that handles a variety of variable types that are
integer variables
real variables that holds an interval of floats.
expressions using variables with the many operators like +, -, /, * and etc.
Choco’s modeler supports 70 constraints some of them are listed below
Arithmetical constraints (integers or real): equal, not equal, greater or equal, less or equal.
Refined constraints i . e Boolean operations between constrains.
It will verify the relation for a set of variables by defining the sets of tuples in the table constraints.
Constraint Programming Solver:
Constraint programming solver provides
The different types of various domains implementations will be done (enumerated, bounded, integer variables).
For constraint propagation several algorithms were implemented (parameterized cumulative, full and bound all different, state-of-the-art AC algorithms for table constraints)
Choco’s Design:
Choco’s design provides clear separation between modeling and solving.
In the modeling the problem will be expressed and variables and relations are defined. The verification for variable constraints for their potential implementation is done. The API is provided that facilitates how to state a problem as user friendly.
In the solving phase, the problem solving is done by Constraint Programming and related information is provided. It handles specific memory management for variables and tree-based search.
5. JAVA:
We use choco constraint java library to build the tool. By embedding choco java library with the java programming we create the required exam timetabling tool.
Java provides us many features which augments security and has many advantages:
Java is designed in such a way that you can easily write the code and debug the code. Java uses the concepts of automatic memory allocation and garbage collection.
As java is an object-oriented programming language, it allows objects to work together. The code written in java is reusable.
Java is platform independent.
This is developed by keeping security in mind. Java augments today’s web with security and reliability.
Because of these features we use java programming in our project. But we need an INTEGRATED DEVELOPMENT ENVIRONMENT(IDE) to develop a java application. Lots of IDE’s are available. In this project “ EXAM TIMETABLING with CONSTRAINT SATISFACTIO” we use MyEclipse IDE.
6. MyEclipse IDE:
MyEclipse is a commercially available JAVA EE and AJAX IDE. This is created and maintained by the company GENUITEC. This is built on the eclipse platform. This integrates proprietary and open solutions into the development environment. MyEclipse incorporates open standard technologies to provide a development environment for J2EE, XML, UML and databases. This is an open source IDE to which you can add external jars.
MyEclipse allows you to save the valuable time on debugging environment. By using MyEclipse, it is easy to edit and debug the environment.
MyEclipse comes with two versions: a professional and a standard edition. The standard edition adds various tools and a number of other features to the basic Eclipse Java Developer version.
CHAPTER 5SYSTEM DESIGN
The development process of the Automated Exam Timetabling tool for a University, we use Choco 2. 1. 0 version which is implemented using Java Programming.
The different tasks which are going to be implemented in the process of developing this application are
Designing Graphical User Interface(GUI).
Data Calculations.
Timetable.
Choco tool for Constraint Satisfaction.
Step1: Designing Graphical User Interface (GUI)
This process includes only Graphical User Interface part, that consists buttons, Tables, Dropdown lists and etc. These controls are arranged in the proper order to display them. Look and feel will be implemented in this process.
Step 2: Data Calculations
Data Calculations part consists of code which results the final output for the Schedule of Exam Timetable. Here we implement the code with logic that works like selection of exams to be held in alternative days.
Here we consider all exams of particular course and prepares a logic for Exam Timetable that includes Supplementary and Regular Exams.
Step 3: Timetable
Timetable process involves in the creation of a schedule that sets the examinations are allocated into venues with limited capacities within an examination period.
This includes the following methods.
We cannot schedule a session where one student cannot taken two examinations in the same session.
The venue’s capacity should not exceed from the total number of candidates writing the exam in a schedule.
Step 4: ChocoSolver
ChocoSolver is a java library for constraint programming and constraint satisfaction.
Choco will define all the variables of time tabling problem that includes the
Constraint Definitions
Candidate Information
Venue Information
Examination information
Exam Session particulars.
User has to enter constraints and changes to the exams related to the particular exam or venue.
Defining the Constraints
This program will allow the users to define all necessary constraints according to the exams.
The different duration should be separated for all examinations .
The examination time and venue of a particular batch should be held in particular date.
Venue Partitioning
This process considers the number of faculties and venues. Invigilators are allocated to particular venue for the examinations.
User interface is provided for the assignment and manipulation of venue partitions to the faculties. In venue partitioning the following points are considered in the Choco Solver
The number of students in a venue should not exceed more than the capacity.
The sufficient invigilators should be allocated for the each examination hall.
The attendance sheet should be provided to the invigilators to confirm the candidate is attended or not.
PROBLEMS IDENTIFIED AND THEIR PROPOSED SOLUTIONS:
Scheduling an exam time table is very difficult and time taking task because there are many constraints that should be satisfied for ex: at least one day gap should be there in between two exams so that student gets time to revise, there should not be any other exam on the same day which collides with the present exam, room allocation, staff allocation, invigilator allocation aˆ¦. Etc.
All this problems are solved in this project, this project saves a lot of time, this helps to schedule exam time table in more user friendly manner.
Proposed System:
In this project user can add any module to any cohort by using dropdown menus.
Mostly we are not sure about the starting date of exams, but in this application user have chance to select the starting date of examinations.
Sometimes same module may be shared by some cohorts. In this case we are going to create new time table for the module shared by different cohorts on the same day. So that time can be saved and number of invigilators can be reduced.
Some student may have supplementary exams. This supplementary exam and regular exam should not be on the same day or on the consecutive days. Separate schedule is created for these supplementary exams or those should be held with next intake students.
This application allows user to add modules to a cohort by using drop down menus. The user can also make changes to the selected modules list.
As per the date, schedule and cohort selected by user examination time table is created.
As the user is allowed to choose options from drop down list provided, problems that occur due to typing mistakes can be decreased.
Application development and deployment:
The steps involved in the development and deployment of application involve
Formulating the data interpretation scheme that is sufficient to handle all the requirements of the problem
converting all data available to data interpretation scheme
Next step is developing the scheduling algorithm that is used to schedule the exams.
The application should support the numerous last minute changes during its development and deployment easily.
Application Uses:
The following are the benefits of Automated Exam Timetabling
The initial implementation of program requires a lot of time for data entry and constraint specification. We can reuse the database of previous exams for next exams.
Assuming that the constraints are specified correctly, the application should produce the schedule that is conflict free.
We can schedule the exam timetable in a short span of time.
We can make last minute changes in a short span of time.
Shortening the exam period can make the expenses spend on conducting the exams (such as buildings, staff, etc.,) come down.
The application benefits from its three tier architecture design.
Conclusion:
Automated Exam Timetabling software is used to schedule the university exam time table. This is reduces time and complexity involved in scheduling the exam time table manually. This document explains about the space and time complexity involved in scheduling the exam.
The application developed is user friendly and it is used to give a graphical look and feel to the user for accessing and entering the information.
Automated Exam Timetabling provides all the features that are required for scheduling the exam time table. Implementation of this software at different universities reduces the cost in terms of money and time.
Future Uses:
Automated Exam timetabling can be extended to schedule the university class time table and school time table
School Timetabling:
This application is used for scheduling the timetables for weekly classes at higher schools.
University Timetabling:
This application is used for scheduling the lectures of students of different modules in a university such that they prevent students and lecturers from double booking.
