1 of 71

The Problem

2 of 71

Complicated Problem!

Many Factors in real life:

Student’s preferences
Availability of resources
Lunch Break at different times for everyone
Elective Classes
Groups
Labs
Tutorials
Rooms allocation
Etc. etc.�

But TimeSched can handle these all!!!

3 of 71

Major�Features

Generates Randomised Time table on its own
Efficiency: Can generate and check 1000s of combinations in seconds
Students can be split into GROUPS and merge them very flexibly
Can handle Lectures, Labs, Tutorials
Can handle Open Elective classes
Has support for Lunch Break with different people having lunch at different times
Room allocation with proper resources!�(e.g. “C++ Tute can be taught only in room with projector”)
Generates 3 views - Student view, Faculty View and Room view
Flexible Tagging system and input in javascript so you can specify very complex conditions on input
Preferences for time can be set (eg. no late classes on friday)
Highly extensible and customisable.

4 of 71

Main details

Implemented in TypeScript using latest ES2020 features�
Input is given as a JavaScript Object to the TimeSched class

TypeScript automatically provides hints for the input data type
This allows us to use a Flexible Tagging system which can make use of JavaScript’s logical operators.�

You have to just call t.run() in the end�
It will go through thousands of combinations using a Hill Climbing optimisation algorithm and save the best result to disk.

5 of 71

OVERVIEW

Students

Rooms

Courses

Time Slots

Teachers

6 of 71

We have to match these resources to each other optimally.

7 of 71

Time table Scheduling Problem

Resource Matching Problem

Optimization Problem

8 of 71

Mathematical Optimization Problems

The code converts the problem of finding a timetable into an Optimization problem.
Then it uses a standard technique to solve the optimization problem.
Some standard techniques are:

Brute Force
Hill Climbing
Simulated annealing

Currently we are using Hill climbing but Simulated Annealing can also be implemented by only few code.

9 of 71

Demo and Screenshots

10 of 71

Inputs

First we import the TimeSched Class and declare the days and number of hours in each day,

Then we declare the different groups of students.

For example here,

Class of CSE is divided into 4 groups (G1 & G2 and Bio & Econ). ��Strength of each group is mentioned, which will help in room allocation.��Tags are declared for each of these.

11 of 71

Inputs

Then we declare the various teachers.

The tags are just for our own reference, they will help us later on while declaring the requirements.

12 of 71

Inputs

Similarly, Rooms are declared.

Here we declare three rooms, Lecture Hall F1, F2 and a Computer Lab Room.

Notice, LH-F2 has a working Projector!

So we add a tag ‘Proj’ to it.

Comp Lab is a Lab room so it has tag ‘Lab’.

We could also similarly declare Extra Resources which have an id and tags but for now I left it blank for the demo.

13 of 71

Courses

Now we come to the crucial part, the COURSES.

This part is different from the static inputs, because this is not JSON data, it is JavaScript!

Let us go through this.

First each course has a `name` which should be unique. (It could be `CSD-411` etc.)

We declare which resources we want through an arrow function which returns true if it wants that resource.

14 of 71

Requirements

Note: there is a difference between “studentsRequired” and the rest of the functions.��First we ask for ALL the students which contain the tag CSE. They have to attend this C++ lecture 4 times weekly.

For the other resources, ANY ONE resource matching the function will be assigned. So, any professor from CSE dept, any room in LH, and any time slot with duration 1.

This will allocate the resources and add the lecture to some appropriate place in the time table. Similarly we create a lecture for Math.

15 of 71

Selecting Students

CSE Lecture��studentsRequired: � (s) => s.tags.includes(‘CSE’)

CSE: G1

G2

ECE: G1

G2

Bio

Econ

16 of 71

Selecting Students

ECE Lecture��studentsRequired: � (s) => s.tags.includes(‘ECE’)

CSE: G1

G2

ECE: G1

G2

Bio

Econ

17 of 71

Selecting Students

Bio Nano Tech - Open Elective��studentsRequired: � (s) => s.tags.includes(‘Bio’)

CSE: G1

G2

ECE: G1

G2

Bio

Econ

18 of 71

Selecting Students

