
## 4 Threshold Accepting Based Improvement 4.1 Description Of The Approach

The constructive approach as described in Section 3 only aims to identify a first feasible assignment of events to timeslots, not taking into consideration the resulting soft constraint violations. An iterative procedure continues from **here, searching for an optimal**
solution with respect to the soft constraints.

The formulation of the approach is rather general. One of the **reason for this is that** while we hope for a feasible assignment of all events, the constructive approach does not guarantee it. Nevertheless, search for improved solutions needs to continue at some point, and an approach that is able to handle infeasible solutions is therefore required. Also, in case of an infeasible first assignment, the procedure should be able to later identify a feasible one.

In each step of the procedure, a number of randomly chosen events is unassigned from the timetable and reinserted in the set E
u**. A reassignment phase follows. Contrary**
to the constructive approach, where events are selected based on whether they are critical with respect to the available timeslots, events are now randomly chosen from E
u**, each event with identical probability. The choice of the timeslot follows the logic as**
described in the constructive approach, prioritizing timeslots of particular room classes.

Again, we use the two possible preference structures of rooms, Ri1 over Ri2 **over** Ri3, and Ri2 over Ri1 over Ri3**. Each of them is randomly chosen with probability 0.5.**
When evaluating timetables, two criteria are considered. First, the number of unassigned timeslots (distance to feasibility) hc**, second, the total penalty with respect to**
the given soft constraints sc**. Comparison of solutions implies a lexicographic ordering** of the hard constraint violations hc over the penalty function sc**. We therefore accept**
timetables minimizing the distance to feasibility independent from the soft constraint count. This means that in cases in which the initial construction phase is unable to assign all events to timeslots, a later assignment of more events is preferred independent from an increasing value of sc**, closely following the evaluation of solutions as given in**
the ITC 2007.

In case of identical distance to feasibility hc, inferior solutions with respect to sc are accepted up to a threshold. This idea has been introduced by the Threshold Accepting metaheuristic [5], a simplified deterministic variant of Simulated Annealing. Previous research has shown that simplifications of Simulated Annealing may be very effective for timetabling problems [1].

The implementation of the Threshold Accepting approach compares the quality of neighboring solutions with the current best alternative, permitting an acceptance of inferior alternatives up to the given threshold. An alternative strategy would be the comparison with the current solution instead of the globally best one. In this case however, a subsequent acceptance of inferior solutions can **happen, and for that reason,**
the more restrictive acceptance strategy has been chosen.

## 4.2 First Results And Comparison With Other Approaches

Different configurations of the algorithm have been tested on **the benchmark data** from the ITC 2007. A first implementation has been made available, however without optimizing the code with respect to speed and efficiency. This has been done later, and 7