The Collaborative Traineeship Planning Problem

In this thesis we study the collaborative traineeship planning problem (CTPP). This problem consists of the construction of an initial traineeship planning and the rescheduling of an existing planning in case of disturbances. We start by pointing out some places in the literature related to the CTPP. We then formulate the initial planning problem as a Mixed Integer Programming problem (MIP). Thereafter, we formulate the rescheduling problem as a MIP by extending the MIP formulation of the initial planning problem. We prove both problems are NP-complete. Next, we elaborate on an exact approach for the initial planning problem wherein we exploit variable fixing methods and valid inequalities to increase the performance of a branch-and-bound algorithm. Furthermore, we consider a three-stage genetic algorithm as heuristic approach to solve the initial planning problem. We formulate the subproblem in this genetic algorithm as a MIP and impose symmetry breaking constraints in an attempt to improve the performance in terms of computation time. Also, for the rescheduling problem we consider an exact and a heuristic approach. In the exact approach we again take advantage of variable fixing methods and valid inequalities. The heuristic approach consists of a variable neighborhood search strategy, where each neighborhood is evaluated by means of a tabu search procedure. Finally, we provide results for both the initial planning as well as the rescheduling problem.