
## 3 Construction Of Feasible Initial Solutions 3.1 Preprocessing

Prior to the computation of a first solution, some preprocessing is carried out. This preprocessing is relevant both for the construction of an initial solution, as well as for the following improvement phase. In brief, some problem-specific characteristics are employed, adding some additional structure to the problem.

For each given lecture Li, events Ei1, . . . , Eie **are created which are later assigned**
to timeslots. The number of events e **is given in the problem instances. Creating events**
for each lecture leads to a more general problem description, and the solution approach only needs to concentrate on the assignment of all events, one to a single timeslot, as opposed to keeping track of assigning a lecture to e **timeslots.**
Second, we categorize for each lecture Li **(and thus for each event belonging to**
lecture Li**) the available rooms in three disjunct classes** Ri1, Ri2, Ri3.

Ri1 refers to the rooms in which the lecture fits best, that is the rooms Rk **with the**
minimum positive or zero value of ck − si, ck being the room capacity, si **the number**
of students of lecture Li.

The class Ri2 stores the rooms in which lecture Li fits, that is si < ck**, but not best,**
and Ri3 contains the rooms in which lecture Li **does not fit. With respect to the given**
problem statement, events of lectures may be assigned to timeslots of rooms in Ri3, this however results in a penalty.

The underlying assumption of the classification of the rooms **is that events are**
preferably assigned to timeslots belonging to a room of class Ri1**, followed by** Ri2 and Ri3**. It has to be mentioned however, that this cannot be understood as a binding,**
general rule but rather should be seen as a recommendation. A **randomized procedure is** therefore going to be implemented when assigning events to timeslots (see the following section), allowing a certain deviation from the computed room order.

## 3.2 A Myopic Construction Approach The Method

The constructive phase tries to obtain a first feasible assignment of all events to timeslots. A simple heuristic approach is used, successively assigning all events to timeslots, one at a time, with the given pseudo-code of Algorithm 1. In this description, we denote the set of all events with E**, and the set of unassigned (open) events with** E
o.

During the successive assignment procedure, a set of events **that have been impossible**
to assign is maintained, denoted with E
u**. In cases of assigning all events to timeslots,**
E
u = ∅ **is returned.**
A greedy approach is used in the assignment procedure, selecting in each step the
'most critical' event E **from** E
o**, that is the event with the smallest number of timeslots**
to which it may be assigned.

The choice of timeslots for the events reflects the initial categorization of rooms.

With a probability of 0.5, timeslots of rooms in Ri1 are preferred over Ri2 **over** Ri3, and with a probability of 0.5, timeslots of Ri2 are preferred over the ones of Ri1 **over** Ri3**. Within each class, timeslots are randomly chosen with equal probability. In cases**
where a most-preferred class of timeslots is empty, the choice is made from the lesser preferred class and so on.

3