کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
474637 | 699086 | 2014 | 10 صفحه PDF | دانلود رایگان |
The high school timetabling is a classical combinatorial optimization problem that takes a large number of variables and constraints into account. Due to its combinatorial nature, solving medium and large instances to optimality is a challenging task. When resources are tight, it is often difficult to find even a feasible solution. Among the different requirements that are considered in Brazilian schools, two compactness requirements must be met on a teacher׳s schedule: the minimization of working days and the avoidance of idle timeslots. In this paper, we present a mixed integer linear programming model and a fix-and-optimize heuristic combined with a variable neighborhood descent method. Our method uses three different types of decompositions - class, teacher and day – in order to solve the high school timetabling problem. The method is able to find new best known solutions for seven instances, including three optimal ones. A comparison with results reported in the literature shows that the proposed fix-and-optimize heuristic outperforms state-of-the-art techniques for the resolution of the problem at hand.
Journal: Computers & Operations Research - Volume 52, Part A, December 2014, Pages 29–38