Economics - Open Elective��studentsRequired: � (s) => s.tags.includes(‘Econ’)

CSE: G1

G2

ECE: G1

G2

Bio

Econ

19 of 71

Selecting Students

CSE G1 Tutorial��studentsRequired: � (s) => s.tags.includes(‘CSE’)� && s.tags.includes(‘G1’)

CSE: G1

G2

ECE: G1

G2

Bio

Econ

20 of 71

Selecting Students

Some sort of Combined class??��studentsRequired: � (s) => s.tags.includes(‘CSE’)� || s.tags.includes(‘ECE’)

CSE: G1

G2

ECE: G1

G2

Bio

Econ

21 of 71

Selecting Students

One particular subgroup??��studentsRequired: � (s) => (s.id == “CSE_G1_Bio”)

CSE: G1

G2

ECE: G1

G2

Bio

Econ

22 of 71

Requirements

Wait, Why are we using JavaScript Arrow functions here??

Suppose we wanted that the C++ lecture can take place on any time slot but not after lunch. We could write the condition like this:

�So we are not limited in our language and we can write very powerful queries here. This, combined with the tagging system provides a lot of flexibility in specifying real world conditions which would be very hard to do with static data!

23 of 71

Requirements

Similarly we declare our requirements for Labs, Tutorials and Open Elective classes. We can combine arbitrary groups of students thanks to the tagging system! We can also require that the Tutorial should be in some room which has a projector.

24 of 71

Requirements

We can then also declare the Lunch Hours. Lunch hours [2,3] means that every student should have at least one empty slot in the 3rd or 4th hour. (This is 0-indexed).

We declare the relative penalty for no lunch, overlapping classes and some day ending too late (like a lab exceeding the limit of 6pm).

We also declare the time preference. Like, no one wants to wake up early on monday and everyone wants to leave quickly on friday.

After we declare our requirements we just run it for 10000 steps!

25 of 71

OUTPUT

Running the code is simple: ��$ npm install�$ npm start

The code starts iterating and it shows an evaluation which is a large negative number and it will try to maximise this evaluation (so it should converge to 0 hopefully).

At the end of 10000 iterations it saves the best value found so far to files on the disk.

It stores it in a JSON format with all details, along with three human readable views shown ahead. (Students view, Faculty View and Rooms View)

26 of 71

Student View (G1 Bio)

27 of 71

Student View (G1 Econ)

28 of 71

Student View (G2 Econ)

29 of 71

Student View (G2 Bio)

30 of 71

Rooms View (LH-F2)

31 of 71

Rooms View (Comp Lab)

32 of 71

Faculties View

33 of 71

It Worked!

The code did manage to solve most of the constraints we threw at it.

In particular the following things can be seen:

Courses assigned correctly and in sync in both groups.
Lunch break respected
Time preferences respected
Open Electives work
Room allocation works
No Overlaps were found
Code could calculate 10000 combinations within 10-20 seconds.

34 of 71

Extensibility

The code is easily extensible. To add a new feature, we have to simply add a new term to the penalty function.

For example, if we want that each subject should have only one lecture in a day, mostly, then we can simply add another condition which adds a penalty if the subject is taught twice.�
If we want a human-like time table then along with this we could add a bonus for consistency. That is, a bonus is added to the evaluation if two classes are at the same hour on two consecutive days.

If we want the faculty to have evenly distributed work, and not more than 3 consecutive classes, we can add a term for that too.

class TimeSched {

evaluation(t: TimeTable): number {�

let evaluation = 0;

� evaluation -= StudentsOverlap(t);

� evaluation -= FacultyOverlap(t);�� evaluation -= NoLunchBreak(t);

� evaluation -= RepeatedLectures(t);

� evaluation += ConsistencyBonus(t);

� return evaluation;

}�

}

35 of 71

Extensibility

Adding room distances is quite simple too, once you have the data.�
A lot of Performance improvements could be gained by coding this in C++ or Rust.�
We could replace Hill Climbing with Simulated Annealing which overcomes the problem of local maxima in hill climb when there is not sufficient space to move around it.

