haku: @all interaction / yhteensä: 324
viite: 313 / 324
Tekijä: | Daskalaki, S. Birbas, T. |
Otsikko: | Efficient solutions for a university timetabling problem through integer programming |
Lehti: | European Journal of Operational Research
2005 : JAN, VOL. 160:1, p. 106-120 |
Asiasana: | Timetabling Scheduling Integer programming Models Universities |
Kieli: | eng |
Tiivistelmä: | 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