04-10-2016, 04:10 PM
UNIVERSITY TIMETABLING WITH CONSIDERATION OF USERS PSYCHOLOGICAL PREFERENCES AND OPTIMIZATION OF RESOURCE UTILIZATION BY APPROACHING AS AN ASSIGNMENT PROBLEM
1457718696-Miniprojectreportedited1.docx (Size: 86.46 KB / Downloads: 4)
Abstract:
Timetable scheduling process is one of the complex tasks which involve large number of constraints and handling of cross matches. As several heuristics are being practiced for this timetable allocation they don’t meet the expectation, comfort and other psychological needs of users that are in the user end. So we developed a heuristic which approach the time table scheduling as an assignment problem with more flexibility considering major human preferences.
Introduction:
Timetabling for classes in educational institutions which is the allocation of classes and respective teacher/professor for each batches of student for the given time slots is a problem commonly arises and which is also combinatorial. Timetabling as it is a NP-complete problem for which there is no optimization algorithm which can give an accurate one point best solution.
Hence heuristics is a best known solution for such a kind of problem which can give good enough solutions. So far several heuristics have been developed to solve such timetabling problem. But the problem with raw methods which consider only basic necessities such as number of time hours required, teacher/professor availability will give a solution which may contradict with the psychological needs of users (professors and students) while implementing in day to day uses.
So we aimed to develop a heuristic to solve this timetabling problem which will consider some psychological needs of the user like off-hours, time slot preferences, continuity, priority, non-repeat classes in a same day and more. The heuristics must be flexible enough to satisfy the needs demanded by the users, must optimize the utilization of available resources (human resource, time, and space capacity) and must give a valid timetable which can be fit practically.
Mathematical model for timetabling:
Initially a mathematical model for the timetabling has been modeled. Timetabling has been approached and modeled as an assignment problem where each time slots of the timetable has to be assigned with appropriate students batch, appropriate subject and the corresponding subject handler.
Assignment to a timeslot from the available alternatives is characterized by means of weights assigned to each alternative for every instance of allocation. Weight of each alternative comprises of contribution of user (students, professors) preferences (psychological needs or factors) which are derived from the input given by the users.
The assumptions made for modeling and the components of weight calculations are explained as follows.
Assumptions:
To approach the timetabling as an assignment problem the timeslots has been considered as discrete unit(periods) instead of continuous one. Other assumptions are as follows,
i. Each day in the timetable are divided into time slots.
ii. Number of timeslots in a day for a class timetable can be of any number and can be different between classes.
iii. Time period of any time slot in a class timetable will be same for corresponding slots in timetables of all other classes.
iv. Time period of a time slot in a timetable can be different from other slots of same table
v. Number of days must be same in all the timetables
vi. There were no subgroups in a class.
vii. One teacher/professor can take class for only one time at an instant of time.
From the assumptions on the time slot it will become clear that the approach is assignment rather than scheduling of class. For easy understanding and formulation, the model is provided in three stages. These stages are,
i. Assignment for one timeslot for timetable of one class.
ii. Assignment for one timeslot for timetable of all class.
iii. Assignment for all timeslot for timetable of all class.
Before going through these stages let us see the notations used in the mathematical model.
Limitations to solve the mathematical model:
It can be seen that the model derived above is a NP-Complete problem. It is very complex to find an algorithm to solve the above problem in polynomial time.
Moreover some other user preferences like off-hours, continuity, preference over some timeslots, priority over other user preferences and process for optimizing resources utilization((human resources, space capacity, time) cannot be devised into the model since it will become more complex.
Hence heuristic will provide more advantage in terms of flexibility, inclusion of more user preferences and time to arrive at the good enough solution.
Heuristics for timetabling:
The heuristic developed also approaches the timetabling as an assignment approach. Here the choosing between the alternatives is determined by means of weights assigned to each alternative same as in the mathematical model but with few more components added to the weight to include some other user preferences like off-hours, continuity, preference over some timeslots, priority over other user preferences.
The heuristics consists of two blocks of steps. They are,
• First block of steps is for finding best set of subjects for the timeslots.
• Second blocks of steps is for finding best fit of room space for the corresponding classes for which the selected subjects from the first blocks will be instructed.
In each blocks optimizing of resources will be done subsequently while finding best fits.
Each block consists of two stages. These two stages are as follow,
Primary stage- In this stage initial rough allocation will be done considering user preferences and needs to be satisfied to in the timetable where weights of the subject will be the measureto make decision.
Secondary stage- In this stage reassignment will be done in the assignments from the primary stage for optimizing the resource (space capacity,time, human resource) utilization will be done.
Now we can see the assumptions and steps in our heuristics.
Assumptions:
Like the assumptions made for mathematical modelling, certain assumptions has been made for solving the timetabling problem in assignment approach. They are as follows,
i. Each days in the timetable are divided into time slots.
ii. Number of timeslots in a day for a class timetable can be of any number and can be different between classes.
iii. Time period of any time slot in a class timetable will be same for corresponding slots in timetables of all other classes.
iv. Time period of a time slot in a timetable can be different from other slots of same table
v. Slots of intervals like lunch if added in timetable of one class has to be included in all other timetable also and has to be marked as blocked
vi. Number of days must be same in all the timetables (Time slots in the unnecessary days(if any) of a day has to be marked as blocked)
vii. Similarly unnecessary timeslot of a day in a timetable has to be marked as blocked.
viii. There were no subgroups in a class.
ix. One teacher/professor can take class for only one time at an instant of time.
Example for the assumptions are shown below. On seeing the timetables we can find that,
• Timetable of class 2 shows the assumption 6.
• Timetable of class 3 and class 4 shows the assumption 7.
• Timetable of class 3 and class 4 shows the assumption 2.
• All the timetables have equal number of days (assumption 6).
• Corresponding timeslots in every timetables have same time period (assumption 3).
• Interval slots (i.e. lunch) is included in all timetables (assumption 5).
• Third time slot of class 1 have different time period then other slots (assumption 4)and also corresponding timeslot in other timetables have the same timeperiod(assumption 3).
Conclusion:
We have developed a heuristic for timetabling which considers basic preferences of users while allocation and also the heuristic have been developed with rules which increase utilization of resources. This results in generation of timetable which increase compatibility with the environment where it will be implemented.Several others aspects which play major role in the environment where the timetable forms a part like facility location which will be utilized by the users based on the given timetable, batching of different user groups for a schedule and more can be included in further development of the above heuristic. Timetable formed from such heuristic will be an intelligent schedule which plan activities and utilize resources and effective.