Timetabling is defined as the allocation, subject to constraints,
of given resources to objects being placed in space-time, in such a way as to
satisfy as nearly as possible a set of desirable objectives (Wren,
1996). This work focus on university course timetabling problem that assign
a set of courses within a given number of rooms and time periods (McCollum
and Ireland, 2006). Generating a course timetable manually often requires
a lot of time, effort and usually it is hard to satisfy all constraints. Thus,
automating the generation of course timetables is still a challenging task (McCollum
and Ireland, 2006).
Many researchers have focused on solving this problem using meta-heuristics.
The Meta-heuristics are typically high-level strategies which guide an
underlying, more problem specific heuristic, to increase their performance
(Blum and Roli, 2003). Some example of common mela-heuristics
approaches are: ant colony optimization (Eley, 2007),
genetic algorithms (Ueda et al., 2004), tabu
search (Alvarez-Valdds et al., 2002), evolutionary
search (Beligiannis et al., 2008) and Simulated
Annealing (SA) (Abramson et al., 1999).
SA is one of the popular meta-heuristic algorithms due to its ease of implementation
and ability to solve many combinatorial optimization problems. However, the
disadvantages are that, it could still get trapped in local optimum and take
longer time to find good quality solutions (Xinchao, 2011).
Several researchers have tried to overcome this drawback. For examples, Azizi
et al. (2009) proposed a hybrid simulated annealing with evolution-based
diversification approach called SAMED to solve job shop scheduling problem.
SAMED hybridized SA, three types of memories and GA based crossover component.
The first two types of memories are short term memories (tabu list and seed
memory list), while the third type is long term memory. SAMED used short term
memory (tabu list) to temporarily save the accepted solutions to avoid the recycling;
whilst the second short term memory (seed memory) is to keep track of the best
solutions with lowest objectives functions for further improvement. The differences
between our study with SAMED is in the memory part. We save the unaccepted solutions
to jump to other promising region when the search got trapped in local optimum,
whilst the SAMED save the best accepted solutions. Gao et
al. (2006) presented a hybrid meta-heuristic algorithm by combined the
characteristic of simulated annealing, genetic algorithm and chaos strategy
to solve TSP problem. The experimental results showed that the hybrid meta-heuristic
algorithm (CASAGA) is quite flexible with satisfactory results.
Kolonko (1999) investigated the cooling schedules for
a wide range of examination timetabling problems and proposed that, very slow
cooling schedule should be used. Thompson and Dowsland (1995)
and Swarnkar and Tiwari (2004) hybridized SA with tabu
search to avoid revisiting solutions. Jeon and Kim (2004)
proposed UMOSA algorithm that use a strategy called the criterion scalarizing
approach since the probability to accept new solution must take into account
the distance between the old and the new move. Elmohamed
et al. (1998) employed a simulated annealing with different cooling
schedules (geometric, adaptive and adaptive with reheating). The experiment
results showed that using SA with adaptive cooling schedules with reheating
is able to generate competitive results comparing with other state-of-the-art
techniques and outperformed other SA approaches. Therefore, the use of reheating
function might be good to escape from local optimum, whilst the search could
revisit the same local optimum again after several iterations. Nevertheless,
The use of memory to save the not accepted solutions and reuse one of them when
the search trapped in local optimum could avoid to re-trapped in the same local
optimum again and escape from local optimum.
This study aims to solve the problem of trapping in local optimum especially when the temperature in SA are very low. The low temperature leads SA to accept only improved solutions. This means more chance to get trap in local optimum. The question is:
||How to escape from local optimum, if the search got trapped
Hybridize the simulated annealing with other techniques may be a reasonable good answer for the above question. However, this might not be efficient to deal with a bad solution structure that leads the search to get trapped in bad local optimum (very hard to escape). Therefore, this study aims to deal with this problem by saving several unaccepted solutions; and to reuse them when the search got trapped in the local optimum, in order to jump to other promising region.
The contribution of this work is to enhance the performance of SA by escaping from local optimum using solutions memory by saving non-accepted solutions and reuse it when the search got trapped in local optimum.
The Curriculum-based Course Timetabling problem for the ITC-2007 is about the
scheduling all lectures for a set of courses into a weekly timetable. Each lecture
of a course must be assigned to periods and rooms in accordance to a given set
of constraints. The employed method of determining the schedule must be able
to satisfy the hard constraints and to minimize the soft constraints violations.
This problem has four hard constraints H1-H4 and four soft constraints S1-S4
as follows (Gaspero et al., 2007):
H1: Lectures. All lectures of a course must be scheduled to a distinct periods
H2: Room Occupancy. Any two lectures cannot be assigned to the same period and the same room
H3: Conflicts. Lectures of courses in the same curriculum or taught by the same teacher cannot be schedule in the same period
H4: Availability. If the teacher of a course is not available at a given period, then no lectures of the course can be assigned to that period
S1: Room Capacity. For each lecture, the number of students attending the course should not be greater than the capacity of the room hosting the lecture
S2: Minimum Working Days. The lectures of a course should be spread into the given minimum number of days
S3: Room Stability. All lectures of a course should be scheduled at the same room. If this is impossible, the number of occupied rooms should be as few as possible
S4: Curriculum Compactness. For a given curriculum a violation is counted if there is one lecture not adjacent to any other lecture belonging to the same curriculum within the same day, which means the agenda of students should be as compact as possible
This work is divided into two stages. The first stage is to construct initial
solution using constructive algorithms. At this stage, the feasible initial
solution is constructed by satisfying all hard constraints (H1-H4) using sequential
greedy heuristic as in Lu and Hao (2010). There is
no guarantee that this greedy heuristic can always find feasible solution. Therefore,
we used steepest decent to search for a feasible solution if the solution still
not feasible. The second stage is to minimize soft constraints violations. At
this stage, we used the enhanced Simulated Annealing with memory (SAM).
Simulated annealing with memory: SA has been widely used to solve combinatorial optimization problems. It accepts the new solution when the objective value is lower than or equals to the current one. There is a probability to accept worse quality solutions using probability acceptance criteria:
This probability function controls the acceptance of new solution, where Δf = f (s*)-f (s), the difference between the quality of new solution f (s*) and the current solution f (s). The current temperature, T1 is iteratively reduced according to the cooling schedule with a given cooling rate α for each iteration or level until this temperature reaches final minimum temperature, which is close to Zero, Tmin.
When the SA temperature becomes very low, the SA behaves like descent heuristic
(accept only improve solution). Thus, the search might easily be trapped in
local optimum. Therefore, this work will save several non-accepted solutions
(Solm) in the memory during the search (before the non- improvement)
and randomly employs one of these solutions when local optimum is met. The memory
size is fixed and is updated by replacing the worst solutions in memory with
new ones (Fig. 1).
Our SA algorithm involves: neighborhood structure, temperature, cooling schedule, termination criteria and memory.
The algorithm terminates when one of the three cases occurs:
||Case I: The minimum temperature Tmin closed
to zero (frozen stage) (Tmin = 0.0001).
||Case II: Number of iterations.
||Case III: Timeout based on ITC 2007 course timetabling track 3
||Sol be an initial solution,
||f (Sol) as the quality of Sol,
||Sol* as the best found solution so far;
||Iter as the total iterations number,
||Citer as the current iteration,
||T0 as the initial temperature,
||TC as the current temperature,
as the non-improvement consecutive iterations,
||Mem as the memory that save the not accepted solution with length μ.
|| Proposed schematic representation of SA with memory
|| A pseudo-code for SAM
The algorithm begins with a given initial solution. First, it generates n neighbors
from Ni neighborhood structures. The best (Sol1) and second
(Sol2) (based on the quality of solutions) are selected. The algorithm
accepts (Sol1) if its objective value is less than or equals the
current solution (Sol), whilse (Sol2) will be saved in the memory
(if the memory (Mem) is full replace the worst solution in Mem with (Sol2).
In case (Sol1) if (Sol) (i.e., the quality of Sol1 is
worse than Sol), the acceptance criteria (e(-Δ/T)) is applied.
generated random number is between 0 and 1, the Sol1 is accepted.
Similarly, the memory Mem is updated with (Sol2). If the algorithm
does not accept (Sol1), Mem will be updated by (Sol1)(Fig.
When the non-improvement consecutive iterations are met, one solution is randomly selected from the Mem and a shaking procedure is applied on it to produce Solm. This will divert the search to other solution space, by randomly swap the highest penalties lecture with other lectures (free clash), when the difference Δ between the solution Solm and the current solution Sol is less than Costr (Eq. 1):
where, Iter is total iterations number, CIter is the current iterations,
f (Sol) the current cost and Costr is the cost range to limit the
cost value of Solm. Lu and Hao (2010) presented
strategy called penalty guided perturbation to improve the best solution if
the search cannot improve it. They employed the perturbation operator to reconstruct
the obtained local optimum by selecting a number of the highly-penalized lectures
randomly and applies swap or move. The difference between the proposed shaking
procedure and (Lu and Hao, 2010) is in the ranking
penalties of soft constraint violation. Lu and Hao (2010)
ranked the lectures in non-increasing order according to their total penalties
of soft constraint violations (for all soft constraints penalties). Whilst,
the proposed shaking procedure assign the lectures in non-increasing way according
to each soft constraint penalty independently, so that almost all lectures with
high penalty will be involved in this shaking procedure during the search space.
Neighborhood structure: One of the important features of local search
algorithm is the definition of its neighborhood (Lu and
Hao, 2010). This study use three neighborhood structures denoted by NS1,
NS2 and NS3. (Note: - all neighborhoods consider free
NS1: Move one lecture from the current period to another
free position period.
NS2: Randomly swaps two different lectures from different
time slots and rooms.
NS3: Normally the selection mechanism in neighborhood structure
happens randomly (e.g:- select two lectures randomly which belongs to two different
rooms and slots). Thus, the search may need more time to reach good solution.
Hence, this study proposed neighborhood structure to minimize the random selection.
In NS3, the total soft constraints violations for each timeslot and
sum them up for all days in the week is calculated (Table 1)
and the highest penalty timeslot is swapped with randomly selected timeslot.
|| Soft constraint violation for each period and time slot
|| Average penalty costs and CPU time for NS1, NS2
and NS3 neighborhood structures and their combinations over 35
Cooling schedule: The performance of SA depends heavily on the cooling
schedule (Blum and Roli, 2003). This work used cooling
scheme that was proposed by Lewis (2006) as follow:
where, β represents a parameter to control a value for λ. The resulting
value for λ is used to influence the amount of concavity or convexity present
in the cooling schedule. M represents the number of steps taken by temperature
T0 to decrease to a value close to zero. In this experiment, the
parameters are set based on the preliminary experiments, where T0
= 1500 and β- -0.99 as in Lewis (2006) study.
Experiment and result: This study test on 3 datasets instances categories.
The first 4 instances (test 1-4) were previously used for the old version of
the Curriculum-based Course Timetabling (CB-CTT) in the literature (Di
Gaspero and Schaerf, 2006). The second 7 instances (DDS1-DDS7) proposed
by Bonutti et al. (2008) and the third 21 competition
instances from The Second International Timetabling Competition ITC 2007 track
3 (Gaspero et al., 2007). This work is programmed
in vb.net 2010 on a PC Windows Vista platform with 2.10 GHz CPU and 4 GB RAM.
The experiment was first carried out to analyze the performance of the proposed
neighborhood structure (NS3). Table 2 shows the
results of the experiments that were carried out on the three neighborhoods
and their different combinations. For comparison purpose, this experiment applied
Steepest Descent (SD) with for the first 8 competition instances (Abramson
et al., 1999). The average penalty cost and CPU time over 35 independent
runs is reported in Table 2. From Table 2
one clearly finds that obtain much better quality solution. According to the
results, starting from NS1 will decrees the costs and minimizes the
CPU time more than from NS2. This result had encouraged this study
to use this combination in the enhance SA.
Firstly, to make a fair comparison, the basic SA applied with geometric cooling
schedule (Abramson et al.,1999) and compare
it with the SA with the adopted cooling schema proposed by Lewis
(2006) in Table 3. The SA with the adopted cooling schema
performed better than the geometric cooling schedule almost in all instances,
whereas geometric cooling schedule performed better in Comp 5 and Comp 10 but
ties with the adopted cooling schema.
||Comparable results between SAs (adopted cooling schema and
geometric cooling schema) average penalties costs over 30 indepe ndent runs
||Comparison between different numbers of non-Improved iteration
(average value of penalty costs over 25 runs)
||Computational statistics results of the SAM algorithm over
30 independent runs under the ITC 2007 competition stop conditions
Next, this study made preliminary experiments to find good number non improvement
consecutive iterations, .
is the maximum number of consecutive iterations that the search is allowed to
local optimum. When this number is met, the search will randomly select a solution
from the memory (Mem). For this experiment, Comp 1 and Comp 11 are used to investigate
this parameter. Table 4 showed that in 25 runs the best
Results under ITC 2007 timeout condition: Table 5
illustrates the computational statistic of the proposed SAM algorithm based
to the following performance indicators:- the best penalty cost (Best), the
average penalty costs (Mean), median result (Median) and the standard deviation
over 30 runs.
||Best results and comparison with the best known results under
ITC 2007 timeout condition over 30 independent runs
|Best results are bold
Results in Table 5 showed that SAM standard deviation is quite small and the mean penalty results is small as well.
Table 6 shows the comparison results of SAM with best known
results under ITC 2007 timeout condition (http://tabu.diegm.uniud.it/ct/).
The first column indicates the instances. Column 2-4 indicate the penalty of
best, average results and average runs time in seconds over 30 runs on each
instance for the SAM. Column 5-6 shows the penalty cost of the best known results
and the approaches that obtained the best known results.
As shown in Table 6, SAM obtained competitive results with
all best known approaches. For instance Comp 1, Comp 11, DDS2, DDS3, DDS5, DDS6,
DDS7 and Toy, the optimal solutions are found (under the ITC 2007 timeout condition).
Therefore, this study can conclude that the SAM algorithm is generally able
to produce high quality solutions when compared to the best known results.
In the next experimentation, the experiments evaluate the performance of SAM
with other algorithms in literature (Lu and Hao, 2010;
Cesco et al., 2008; Muller,
2008; Lach and Lubbecke, 2008; Geiger,
2008; Clark et al., 2008), (M2 to M6) consecutively
(Table 6). Best solutions cost is written in bold.
This study presented a new hybridization between simulated annealing with non-accepted
solutions memory. The main idea of the hybrid SAM is to enhance the ability
of escaping from local optimum. SA could be trapped in local optimum especially
when the temperature is very low. When the search trapped in local optimum for
a number of consecutive non-improvement solutions, SAM randomly select one solution
from the memory which was generated and not-accepted in some recently visited
iterations, to be the current solution . Thus, the search can jump to other
promising region and escape from local optimum. Whilst, the memory and the proposed
shaking procedure leads the search to avoid recycling and trapping in the same
In this work, the SAM algorithm is evaluated on curriculum-based course timetabling problem track 3 of the Second International Timetabling Competition. The computational results showed that the SAM algorithm competes very well with reference algorithms and the best known results in the literature. Thus, the proposed SAM enhanced the SA performance by enhancing the ability of escaping from local optimum, which might lead to a good promising region.
In future works, the next study plan to use tabu list mechanism to save both not accepted and not visited solutions in order to avoid recycling and will test it on in real world course timetable dataset from Universiti Kebangsaan Malaysia (Faculty of Engineering case study).
The authors wish to thank Ministry of Higher Education for supporting this work under the FRGS Research Grant Scheme (FRGS/1/2012/SG05/UKM/02/11).