search query: @indexterm integer programming / total: 355
reference: 3 / 355
| Author: | Daskalaki, S. Birbas, T. |
| Title: | Efficient solutions for a university timetabling problem through integer programming |
| Journal: | European Journal of Operational Research
2005 : JAN, VOL. 160:1, p. 106-120 |
| Index terms: | Timetabling Scheduling Integer programming Models Universities |
| Language: | eng |
| Abstract: | Integer programming (henceforth as: i-p.) has always been an alternative for formulating combinatorial problems such as the university timetabling problem (here as: u-t-p. | for 'timetable/s' as: t-t./t-ts.). This paper presents another approach, that is, a 2-stage (for 'stage' here as: stg./stgs.) relaxation procedure that solves efficiently the i-p. formulation of a u-t-p. The relaxation is performed in the first stg. and concerns the constraints (here as: cnstrs.) that warrantee consecutiveness in multi-period sessions of certain courses. These cnstrs., which are computationally heavier than the others, are recovered during the second stg. and a number of sub-problems, one for each day of the week, are solved for local optima. Comparing to a solution approach solving the problem in a single stg., computation time is reduced significantly without any loss in quality for the resulting t-ts. The new solution approach gives a chance for further improvements in the final t/ts., as well as for certain degree of interaction with the users during the construction of the t-ts. |
SCIMA