Beta 1


Title Metaheuristics for High School Planning
Author Binzer, Sune Pelle
Kjeldsen, Sune Høj
Supervisor Stidsen, Thomas K. (Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2008
Abstract This report investigates the application of metaheuristics for solving practical planning problems of Danish high schools. Two important planning problems are specified and formulated mathematically; the Packing Problem and the Timetabling Problem. They are both practical subproblems of the timetabling process in a school. Timetabling has been the subject of much research, while the subproblem of Packing has had little attention. Both problems are shown to be NP-hard. For the Packing Problem, two metaheuristics are implemented, GRASP and Tabu Search, and they provide near-optimal results for a suite of practical problem instances. For the Timetabling Problem, a Tabu Search algorithm with three diversification techniques and a Genetic Algorithm with guided mutation are implemented. Experiments are performed on data sampled from real school timetables. The Genetic Algorithm does not perform as well as the Tabu Search due to premature convergence. The Tabu Search algorithm finds feasible or close to feasible timetables within a reasonable amount of time.
Series IMM-M.Sc.-2008-50
Fulltext
Original PDF ep08_52.pdf (0.92 MB)
Admin Creation date: 2008-06-11    Update date: 2008-06-11    Source: dtu    ID: 220643    Original MXD