DocumentCode :
2847173
Title :
A variant of examination timetabling problem
Author :
Chen, Weiwei ; Shi, Leyuan
Author_Institution :
Dept. of Ind. & Syst. Eng., Univ. of Wisconsin-Madison, Madison, WI
fYear :
2008
fDate :
23-26 Aug. 2008
Firstpage :
353
Lastpage :
358
Abstract :
The examination timetabling problem is a typical combinatorial optimization problem. In literature, heuristic methods are usually chosen to solve these problems, and mathematical programming approaches have not been well developed. This paper raises a variant of exam timetabling, with multiple exam paper versions, which comes from real-world applications. The mathematical formulation is presented, and further refined under assumptions to make it solvable for large-scale problems. Then, a preprocessing procedure, called ldquogroup-and-dividerdquo, is introduced to improve the solution quality by reducing the size of the input data. In addition, the symmetry of the model is studied, and a set of constraints are added to break the strong symmetry existing in the model. Real data are tested using CPLEX solver, and the results show that our approach is effective and applicable for real-world problems.
Keywords :
combinatorial mathematics; education; mathematical programming; combinatorial optimization problem; examination timetabling problem; group-and-divide preprocessing procedure; heuristic method; mathematical formulation; mathematical programming approach; multiple exam paper version; Automation; Bridges; Costing; Data preprocessing; Job shop scheduling; Mathematical programming; Search methods; Systems engineering and theory; Testing; USA Councils; Examination Timetabling; Mathematical Programming; Preprocessing; Symmetry Breaking;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Automation Science and Engineering, 2008. CASE 2008. IEEE International Conference on
Conference_Location :
Arlington, VA
Print_ISBN :
978-1-4244-2022-3
Electronic_ISBN :
978-1-4244-2023-0
Type :
conf
DOI :
10.1109/COASE.2008.4626428
Filename :
4626428
Link To Document :
بازگشت