Effective computational models for timetabling problem

Abstract

Timetabling is a table of information showing when certain events are scheduled to take place. Timetabling is in fact very essential in making sure that all events occur in the time and place required. It is critical in areas such as: education, production and manufacturing, sport competitions, transport and logistics. The difficulty in timetabling is satisfying all the restrictions and requirements. The restrictions relate to resources such as time and location as well as conflicts. The requirements relate to the preferences of customers and service providers. The problem is further complicated by the desire to optimize an objective function that usually relates to the cost or effectiveness of the schedule. The task of how to construct a high quality timetable which satisfies all requirements is definitely not an easy one. A further difficulty is the dynamic aspect of timetabling and the need to accommodate changes after the schedule has been announced. Our focus in this study is on university timetabling problems.Mathematically, the problem is to optimize an objective function that reflects the value of the schedule subject to a set of constraints that relate to various operational requirements and a range of resource constraints (lecturers, rooms, etc). The usual objective is to maximize the total preferences or to minimize the number of students affected by clashes. The problem can be conveniently expressed as an Integer Programming (IP) problem. The computational difficulty is due to the integer restrictions on the variables. Various computational models including both heuristics and exact methods have been proposed.The timetabling problem in universities courses has existed for a long time, but due to the complexity and its variation, many researchers are still trying to decipher the solution for this problem. Numerous methods have been developed over the years and most of them have been successful. However, according to McCollum (2006) based on the international review of Operational Research in the UK (Commissioned by the Engineering and Physical Sciences Research Council), a gap still exists between the theory and practice of timetabling. Additionally, Burke and Petrovic (2002) also mentioned that many methods that have succeeded in solving this problem are applicable to specific institutions where they are designed. Nevertheless, Benli and Botsali (2004) explained that there is no generalized model for this problem because of the variation present in each university. Moreover, the limited availability of facilities and growth of flexibility of the student’s choices of courses makes the problem even tighter.This thesis in whole outlines studies which gain a step in a pathway to develop a more general IP model for university course timetabling problem. We incorporate all important features of this problem which includes the hard constraints and the desirable soft constraints. AIMMS 3.11 mathematical software is employed as a tool to solve the models with CPLEX 12.1 as the solver.In the first study (Chapter 3), we aim to develop models for timetabling problems which are flexible in terms of the ability to be applied in various institutions. To achieve this, we gather the information obtained on features that are used in other studies, which is covered in the literature review (Chapter 2) of this thesis. From the information on the gathered features, we observed that some features are compulsory, being that they are always used in models to solve timetabling problems. These features therefore form a basic model of university course timetabling problem in this study. We then develop an extended model by incorporating additional features found from the literature. The extended model also contains a few more additional features which we generate that are significant to be included in a model for solving this problem.Different combinations of the features which form the extended model are extracted to produce a range of models. These models are useful to be used by any institutions which require some relevant features to solve their timetabling problem. These models are tested with a small randomly generated test problem. In the following chapter (Chapter 4), we apply the developed model into 3 case studies obtained from the literature. The objective of this is to test the efficiency of the developed models for application to larger problems. Appropriate variation models are used to solve each of the case studies. This application testing is further extended by including a number of additional features. This is to illustrate that the developed model is able to be applied in institutions even ivwhen changes of requirements occur. Results from these tests demonstrate successful outcomes from application of our developed models to the chosen case studies.In Chapter 5, we tested the application of the developed models application in a case study using a pre-assignment approach as a simplification in solving timetabling problem. In this approach, the core units are determined and prioritized to be assigned into prime time slots at the very beginning of the scheduling process. It then follows with the assignment of the remainder units subject to the university requirements. One case study which is applied in Chapter 4 is used for the purpose of testing the pre-assignment approach. From this testing, we show that the pre-assignment is a useful simplification tool in solving timetabling problem of the chosen case study using the developed model, especially in reducing the computational time. We believe that this approach can be applied in other case studies using the developed model.As an overview of the thesis, we believe that the developed models will be applicable to other problems apart from the ones tested.