Efficient solutions for a university timetabling problem through integer programming |
| |
| Institution: | 1. Department of Engineering Sciences, University of Patras, Rio Patras, GR-26500, Greece;2. Department of Electrical & Computer Engineering, University of Patras, Rio Patras, GR-26500, Greece;1. Section of Operations Research, Department of Management Engineering, Technical University of Denmark, DK-2800 Kgs. Lyngby, Denmark;2. MaCom A/S, Vesterbrogade 48, 1., DK-1620 Copenhagen V, Denmark;3. Chair of Operations Research, RWTH Aachen University, Kackertstrasse 7, 52072 Aachen, Germany;1. School of Computer Sciences, Universiti Sains Malaysia, Penang, Malaysia;2. Department of Computer Science, University of Ilorin, Ilorin, Nigeria;3. Department of Information Technology, Al-Huson University College, Al-Balqa Applied University, P.O. Box 50, Al-Huson, Irbid, Jordan;1. Software Engineering Research Group, Software Engineering Department, Universiti Teknologi Malaysia, 81310 UTM Skudai, Johor, Malaysia;2. Department of Computer Science, Queen’s University Belfast, Belfast BT7 1NN, United Kingdom;3. Department of Electronic, Information and Communication Engineering, Osaka Institute of Technology, Osaka 535-8585, Japan;1. DIES, University of Udine, via Tomadini 30/A, I-33100 Udine, Italy;2. DIEGM, University of Udine, via delle Scienze 208, I-33100 Udine, Italy;3. NICTA, Canberra Research Laboratory, Tower A, 7 London Circuit, Canberra ACT 2601, Australia;1. School of Science and Technology, Hellenic Open University, Parodos Aristotelous 18, 26335 Patra, Greece;2. Department of Business Administration of Food and Agricultural Enterprises, University of Patras, G. Seferi 2, GR-30100 Agrinio, Greece |
| |
| Abstract: | Integer programming has always been an alternative for formulating combinatorial problems such as the university timetabling problem. However, the effort required for modeling complicated operational rules, as well as the computational difficulties that result from the size of real problems have discouraged researchers and made them turn their interest to other approaches. In this paper, a two-stage relaxation procedure that solves efficiently the integer programming formulation of a university timetabling problem is presented. The relaxation is performed in the first stage and concerns the constraints that warrantee consecutiveness in multi-period sessions of certain courses. These constraints, which are computationally heavier than the others, are recovered during the second stage and a number of sub-problems, one for each day of the week, are solved for local optima. Comparing to a solution approach that solves the problem in a single stage, computation time is reduced significantly without any loss in quality for the resulting timetables. The new solution approach gives a chance for further improvements in the final timetables, as well as for certain degree of interaction with the users during the construction of the timetables. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