class TimeSched {

evaluation(t: TimeTable): number {�

let evaluation = 0;

� [...]�� evaluation -= RoomDistance(r1, r2);

� return evaluation;

}�

}

36 of 71

Another Example!

�With the consistency condition

And more complexity

37 of 71

Problem

CSE 2nd year

G1 G2

CSE 1st year

Econ and Bio

ECE 1st Year

Econ and Bio

Subjects:

CSE 1st year:

C++ (Dr. Priyanka)
C++ Lab (Dr. Priyanka)
Physics (Dr. S Chand)
Bio / Econ (Dr. Ghosh / Dr. Manoj)

CSE 2nd year:

OS (Dr. Priyanka)
Microprocessor (Dr. Amit)
Micro Lab (Dr. Amit)
Math (Dr. S Chand)

ECE:

Physics (Dr. S Chand)
Microprocessor (Dr. Amit)
Micro Lab (Dr. Amit)
Bio / Econ (Dr. Ghosh / Dr. Manoj)

38 of 71

Challenges

Challenges:

Common teachers

C++/OS between CSE 1 & CSE 2
Micro between CSE 2 and ECE
Physics and Math between all 3

Bio & Econ Open electives

Coordinate between ECE and CSE 1

C++ and Physics classes require projectors

Only two lecture halls and only one has projector

Limited time: 6 hours per day, out of which one should be lunch
CSE 2nd year has two groups and lab timing should be different for both

CSE 2nd year

G1 G2

CSE 1st year

Econ and Bio

ECE 1st Year

Econ and Bio

39 of 71

Let us see the output… ��After 200000 steps…

40 of 71

Students View

41 of 71

CSE - YEAR 1 - BIO

42 of 71

CSE - YEAR 1 - ECON

CSE - YEAR 1 - BIO

43 of 71

CSE - YEAR 2 - GROUP 1

CSE - YEAR 1 - BIO

44 of 71

CSE - YEAR 2 - GROUP 2

CSE - YEAR 1 - BIO

45 of 71

ECE - YEAR 1 - BIO

CSE - YEAR 1 - BIO

46 of 71

ECE - YEAR 1 - ECON

CSE - YEAR 1 - BIO

47 of 71

Faculty View

48 of 71

Dr. S. Chand

CSE - YEAR 1 - BIO

49 of 71

Dr. Priyanka

CSE - YEAR 1 - BIO

50 of 71

Dr. Amit

CSE - YEAR 1 - BIO

51 of 71

Dr. Manoj

CSE - YEAR 1 - BIO

52 of 71

Dr. Ghosh

CSE - YEAR 1 - BIO

53 of 71

Rooms View

54 of 71

Lecture Hall - 1

CSE - YEAR 1 - BIO

55 of 71

Lecture Hall - 2

CSE - YEAR 1 - BIO

56 of 71

Computer Lab

CSE - YEAR 1 - BIO

57 of 71

Comparison B/w Various Algorithms Implemented

We have tried to schedule time table by implementing various algorithms and tried to compare them.

58 of 71

Various Approaches

The first and most obvious approach to get "pretty good" solutions to NP-Hard problems is to devise greedy algorithms or Brute Force
The second approach is using optimization.
There are various optimization approaches such as Heuristics/Graph Coloring,Local Search Based techniques like Hill Climbing and Simulated Annealing or Population Based techniques like Genetic Algorithm, Ant Colony Optimization .etc

59 of 71

Improvements to Hill Climbing Algorithm

Taking multiple steps�at a time may help�in not getting stuck at�Local optima�
We implemented this�and compared results�with standard hill �climbing

60 of 71

Improvements to Hill Climbing Algorithm

61 of 71

Improvements to Hill Climbing Algorithm

62 of 71

Improvements to Hill Climbing Algorithm

63 of 71

Simulated Annealing Algorithm

64 of 71

Implementation of Simulated Annealing and ACO

65 of 71

66 of 71

Brute Force

67 of 71

Hill Climb

(Standard version�With increasing�Iterations)

68 of 71

Hill Climb

(Two Step version�With increasing�Iterations)

69 of 71

Hill Climb

(Three step version)

70 of 71

Simulated annealing�With various parameters

71 of 71

ACO