19-09-2012, 01:14 PM
PREFERENCES OF TEACHERS AND STUDENTS FOR AUTO GENERATION OF SENSITIVE TIMETABLE: A CASE STUDY
1PREFERENCES OF TEACHERS.pdf (Size: 48.77 KB / Downloads: 49)
Abstract
A large amount of tools are available for generating timetable based on the constraints provided by user. The
tools generally consider those constraints which are insensate and which are unavoidable. They emphasize
mainly on the specifications of classrooms, teachers, subjects but are not able to fit in constraints related to the
human factors like fondness, placate and weakness of the major target stake holders namely teachers and
students. To make system which works like humans, it might be highly beneficial to frame rules stating the
personal preferences of the main stakeholders and subsequently design the timetable incorporating these rules as
well.
This paper presents a survey done to find the preferences of teachers and later concludes with the rules
mined using classification method. Later these rules can be utilized intelligently for an insightful timetable
generation.
Introduction
The timetabling problem comes up every year in educational institutions, which has been solved by leveraging
human resource for a long time. The problem is a special version of the optimization problems; it is
computationally NP-hard [D.Schindl(2000)] . As a result, only the major inevitable conditions can be
considered during the manual arrangement process. However the manual process takes into account soft
constraints whereas automated system might not consider them. This is a major shortcoming of automated
systems, wherein they don’t give due importance to human feelings.
If we want to have a system which works like humans, it would be necessary to make it aware of the soft
constraints of humans. Hence we propose a method to add this aspect in the timetable generation to achieve an
artificial intelligent computer system more close to human. We propose to use a mechanism to mine rules
which can later be incorporated in the automated system to draw its attention to the soft constraints.
Time Table Constraints
1) Hard constraints: - Hard constraints have to be taken into consideration very strictly, because the timetables
that violate just one of these are unusable. The finite “resources” belong to this group. The constraint that one
person cannot be in two places at once or that there is a maximum number of people that can be accommodated
in a particular room.[Burke and Newall(2002)] Many systems designed to treat mainly the hard constraints have
been proposed, some noteworthy of them are constraint based reasoning to timetable generation [Banks(1998)] ,
hybrid approach based on heuristic [Abdullah & Hamden (2008)],based on ordering heuristics [Rehman et al.]
,based on genetic algorithms [Colorni et al(1990)] etc.
2) Soft Constraints: - The timetable that violates these constraints is still usable, but it is not convenient for
either students or teachers, and it also makes more difficult to understand the lessons. The constraints under this
category are teacher’s soft availability, capability of teacher to handle two or more consecutive lessons, to name
a few.
In real-world situations it is, usually impossible to satisfy all soft constraints[Burke and Petrovic (2002)].As a
result the tools used for automated timetable generation concentrate on hard constraints ignoring the soft
constraints . But when we are interested in designing a sensitive or intelligent time table generator system, it
gets very important to consider these soft constraints too while designing the time table. And this in turn would
necessitate having some rules to indicate the soft constraints suggestion.
Rule-based timetable generation has been suggested by [Shaikh & Al-Bastaki(2004)] and [Yuri Kochetov et al
(2008)] have developed a mathematical model for timetabling problem and have proposed local search
heuristics to solve the problem. A wide variety of other approaches to solve timetabling problems have been
investigated in [Burke & Petrovic(2002)]
Materials and methods
Classification Trees
Classification trees are used to predict membership of cases or objects in the classes of a categorical dependent
variable from their measurements on one or more predictor variables. The goal of classification trees is to
predict or explain responses on a categorical dependent variable [12]. Classification trees readily lend
themselves to being displayed graphically, helping to make them easier to interpret than they would be if only a
strict numerical interpretation were possible. Other characteristics of decision tree are their hierarchical nature
and flexibility.
CART (Classification & Regression trees) is a stepwise, nonparametric procedure that uses exhaustive
computerized searches and sorting techniques to identify useful tree-structures for classification of data from
several groups. It provides a set of rules that can be applied to a new (unclassified) dataset to predict which
records will have a given outcome. Trees are formed by a collection of rules based on values of certain
variables in the modeling data set.
Rules are selected based on how well splits based on variables’ values can differentiate observations based on
the dependent variable Once a rule is selected and splits a node into two, the same logic is applied to each
“child” node (i.e. it is a recursive procedure). Splitting stops when CART detects no further gain can be made,
or some pre-set stopping rules are met. Each branch of the tree ends in a terminal node. Each observation falls
into one and exactly one terminal node. Each terminal node is uniquely defined by a set of rules.
Experimental Setup
CART analysis was performed with trial version of commercial statistics software, namely SPSS statistics 17.0
[Online available at:www.spss.com]. The Decision Tree procedure in this tool creates a tree-based
classification model. It classifies cases into groups or predicts values of a dependent (target) variable based on
values of independent (predictor) variables. The procedure provides validation tools for exploratory and
confirmatory classification analysis. It provides the CART growing method wherein the data is split into
segments that are as homogeneous as possible with respect to the dependent variable. A terminal node in
which all cases have the same value for the dependent variable is a homogeneous, "pure" node.
Conclusion & Future Work
The rules mined can be incorporated in a system for auto generation of the timetable schedule for the particular
university where the survey was conducted. Similar procedure can be followed in any institute to get such
interesting rules mined and can be later fed to timetable generator software.
Consequently, this method would prove to be beneficial to achieve a sensitive, comfortable, and friendly
timetable for the teachers as well as students of an institute.
In future it would be interesting to collect and analyze the feedback of the intelligent and sensitive timetable
generated.Also it would help to understand the impact of an artificial intelligent timetable on the overall
productivity and working capabilities of the stake holders of this asset.
In current paper, only university timetabling problem is addressed,however it would be expanded to other
timetabling problems such as employee timetabling,timetabling of sports fixture etc.