Abstract: This paper explains the educational timetabling problem, a type of scheduling problem that is considered as one of the most challenging problem in optimization and operational research. The university examination timetabling problem (UETP), which involves assigning a set number of exams into a set number of timeslots whilst fulfilling all required conditions, has been widely investigated. The limitation of available timeslots and resources with the increasing number of examinations are the main reasons in the difficulty of solving this problem. Dynamical change in the examination scheduling system adds up the complication particularly in coping up with the demand and new requirements by the communities. Our objective is to investigate these demands and requirements with subjects taken from Universiti Malaysia Terengganu (UMT), through questionnaires. Integer linear programming model which reflects the preferences obtained to produce an effective examination timetabling was formed.
Abstract: Course timetabling problems occur every semester in a university which includes the allocation of resources (subjects, lecturers and students) to a number of fixed rooms and timeslots. The assignment is carried out in a way such that there are no conflicts within rooms, students and lecturers, as well as fulfilling a range of constraints. The constraints consist of rules and policies set up by the universities as well as lecturers’ and students’ preferences of courses to be allocated in specific timeslots. This paper specifically focuses on the preferences of the course timetabling problem in one of the public universities in Malaysia. The demands will be considered into our existing mathematical model to make it more generalized and can be used widely. We have distributed questionnaires to a number of lecturers and students of the university to investigate their demands and preferences for their desired course timetable. We classify the preferences thus converting them to construct one mathematical model that can produce such timetable.
Abstract: The agenda of showing the scheduled time for
performing certain tasks is known as timetabling. It is widely used in
many departments such as transportation, education, and production.
Some difficulties arise to ensure all tasks happen in the time and
place allocated. Therefore, many researchers invented various
programming models to solve the scheduling problems from several
fields. However, the studies in developing the general integer
programming model for many timetabling problems are still
questionable. Meanwhile, this thesis describes about creating a
general model which solves different types of timetabling problems
by considering the basic constraints. Initially, the common basic
constraints from five different fields are selected and analyzed. A
general basic integer programming model was created and then
verified by using the medium set of data obtained randomly which is
much similar to realistic data. The mathematical software, AIMMS
with CPLEX as a solver has been used to solve the model. The model
obtained is significant in solving many timetabling problems easily
since it is modifiable to all types of scheduling problems which have
same basic constraints.
Abstract: In this article, we deal with a variant of the classical
course timetabling problem that has a practical application in many
areas of education. In particular, in this paper we are interested in
high schools remedial courses. The purpose of such courses is to
provide under-prepared students with the skills necessary to succeed
in their studies. In particular, a student might be under prepared in
an entire course, or only in a part of it. The limited availability
of funds, as well as the limited amount of time and teachers at
disposal, often requires schools to choose which courses and/or which
teaching units to activate. Thus, schools need to model the training
offer and the related timetabling, with the goal of ensuring the
highest possible teaching quality, by meeting the above-mentioned
financial, time and resources constraints. Moreover, there are some
prerequisites between the teaching units that must be satisfied. We
first present a Mixed-Integer Programming (MIP) model to solve
this problem to optimality. However, the presence of many peculiar
constraints contributes inevitably in increasing the complexity of
the mathematical model. Thus, solving it through a general-purpose
solver may be performed for small instances only, while solving
real-life-sized instances of such model requires specific techniques
or heuristic approaches. For this purpose, we also propose a heuristic
approach, in which we make use of a fast constructive procedure
to obtain a feasible solution. To assess our exact and heuristic
approaches we perform extensive computational results on both
real-life instances (obtained from a high school in Lecce, Italy) and
randomly generated instances. Our tests show that the MIP model is
never solved to optimality, with an average optimality gap of 57%.
On the other hand, the heuristic algorithm is much faster (in about the
50% of the considered instances it converges in approximately half of
the time limit) and in many cases allows achieving an improvement
on the objective function value obtained by the MIP model. Such an
improvement ranges between 18% and 66%.
Abstract: This paper presents a hybrid algorithm for solving a timetabling problem, which is commonly encountered in many universities. The problem combines both teacher assignment and course scheduling problems simultaneously, and is presented as a mathematical programming model. However, this problem becomes intractable and it is unlikely that a proven optimal solution can be obtained by an integer programming approach, especially for large problem instances. A hybrid algorithm that combines an integer programming approach, a greedy heuristic and a modified simulated annealing algorithm collaboratively is proposed to solve the problem. Several randomly generated data sets of sizes comparable to that of an institution in Indonesia are solved using the proposed algorithm. Computational results indicate that the algorithm can overcome difficulties of large problem sizes encountered in previous related works.
Abstract: Timetabling problems are often hard and timeconsuming
to solve. Most of the methods of solving them concern
only one problem instance or class. This paper describes a universal
method for solving large, highly constrained timetabling problems
from different domains. The solution is based on evolutionary
algorithm-s framework and operates on two levels – first-level
evolutionary algorithm tries to find a solution basing on given set of
operating parameters, second-level algorithm is used to establish
those parameters. Tabu search is employed to speed up the solution
finding process on first level. The method has been used to solve
three different timetabling problems with promising results.
Abstract: This paper explores university course timetabling
problem. There are several characteristics that make scheduling and
timetabling problems particularly difficult to solve: they have huge
search spaces, they are often highly constrained, they require
sophisticated solution representation schemes, and they usually
require very time-consuming fitness evaluation routines. Thus
standard evolutionary algorithms lack of efficiency to deal with
them. In this paper we have proposed a memetic algorithm that
incorporates the problem specific knowledge such that most of
chromosomes generated are decoded into feasible solutions.
Generating vast amount of feasible chromosomes makes the progress
of search process possible in a time efficient manner. Experimental
results exhibit the advantages of the developed Hybrid Genetic
Algorithm than the standard Genetic Algorithm.
Abstract: The Resource-Constrained Project Scheduling
Problem (RCPSP) is concerned with single-item or small batch
production where limited resources have to be allocated to dependent
activities over time. Over the past few decades, a lot of work has
been made with the use of optimal solution procedures for this basic
problem type and its extensions. Brucker and Knust[1] discuss, how
timetabling problems can be modeled as a RCPSP. Authors discuss
high school timetabling and university course timetabling problem as
an example. We have formulated two mathematical formulations of
course timetabling problem in a new way which are the prototype of
single-mode RCPSP. Our focus is to show, how course timetabling
problem can be transformed into RCPSP. We solve this
transformation model with genetic algorithm.