EXCHANGES PROCEDURES FOR TIMETABLING PROBLEMS

Timetabling problems appear in several practical applications, and they can be formulated as 0-1 programming problems to determine an optimal assignment of items to resources minimizing total cost and satisfying K additional side constraints. The proposed approach to deal with this problem is a heuristic iterative procedure where the assignment of one item is modified at each iteration. This exchange procedure is applied first to determine a feasible solution satisfying the side constraints, and then to improve the objective function. A geometric interpretation of an exchange is first given to induce a theoretical framework for the procedure. Furthermore, two other procedures are introduced to prevent jamming situations outside the feasible domain or at a local optimum. The first procedure uses inductively more than one exchange per iteration, and the second one relies on Lagrangean relaxation.