Automated Timetable Generator

An application of Genetic Algorithm

Title: Automated Timetable Generator using Genetic Algorithm 
Source code link : https://github.com/ompranavagrawal/Automated-Timetable-Generator-using-Genetic-Algorithm

Abstract

Automatic Timetable Generator is a Java based application used to generate timetable automatically. Currently timetable is managed manually. It will help to manage all the periods automatically and also will be helpful for faculty to get timetable by using application. It will also manage timetable when any teacher is absent , late coming or early going. Maximum and minimum work load for a Faculty for a day, week and month will be specified for the efficient generation of timetable.

Introduction

Time table scheduling has been in human requirements since they thought of managing time effectively. It is widely used in schools, colleges and other fields of teaching and working like crash courses, couching centres, training programs etc . In early days, time table scheduling was done manually with a single person or some group involved in task of scheduling it with their hands, which take lot of effort and time.

While scheduling even the smallest constraints can take a lot of time and the case is even worse when the number of constraints or the amount of data to deal with increases. In such cases perfectly designed time table is reused for whole generation without any changes, proving to be dull in such situations. Other cases that can cause problem is when the number of employers/workers are weak, resulting in rescheduling of time table or they need to fill on empty seats urgently.

Institutions/Schools/Collages/Universities are the regular users of such time tables. They need to schedule their course to meet the need of current duration and facilities that are available to them. However, their schedule should meet the requirement of new course addition and newly enrolled students to fresh batches. This may result in rescheduling the entire time table once again for its entire batches and to be scheduled in shortest possible time before the batches course start. Another problem that occur when scheduling time table for exams. When multiple batches have exam on same day, they need to be schedules effectively taking into account all problems related to facilities that are available to conduct these exams simultaneously.

Benefits

Automated Timetable Generator, our software allows users to generate time table for newly occurring changes in less time, with less effort and with more efficiency. It will allow users to work on and view time tables in different platforms and view different information simultaneously.

Use Case Diagram

Work Breakdown Structure

Algorithm Implementation

TimeTable generation is an NP-Complete problem; specifically speaking NP-Hard. So it lacks a proper time bound for execution i.e. problems like these often can have many different outputs. So we assign cost to each output which gives the measure of deviation of the output from the desired one. So our aim is to get the output with minimum cost if there is one.

Genetic algorithm can give best results but the time needed for it to compute cannot be determined so we have developed an alternative approach which can be applied to solve most of the NP-Complete problems.
  • First determine the various constraints which the output must satisfy.
  • We then categorize them as soft and hard constraints.
  • Third step is to make a procedure which can generate an output for most of the possible inputs.
  • The final step is to reduce the cost.
The current working scenarios these can be explained as follows. The first two steps are explained earlier. The procedure mentioned in the third step here is the gene() function in the TimeTableGA class. What this function does is to assign properties to teacher, subject and position. So that if we arrange timetable according to this priority there is a greater probability to end up in the output which satisfies all the hard constraints.

First and foremost priority is that of teachers. Subject priority and position priority depends on teacher priority, also teacher is the most important resource in the time table. The priority of teacher increases if the number of periods he handled increases, also if the number of batches he is present increases and decreases if an alternative teacher is available. Subject priority is also similar to that of teacher priority. It must also increase with the continuous hours needed. So in the algorithm we have considered subject which have different consecutive periods need as different subjects. Position has priority if it correctly fits and the adjacent portions are not that of the same subject.

Finally we need to manually assign priority and optimize the table to reduce cost. The main logic of our algorithm resides in the TimetableGA class. The gene function in the class reads the various data needed for generation of timetable for current batches from the GUI creates the table in an String and copies it back .

Login Form

Data Entry Form

TimeTable Name Entry

Sample output

Testing

Testing is an important phase in software lifecycle. Testing improves reliablity and robustness of the application. The basic operations to be tested are
  • There should be at least one working day and one working hour.
  • Different inputs must be checked for its range. For example no of hours in morning or evening should be between 0-5, total number of periods for a course must be between 0-70, code for course must be 0-8 character long.
  • User should not be given permission to edit or modify subjects, teachers or batches without releasing its associations
  • Before generating table it should be checked if all subjects are assigned at least one teacher, no of periods available((morning hours +evening hours)*no of days) must be equal to no of periods assigned.
  • If any problem occurs during generation (due to constraints) it must be properly displayed.

Test Approach

The system is to be tested at various stages of the project development: Each user interface is tested individually for its function. Interfaces meant for data input are tested by entering data in the data tables through each interface. Similarly each data base operation is tested through interfaces.

All the user interfaces are joined in the desired sequence and their back end coding is tested for the desired result. Like previous window close as the next desired window opens and each button performs its desired task etc.

Every class in the java code is tested individually with the help of test cases. Whole of the algorithm is tested with sample run of data to generate an optimal time table for the provided database.

Test Planning

Most of the testing requires checking connectivity of the user interfaces, so a properly designed text file is required for testing. Design interfaces and connect each of them to the database and test them for proper output as is it is in the database.

Inter connect all the user interfaces in the desired sequence. Check if each of the buttons result in the desired result. Develop the java classes for data retrieval. Test each of them according to test cases. Develop java code for timetable generation. Test the coding with a small database by generating a time table.

Functional Test Criteria

The objective of these test is to ensure that each element of the application meets the functional requirement of the user.
  • Requirements Catalogue
  • Other functional documents produced during the course of the project i.e. resolution to issues/change requests/feedback.
  • Validation Testing - which is intensive testing of the new Front end fields and screens. Windows GUI Standards; valid, invalid and limit data input; screen look and appearance, and overall consistency with the rest of the application.
  • Functional testing - these are low-level tests which aim to test the individual processes and data flows.

Integartion Testing

This test proves that all areas of the system interface with each other correctly and that there are no gaps in the data flow. Final Integration Test proves that system works as integrated unit when all the fixes are complete.

User Acceptance Test

This test, which is planned and executed by the User Representative(s), ensures that the system operates in the manner expected, and any supporting material such as procedures, forms etc. are accurate and suitable for the purpose intended. It is high level testing, ensuring that there are no gaps in functionality.

System Test Criteria

Entrance Criteria:
  • All developed code must be unit tested. Unit and Link Testing must be completed and signed off by development team.
  • All human resources must be assigned and in place. • All test hardware and environments must be in place, and free for System test use.
Exit Criteia:
  • All High Priority errors from System Test must be fixed and tested

Test cases and Test results

Outlined below are the main test types that are performed for this release. All test entries on wrong input has been tested to verify code stablilty and correctness. The test cases presented here are based on criterias presented above to validate its test implementation. Each test case table list the detailed test case results for each interface and its user inputs that can be assinged by the user to check the correctness of its implematation.