Lower bounds for the ITC-2007 curriculum-based course timetabling problem

被引:16
作者
Hao, Jin-Kao [1 ]
Benlic, Una [1 ]
机构
[1] Univ Angers, LERIA, F-49045 Angers 01, France
关键词
Bounds; Partitioning; Tabu search; Timetabling; SEARCH;
D O I
10.1016/j.ejor.2011.02.019
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
This paper describes an approach for generating lower bounds for the curriculum-based course timetabling problem, which was presented at the International Timetabling Competition (ITC-2007, Track 3). So far, several methods based on integer linear programming have been proposed for computing lower bounds of this minimization problem. We present a new partition-based approach that is based on the "divide and conquer" principle. The proposed approach uses iterative tabu search to partition the initial problem into sub-problems which are solved with an ILP solver. Computational outcomes show that this approach is able to improve on the current best lower bounds for 12 out of the 21 benchmark instances, and to prove optimality for 6 of them. These new lower bounds are useful to estimate the quality of the upper bounds obtained with various heuristic approaches. (C) 2011 Elsevier B.V. All rights reserved.
引用
收藏
页码:464 / 472
页数:9
相关论文
共 19 条
[1]   A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations [J].
Al-Yakoob, Salem M. ;
Sherali, Hanif D. .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 180 (03) :1028-1044
[2]  
[Anonymous], 2006, J MATH MODELLING ALG
[3]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[4]  
[Anonymous], 1997, TABU SEARCH
[5]  
ATSUTA M, 2009, THESIS KWANSEI GAKUI
[6]  
BONUTTI A, CURRICULUM BASED COU
[7]   Decomposition, reformulation, and diving in university course timetabling [J].
Burke, Edmund K. ;
Marecek, Jakub ;
Parkes, Andrew J. ;
Rudova, Hana .
COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (03) :582-597
[8]  
CLARK M, P 7 INT C PRACT THEO
[9]   A decomposed metaheuristic approach for a real-world university timetabling problem [J].
De Causmaecker, Patrick ;
Demeester, Peter ;
Vanden Berghe, Greet .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 195 (01) :307-318
[10]  
DIGASPERO L, 2007, 20070801 U UD DIEGM