Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.16 No.1 pp.141-153
DOI : https://doi.org/10.7232/iems.2017.16.1.141

An Integer Programming Model for a Complex University Timetabling Problem: A Case Study

R. A. Ranga Prabodanie*
Department of Industrial Management, Faculty of Applied Sciences, Wayamba University of Sri Lanka, Kuliyapitiya, Sri Lanka
Corresponding author : ranga@wyb.ac.lk
May 26, 2016 October 7, 2016 November 14, 2016

ABSTRACT

A binary integer programming model is proposed for a complex timetabling problem in a university faculty which conducts various degree programs. The decision variables are defined with fewer dimensions to economize the model size of large scale problems and to improve modeling efficiency. Binary matrices are used to incorporate the relationships between the courses and students, and the courses and teachers. The model includes generally applicable constraints such as completeness, uniqueness, and consecutiveness; and case specific constraints. The model was coded and solved using Open Solver which is an open-source optimizer available as an Excel add-in. The results indicate that complicated timetabling problems with large numbers of courses and student groups can be formulated more efficiently with fewer numbers of variables and constraints using the proposed modeling framework. The model could effectively generate timetables with a significantly lower number of work hours per week compared to currently used timetables. The model results indicate that the particular timetabling problem is bounded by the student overlaps, and both human and physical resource constraints are insignificant.


초록


    1.INTRODUCTION

    Academic timetabling is a well-known scheduling problem discussed in operations research. Integer Programming (IP) models of timetabling problems belong to the family of NP-hard combinatorial optimization problems which are difficult to solve. With such problems, the time required to find an optimal solution grows rapidly with the size of the problem (Hochbaum, 1997). Nevertheless, owing to the rapid growth of algorithmic efficiency and computational power, efficient tools are now available to solve even large scale timetabling problems (Cacchiani et al., 2013; Badoni et al., 2014; Phillips et al., 2015; Bellio et al., 2016), but still applications of such optimization methods are not very common, particularly in the Sri Lankan context. University timetables are usually prepared by administrative officers based on previous years’ timetables by making amendments to cater new developments. Sometimes these timetables are revised several times to avoid clashes, creating difficulties to both staff and students. Teachers’ and students’ preferences are rarely considered in preparing timetables. Tight timetables (with little or no free time) sometimes restrict the choice of optional courses that the students can take. Timetables with long work days are sometimes blamed for lack of student participation in sports and other extracurricular activities. Given a large number of courses, a variety of subject combinations, and limited resources, it is reasonable to encounter such issues in manually prepared timetables. Lack of knowledge on scientific methods of scheduling, institutional politics, and poor management may have contributed to inefficient timetabling in universities.

    Mathematicians’ involvement in academic timetabl- ing has a long history dating back to the nineteen sixties. A wide variety of methods such as simulated annealing (Ceschia et al., 2012; Basir et al., 2013; Bellio et al., 2016), tabu search (Aladag et al., 2009; Lü and Hao, 2010; Abdullah and Turabieh, 2012), genetic algorithms (Mirrazavi et al., 2003; Agustin-Blas, 2009; Mahiba and Durai, 2012), constraint logic programming (Deris et al., 1997; Panagiotis et al., 1998) and graph colouring (Cangalovic and Schreuder, 1991; Burke et al., 1994) have been used to formulate and solve timetabling problems. Most of these are heuristic search methods which may not produce globally optimal solutions. Hybrid algorithms combining various heuristic methods have also been proposed (Bolagi et al., 2014; Badoni et al., 2014).

    Lawrie (1969), Akkoyunlu (1973) and Tripathy (1980) were among the pioneers of using IP models to solve academic timetabling problems. They modeled the basic requirements of academic timetables such as the number of teaching sessions required per week for each course (completeness constraint) and the need for avoiding simultaneous session assignments for students and teachers (uniqueness constraint). These models were later improved and applied by many others including Dimopoulou and Miliotis (2001), Martin (2004) and Boland et al. (2006).

    Daskalaki et al. (2004) presented a comprehensive IP formulation for university timetabling including a wide range of applicable constraints such as collision, completeness, consecutive sessions, repetitive sessions, and pre-allocations. Their timetabling model was quite a general model which can be applied to a wide range of problems. Later, Schimmelpfeng and Helber (2007) reported on the application of an IP model to generate timetables for a larger scale problem with similar constraints. Ismayilova et al. (2007) applied a multi-objective IP model considering both the administration’s and instructors’ preferences to solve a faculty course scheduling problem. This model considered teacher-course assignments as well as course-time slot assignments. Bakir and Akshop (2008) also used an IP model similar to Daskalaki et al. (2004) to solve a complicated timetabling problem. They recognized the difficulties arising from the large size of the problem when applied to real-world situations and emphasized the need for reducing the number of variables. Broek et al. (2009) proposed an IP model to develop timetables by assigning students to courses based on student preference for courses and other constraints. Miranda et al. (2012) proposed a web based timetabling method (to get data online from users) which produced optimal timetables using IP. Cacchiani et al. (2013) proposed a new method to compute lower bounds for a curriculumbased course timetabling problem aiming the optimal weekly assignment of lectures to rooms and time slots. In curriculum-based timetabling, timetables are prepared before the students enroll for the courses or without knowing the details of student enrolments, based on compulsory and optional courses for each student group. Phillips et al. (2015) introduced a novel generalized patternbased IP formulation for the room assignment problem of university course timetabling. Domenech and Lusa (2015) developed an IP model to assign teachers to courses while balancing teachers’ teaching load and maximizing teachers’ preferences for courses. Vermuyten et al. (2015) presented a two-stage IP model to minimize student flows through the corridors and stairwells while satisfying other timetabling requirements.

    The IP based timetabling models proposed and used to date vary in the scope and applicability. While some timetabling models handle course-teacher assignments (for ex., Domenech ans Lusa, 2015) and/or student-course enrollments (for ex., Broek et al., 2009), others handle course-time slot and course-lecture hall assignments assuming that course-teacher and course-student assignments have been fixed (for ex., Vermuyten et al., 2015). In this paper, a timetabling problem of the latter type (i.e. post enrollment timetabling) was considered.

    The main objective of this work was to develop an economical and manageable IP model of a complicated timetabling problem in the Faculty of Applied Sciences, Wayamba University of Sri Lanka. A slightly different modeling approach was used to economize the model size and to maintain the simplicity of the model. A freely available open-source optimizer, OpenSolver, was used together with MS-Excel to code and solve the problem. The results indicate that, large scale timetabling problems can be solved more efficiently using the proposed integer programming model. The model could effectively reproduce manually prepared timetables with a significantly lower number of work hours per week. For example, the results indicate that an extremely tight faculty timetable with 51 course-work hours per week can be effectively reduced to 43 course-work hours per week without violating any applicable constraint. The model simulations were further useful in identifying the binding factors. For example, it was observed that the Faculty of Applied Science timetabling problem is bounded by the student overlaps (student uniqueness constraint), and both human and physical resource constraints are not significant. The model can be modified and applied for other university timetabling problems as well as for other scheduling problems.

    The rest of this paper is organized into three main sections. After a brief description of the case study, the proposed timetabling formulation and modeling strategies are discussed in section 2. Section 3 covers the results observed by applying the proposed model to the identified case study. Section 4 wraps up the paper with a comparison of the observed results with previous work and a discussion on possible extensions.

    1.1.Faculty of Applied Sciences–Timetabling Problem

    To formulate a timetabling problem accurately, a deep understanding of the problem domain is required together with a sound mathematical programming background. The timetabling problem in the Faculty of Applied Sciences (FAS), Wayamba University of Sri Lanka has some unique, favorable and unfavorable features compared to general timetabling problems. The faculty conducts 3-year and 4-year B. Sc. degree programs in various disciplines. Each internal student of the faculty can be identified with a combination of major subjects he or she is studying. For each combination, there are compulsory courses and optional courses. The students may have to take optional courses out of their majors to fulfill the credit requirements in each year. In a given academic year, each student is at a certain level of study which corresponds to the year of study (for example, the students who are in their first year in the university, are level I students, the students in their second year of study are level II students, and so on). Students in each of the four levels of study follow separate sets of courses, but the timetabling problem for each level is not independent owing to the common pool of resources shared: mainly lecture halls, laboratories, and teachers.

    This study was carried out during the second semester of 2014 academic year scheduled from September 2014 to January 2015. In this semester, FAS had 409 internal undergraduates at levels I, II, and III studying two major subjects from Computing & Information Systems, Electronics, Industrial Management, Mathematics & Mathematical Modelling, and Statistics. All students at levels I and II have compulsory Mathematics courses despite their majors. Level-4 students go for a 6-month industrial training during the second semester and no course work is scheduled for them during this period. The teaching staff on duty consisted of 30 permanent lecturers and 21 temporary tutors. One or more lecturers and one or more tutors are assigned for each course by the respective department, and the details of these assignments are sent to the faculty office before preparing the timetable. For each course, both the assigned lecturer (s) and tutor (s) should be made available for all teaching/learning sessions. FAS has 9 lecture halls with capacities ranging from 60-200 students, an electronic laboratory, and a computer laboratory. In addition, FAS schedules certain practical sessions in the university’s main Information Technology Center. FAS schedules no academic activity in the lunch hour from 12.30 to 1.30 pm, and therefore the consecutive sessions should be either in the morning session or in the afternoon session. Though the usual work hours are from 8.30 am to 4.30 pm, the faculty timetable runs from 7.30 am to 7.30 pm in some week days. It is extremely difficult to produce timetables without clashes, particularly for upper levels of study. Over the years, long work days have frustrated the students as well as the staff. The primary objective of this work is to generate more rational timetables with only 8 work hours per day, or if an 8-hour timetable is not feasible, to minimize the number of working hours over the week.

    2.MATERIALS AND METHODS

    In literature, university timetabling problems similar to that of FAS, have been modeled with six-dimensional binary variables, i.e., with variables xijklmn taking the value of 1, if course m, taught by teacher l to the student group k, is scheduled for the jth time period of day i in classroom n; and 0 otherwise (Daskalaki et al., 2004; Bakir and Akshop, 2008). Modern universities and faculties offer a wide variety of degree programs and courses and therefore millions of variables are required to model timetabling problems. To reduce the number of variables to a manageable level, the variables are usually redefined with relevant subsets of courses, teachers, students groups, and class rooms. In this work, instead of using subsets, a Relation Matrix was utilized to eliminate the need for some dimensions (indices) of the variables, thus reducing the total number of variables in the model.

    For the FAS timetabling problem, five dimensional variables were used by excluding the indices student group and lecturer, and including another dimension as the session type. Each course offered by FAS can have lecture and tutorial sessions, lecture and practical sessions, or just practical sessions. Therefore the type of the sessions could be lecture, tutorial, or practical. Even for the same course, the scheduling requirements of lecture sessions and practical/tutorial sessions can be different. For example, a course may require 2-hour lecture sessions in a lecture hall and 3-hour practical sessions in a laboratory. Therefore the session type index is required. In FAS, since the number of students is relatively less, one course is usually taught by one of few previously assigned lecturers for all the students simultaneously. Therefore, apart from some practical sessions, the teaching sessions are not usually repeated for different student groups. Hence there is no need to index the decision variables over student groups and teachers, instead, a Relation Matrix is used to describe the relationships between courses and student groups and courses and teachers. This approach is more economical in terms of the size of the model because when the number of indices is reduced, the number of variables is also reduced.

    Another matrix is used to indicate the hall feasibility: whether a certain course session can be conducted in a given hall depending on the course, session, number of students, hall capacity, and hall type. Since some course sessions have to be scheduled in only one pre-determined location such as a laboratory, there is no need to define variables relative to other locations. On the other hand, there were some courses which require only practical sessions. For such courses, there is no need to define variables for lecture sessions also. A VBA (Visual Basic Application) programming code was used to create the set of variables based on feasible locations and required type of sessions only. The VBA code reads the course details and hall feasibility matrix and writes the set of required variables. This method further reduces the number of variables in the model. The proposed timetabling model is presented below.

    Indices

    • c =  course: 1, 2, … , C. A course is a taught module which belongs to one of the subjects.

    • s =  session type: 1, 2, …, S. Since a course can have either tutorial or practical sessions, but not both, session types can be taken as lecture and tutorial/ practical, S = 2.

    • h =  hall: 1, 2, …, H. Both lecture halls and laboratories are considered as halls.

    • d =  day: 1, 2, …, D. Five days per week, D = 5.

    • t =  time slot: 1, 2, …, T. Eight 1-hour time slots per day, T = 8.

    • l =  lecturer/tutor: 1, 2, …, L.

    • g =  student group: 1, 2, …, G. Student groups are defined based on the combinations of major subjects. So each student group consists of the students enrolled for a unique combination of major subjects.

    Parameters

    • Ygc =  1 if at least one student of group g is registered for course c; 0 otherwise.

    • Zlc =  1 if lecturer/tutor l teaches course c; 0 otherwise.

    • Ncs =  total number of time slots required each week for session type s of course c.

    • Bcshdt =  Benefit of scheduling session s of course c for the tth time slot of day d in hall h. Benefit values can be assigned based on student and teacher preferences.

    • Rc =  number of students registered for course c.

    • Ecs =  number of consecutive time slots required for session type s of course c. This indicates the length of the sessions. The length of lecture sessions can be either 2 hours or 3 hours. The length of tutorial sessions is 1 hour, and the length of practical sessions can be 2 hours, 3 hours, or 4 hours. Usually the courses do not have sessions of the same type with different lengths. (The only exception was some 3-credit courses requiring one 2-hour lecture session and another one 1-hour lecture session followed by a 1-hour tutorial session per week. The latter was considered as another 2-hour lecture session. This has no effect on the model accuracy because both the assigned lecturer(s) and the tutor(s), and all the students should be available for both lecture and tutorial sessions of these courses).

    • Ph =  Capacity of hall h.

    Decision variables

    • xcshdt =  1 if a session s of course c is scheduled for the tth time slot of day d in hall h; 0 otherwise.

    Model(1)

    Maximize  c s h d t B cshdt -X cshdt
    (1)

    As mentioned above, the primary objective of this work was to reduce the number of work hours per week to 40, or if it is not possible, to minimise the number of work hours per week. However the model is formulated with a secondary objective which maximise the total benefit derived from the assignments. The primary objective was achieved by iteratively solving this timetabling problem over an increasing number of available time slots, starting from 40 hours per week, until a feasible solution is obtained. Once the minimum required number of work hour per week is found, the above objective function assure that those hours are utilised in such a way that maximises the benefit to the students and/or the staff.

    Subject to:

    Completeness Constraint: for each session type of each course, the required number of weekly hours should be allocated.(2)

    h d t X cshdt =N cs  for all c & s.
    (2)

    Uniqueness constraint: each student, each lecturer/ tutor and each hall can have at most one course session at a time.(3)(4)(5)

    c s h Y g c x c s h d t 1  for all  g , d & t .
    (3)

    c s h Z l c x c s h d t 1  for all  l , d & t .
    (4)

    c s χ c s h d t 1  for all  h , d & t .
    (5)

    In constraint 3, the student-course relation matrix (Ygc) is used to calculate the number of course sessions that a student group has to attend in a given time slot. Similarly, the teacher-course relation matrix (Zlc) is used in constraint 4 to avoid simultaneous session assignments for teachers.

    Consecutiveness Constraint: consecutive time slots should be assigned depending on the required length of the sessions, Ecs.

    If two consecutive time slots are required for session type s of course c (if Ecs = 2):(6)(7)(8)

    x c s h d t x c s h d ( t + 1 ) 0  for  t { 1 , 5 }  and all  h & d .
    (6)

    x c s h d t x c s h d ( t + 1 ) x c s h d ( t 1 ) 0  for  t { 2 , 3 , 6 , 7 }           and all  h & d .
    (7)

    x c s h d t x c s h d ( t 1 ) 0  for  t = { 4 , 8 } and all  h & d .
    (8)

    Constraints 6-8 have been specified based on the fact that the lunch time will occur after the 4th time slot of each day (so the consecutive sessions should be either before or after lunch). Constraint 6 specifies that, if a session s of course c which has Ecs = 2 is allocated to the 1st or 5th time slot, then the next time slot (2nd or 6th) should also be allocated to the same session. If such a session is allocated to the 4th or 8th time slot, then the previous time slot should also be allocated to the same session (constraint 8). If such a session is allocated to any other time slot, then either the previous or the next time slot should also be allocated to the same session (constraint 7).

    If three consecutive time slots are required for session type s of course c (if Ecs = 3):(9)(10)(11)(12)

    x c s h d t x c s h d ( t + 1 ) 0  and  x c s h d t x c s h d ( t + 2 ) 0       for  t = { 1 , 5 } and all  h & d .
    (9)

    x c s h d t x c s h d ( t + 1 ) 0  and  x c s h d t x c s h d ( t 1 ) x c s h d ( t + 2 ) 0       for  t = { 2 , 6 } and all  h & d .
    (10)

    x c s h d t x c s h d ( t 1 ) 0  and  x c s h d t x c s h d ( t + 1 ) x c s h d ( t 2 ) 0       for  t = { 3 , 7 } and all  h & d .
    (11)

    x c s h d t x c s h d ( t 1 ) 0  and  x c s h d t x c s h d ( t 2 ) 0       for  t = { 4 , 8 } and all  h & d .
    (12)

    For Ecs = 3, constraints 9-12 have been formulated based on the same concept discussed above. For example, constraint 9 specifies that, if a session s of course c which has Ecs = 3 is allocated to the 1st or 5th time slot, then the next two time slots should also be allocated to the same session.

    If four consecutive time slots are required for session type s of course c (if Ecs = 4):(13)(14)(15)(16)

    x c s h d t x c s h d ( t + 1 ) 0  and  x c s h d t x c s h d ( t + 2 ) 0  and x c s h d t x c s h d ( t + 3 ) 0  for  t = { 1 , 5 } and all  h & d .
    (13)

    x c s h d t x c s h d ( t + 1 ) 0  and  x c s h d t x c s h d ( t + 2 ) 0  and x c s h d t x c s h d ( t 1 ) 0  for  t = { 2 , 6 } and all  h & d .
    (14)

    x c s h d t x c s h d ( t + 1 ) 0  and  x c s h d t x c s h d ( t 1 ) 0  and x c s h d t x c s h d ( t 2 ) 0  for  t = { 3 , 7 } and all  h & d .
    (15)

    x c s h d t x c s h d ( t 1 ) 0  and  x c s h d t x c s h d ( t 2 ) 0  and x c s h d t x c s h d ( t 3 ) 0  for  t = { 4 , 8 } and all  h & d .
    (16)

    For Ecs = 4, above set of constraints (13-16) have also been formulated based on the same concept discussed previously.

    Since the courses offered by FAS usually have fixed length sessions (i.e., a course can have either 2-hour lecture sessions or 3-hour lecture sessions but not both), the consecutiveness constraint could be modeled in a simpler manner compared to previous work (Daskalaki et al., 2004) which allowed any split of weekly teaching hours as decided by the teachers. In this work, different sets of constraints were modeled based on the required length of the sessions, Ecs. Such conditional constraints can be easily modeled using looped IF functions in MS Excel.

    Pre-assignment constraints: if a session s of course c is pre-assigned for time slot t of day d in hall h, the preassignment constraint can be given as:(17)

    x c s h d t = 1.
    (17)

    Certain courses such as English Language Proficiency have to be assigned to a given time slot of a given day as they are conducted by teachers from other faculties. If required, some pre-allocations can be made to reduce the size of the problem and thus the computational burden.

    Binary constraint: all scheduling variables should be binary.(18)

    x c s h d t  binary for all  c , s , h , d & t .
    (18)

    Additional constraints

    Completeness, uniqueness, consecutiveness, and preassignments are essential constraints usually included in any timetabling model. Additionally, there are some specific constraints applicable to the FAS timetabling problem.

    For 4-credit courses which require two 2-hour lecture sessions per week, those two sessions should NOT be scheduled on the same day. Similarly some 4-credit courses require two 3-hour practical sessions per week which should not be scheduled on the same day. For such course sessions cs:(19)

    h t x c s h d t E c s  for all  d .
    (19)

    For some courses, it is usually better if the lecture session and tutorial/practical session are scheduled in different weekdays. Otherwise a public holiday can have a significant impact on some courses. For such courses c:(20)

    h t x c 1 h d t + h t x c 2 h d t Max  ( E c 1 , E c 2 )  for all  d .
    (20)

    As a norm, FAS do not schedule more than one lecture session for any lecturer in either morning or afternoon sessions. Since the lecture sessions can be two or three hours long, this requirement can be formulated as below.(21)(22)

    c h t 4 Z l c x c 1 h d t 3  for all  l  and  d .
    (21)

    c h t 5 Z l c x c 1 h d t 3  for all  l  and  d .
    (22)

    Since the lecture halls have limited capacity, the hall capacity constraint can be modeled as follows, but it is not required in this model because the variables are defined relative to feasible halls only as mentioned above.(23)

    R c x c s h d t P h  for all  c , s , h , d  &  t .
    (23)

    3.APPLICATION AND RESULTS

    The proposed model was applied to generate Level I, level-II and Level-III timetables of the second semester of 2014 academic year (Sept-Jan 2014) and compared with the timetables already prepared by the faculty office. The required data were obtained from student prospectus, existing timetables, student course registration details, and personal observations. The number of students, the number of subject combinations and the number of courses to be scheduled in this semester are summarized in Table 1. The number of subject combinations corresponds to the number of student groups to be considered (Figure 1).

    Some laboratory practical sessions had to be scheduled 2-4 times a week due to resource limitations, and in such cases, the repetitive practical sessions were considered as different courses for different sets of student groups. After this expansion, altogether there were 22 level-III courses, 21 level-II courses and 18 level-I courses in the conceptual model (Figure 2). English courses were assumed to be pre-assigned as in the current timetable. Eight 1-hour time slots starting from 8.30 am in each week day were considered initially. As mentioned above, the benefit from assignments can be based on stu- dent and teacher preferences, but in this illustration, assignments in the current timetable were considered as preferred assignments (with relatively larger values assigned for Bcshdt).

    The IP model was coded on MS Excel and solved using an open source optimization program, OpenSolver (Mason, 2011) which is a free optimizer available as an Excel add-in. The OpenSolver program has the Cbc (Coin-OR branch and cut) solver which execute a branch and cut algorithm written in C++ to solve integer programming problems. In this timetabling model, Excel serves as front-end for the solver program. Unlike the Excel’s built-in solver, OpenSolver does not have any artificial limitations on the number of variables or constraints. Standard Excel formulas such as VLOOKUP and SUMIFS were extensively used in modeling the problem.

    Initially the model was used to generate timetables for each level separately. The existing level-I timetable contained 36 course-work hours per week leaving Friday afternoon free. The model formulation for level-I contained 720 variables, and 1533 constraints. Given equal benefit values for all possible assignments, the model generated the timetable with 34 course hours, and several alternative optimal solutions were available. When a benefit value of 2 was given to current assignments against a benefit value of 1 for other possible assignments, the model generated exactly the current timetable (Figure 3). Since the level-I timetabling problem alone is simple and unbounded, it can be prepared manually. Hence in this work, the level-I timetabling problem was used just to validate the model.

    The present level-II timetable was tight with 46 course-work hours per week starting from 7.30 am in most week days and ending at 6.30 pm on some week days (Figure 4). The level-II timetabling problem was formulated with 1320 variables and 2137 constraints. Initial results indicated that the problem was infeasible with 40 work hours per week and that at least 41 work hours are required to produce a feasible timetable with no overlaps for the students. The proposed model could assign all course sessions into time slots from 8.30 am to 5.30 pm, with just one additional hour as shown in Figure 5.

    The existing level-III timetable was even compact with 51 course-work hours per week scheduled from 7.30 am to 7.30 pm most weekdays (Figure 6). The main objective was to reduce the number of work hours. Since the number of students in each group and in each course is relatively small, all lecture halls other than LR7 and MH (which are usually allocated for level-II and level-I teaching sessions respectively) were considered to enable as many as possible parallel assignments. The formulation contained 4280 variables and 6461 constraints. Again the problem was infeasible with a 40 hour week. After some relaxations, it was observed that at least 43 work hours per week are required to generate a feasible timetable. When three course sessions were pre-assigned to three additional hours, the model could assign all the remaining teaching sessions to time slots from 8.30 am to 5.30 pm (Figure 7).

    Since more than two parallel sessions are not scheduled owing to student overlaps, the level-III timetabling model was refined considering only two lecture halls, LR4 and LR8. These two halls have sufficient capacity for any level-III course. Then the model contained only 2720 variables and 3521 constraints, and it generated the same result with only the locations changed. The usefulness of a computer based optimization model was clearly visible in this case, as it reduced the number of weekly work hours from 51 to 43. This is a significant saving of eight work hour per week, which is equivalent to a saving of a whole work day.

    Finally, the proposed IP model was applied to generate the whole faculty timetable for levels I, II, and III simultaneously. The model then consisted of 61 courses requiring 180 teaching hours. All available lecture halls and laboratories were considered. When the timetabling problem was formulated separately for each level, the teacher overlap constraint was redundant because the student overlap constraint was sufficient to avoid parallel assignment of courses from the same subject stream. But for the generalized whole faculty timetabling problem, the teacher overlap constraint was required. Thus the number of constraints increased to 10,437 while the number of variables still remained economical at 6720. As expected, the model results indicated that at least 43 work hours are required to produce a feasible timetable. The generated timetable is shown in Figure 8. Again the proposed model could reduce a tight 7.30 am to 7.30 pm timetable to 7.30/8.30 am to 5.30 pm enabling the students to attend sports practice and other extra-curricular activities after 5.30 in all week days and before 8.30 in some weekdays. Overtime payments are also minimized.

    The outcomes of the optimization indicate that student overlap is the binding factor in FAS timetabling, and both hall availability and teacher overlaps are not significant. In any time slot, only a maximum of five course sessions are scheduled in parallel leaving the majority of lecture halls and laboratories unoccupied. Owing to student overlaps, only a maximum of one course from one subject stream and one level of study can be scheduled in any time slot (for example, two level-II CMIS courses cannot be scheduled in parallel). The timetables for levels I, II, and III can be solved separately to reduce the model size thereby simplifying the models and increasing the speed of solving, but some manual adjustments are required to eliminate possible teacher overlaps. However, when level-IV courses are also included (particularly in semester 1), about 80 courses will have to be scheduled and then the hall and teacher overlaps can have a significant impact on scheduling. When the practical sessions are divided into several student groups, the grouping criteria have an impact on scheduling. The model can be further developed to find the optimal way of grouping (for practical sessions) so as to minimize scheduling conflicts.

    The calculation time varied from few seconds to half an hour depending on the size of the problem, however if SolverStudio, which is the successor of OpenSolver, was used instead, even the largest model could have been solved faster. SolverStudio is also a free Excel add-in which provides access to other modeling tools such as AMPL and PuLP.

    4.DISCUSSION AND CONCLUSIONS

    An IP model has been proposed for a case study of university timetabling. The model generated timetables appears to be more efficient and compact compared to existing timetables. The model was useful to identify factors which bind the timetabling problem and possible simplifications. For example, it was observed that student overlaps occurring from the presence of several optional courses (i.e., the students can take optional courses from non-major subject areas) have complicated the timetabling process and that the resource constraints (lecture halls and laboratories) were redundant.

    The statistics of the timetabling problems and associated IP models discussed above are summarized in Table 2. To evaluate the efficiency of the proposed modeling approach, the problem sizes and model sizes were compared with those of a relatively similar case study reported in Daskalaki et al. (2004). The whole faculty timetabling problem discussed in this work is comparable to Problem 2 of Daskalaki et al. in terms of both the number courses and the number of teaching hours required. Still, the number of variables and constraints used to model the whole faculty timetabling problem are respectively a half of the number of variables and eighty percent of the number of constraints used to model Problem 2 of Dalskalaki et al. (2004).

    While the model size (relative to the problem size) provides a good indication of modeling efficiency, computational time is the key factor which determines the efficiency of the solution algorithm. The above optimal solutions have been obtained using the Cbc solver algo- rithm (in OpenSolver), and a new solution algorithm has not been developed so far to solve the FAS timetabling problem. Hence, the computational time (obtained with an available algorithm) was not compared with that of other proposed solution algorithms for timetabling problems. This paper focuses on modeling and solving the problems using an available solver algorithm. The next stage of this study is to use SolverStudio which has more advanced solver algorithms. A new customized solution algorithms will be required only if the available algorithms appears to be inefficient.

    Some specific features of the FAS timetabling problems (for ex., fixed-length lecture sessions) have played a favorable role in reducing the model size, and therefore the modeling efficiency also cannot be guaranteed in all other situations. Still, the use of a relation matrix may be more appropriate in modeling other timetabling problems and can be tested with standards datasets.

    The primary focus of the work was to develop a manageable IP model of a complicated university timetabling problem. Owing to the presence of students studying a wide variety of subject combinations, generating a feasible timetable was the main challenge faced. Therefore, the student and teacher preferences were not considered in applying the models. However, the preferences and even other objective criteria such as the work load distribution over the week and utilization of resources can be considered as the objective criteria in the optimization model.

    In general, the results generated from the model show that such computerized timetabling models can produce more efficient timetables meeting complicated requirements. The tools used, namely MS Excel and Open- Solver were very productive for modeling and solving such problems. The programming capability of MS Excel with VBA enabled automated generation of customized sets of variables based on specified requirements. Standard Excel formulas were particularly useful in modeling different sets of constraints for different parameter values. Since MS Excel serves as a user-friendly and familiar interface, once the IP model is developed, no expert knowledge is required to use the model to generate timetables for different scenarios. The IP model can be further adopted to incorporate other requirements and to apply for similar scheduling problems.

    Figure

    IEMS-16-141_F1.gif

    Student-course matrix for level III and level II.

    IEMS-16-141_F2.gif

    Extended student-course matrix for level III.

    IEMS-16-141_F3.gif

    Timetable for Level I. Session type and group are in brackets (L-lecture, T-tutorial, P-practical). The venue is in bold. All CMIS practical sessions are conducted in the CMIS lab and all ELTN practical sessions are conducted in the ELTN lab.

    IEMS-16-141_F4.gif

    Current level-II timetable.

    IEMS-16-141_F5.gif

    Proposed level-II timetable.

    IEMS-16-141_F6.gif

    Current level-III timetable.

    IEMS-16-141_F7.gif

    Proposed level-III timetable.

    IEMS-16-141_F8.gif

    Proposed whole faculty timetable.

    Table

    Summary of data relevant to second semester timetabling in FAS

    Comparison of problem sizes and model sizes

    REFERENCES

    1. Abdullah S , Turabieh H (2012) On the use of multi neighbourhood structures within a tabu-based memetic approach to university timetabling problems , Inform, Sciences, Vol.191 ; pp.146-168
    2. Agustín-Blas L E , Salcedo-Sanz S , Ortiz-García E G , Portilla-Figueras A , Pérez-Bellido A M (2009) Hybrid grouping genetic algorithm for assigning students to preferred laboratory groups , Expert System Applications, Vol.36 (3) ; pp.7234-7241
    3. Akkoyunlu E A (1973) A linear algorithm for computing the optimum university timetable , The Computer Journal, Vol.16 (4) ; pp.347-350
    4. Aladag A H , Hocaoglu G , Basaran M A (2009) The effect of neighbourhood structures on tabusearch algorithm in solving course timetabling problem , Expert System Applications, Vol.36 (10) ; pp.12349-12356
    5. Badoni R P , Gupta D K , Mishra P (2014) A new hybrid algorithm for university course timetabling problem using events based on groupings of students , Computers & Industrial Engineering, Vol.78 ; pp.12-25
    6. Bakir M A , Akshop C (2008) A 0?1 integer programming approach to a university timetabling problem , Hacettepe Journal of Mathematics and Statistics, Vol.37 (1) ; pp.41-55
    7. Basir N , Ismail W , Norwawi N (2013) A simulated annealing for Tahmidi course timetabling , Procedia Technology, Vol.11 ; pp.437-445
    8. Bellio R , Ceschia S , Gaspero L D , Schaerf A , Urli T (2016) Feature-based tuning of simulated annealing applied to the curriculum-based coursetimetabling problem , Computers & Operation Research, Vol.65 ; pp.83-92
    9. Bolaji A L , Khader A T , Al-Betar M A , Awadallah M A (2014) University course timetabling using hybridized artificial bee colony with hill climbing optimizer , Journal of Computational Science, Vol.5 (5) ; pp.809-818
    10. Boland N , Hughes B D , Merlot L T G , Stuckey P J (2006) New integer linear programming approaches for course timetabling , Computers & Operation Research, Vol.35 (7) ; pp.2209-2233
    11. Broek J V D , Hurkens C , Woeginger G (2009) Timetabling problems at the TU Eindhoven , European Journal of Operational Research, Vol.196 (3) ; pp.877-885
    12. Burke E K , Elliman D G , Weare R F (1994) A university timetabling system based on Graph colouring and constraint manipulation , Journal of Research on Computing in Education, Vol.27 ; pp.1-18
    13. Cacchiani V , Caprara A , Roberti R , Toth P (2013) A new lower bound for curriculum-based course timetabling , Computers & Operation Research, Vol.40 (10) ; pp.2466- 2477
    14. Cangalovic M , Schreuder J A M (1991) Exact coloring algorithms for weighted graphs applied to timetabling problems with lectures of different lengths , European Journal of Operational Research, Vol.51 (2) ; pp.248-258
    15. Ceschia S , Gaspero L D , Schaerf A (2012) Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem , Computers & Operation Research, Vol.39 (7) ; pp.1615-1624
    16. Daskalaki S , Birbas T , Housos E (2004) An IP formulation for a case study in university timetabling , European Journal of Operational Research, Vol.153 (1) ; pp.117-135
    17. Deris S B , Omatu S , Ohta H , Samat P A B D (1997) University timetabling by Constraint based reasoning: A case study , Journal of the OperationalResearch Society, Vol.48 (12) ; pp.1178-1190
    18. Dimopoulou M , Miliotis P (2001) Implementation of a university course and examination timetabling system , European Journal of Operational Research, Vol.130 (1) ; pp.202-213
    19. Domenech B , Lusa A (2015) A MILP model for the teacher assignment problem considering teachers' preferences , European Journal of Operational Research, Vol.249 (3) ; pp.1153-1160
    20. Hochbaum D S (1997) Approximation algorithms for NP-hard problems, PWS Publishing Company,
    21. Ismayilova A A , Sağir M , Gasimov R N (2007) A multiobjective faculty-course-time slot assignment problem with preferences , Mathematical and Computer Modelling, Vol.46 (7-8) ; pp.1017-1029
    22. Lawrie N L (1969) An integer linear programming model of a school timetabling problem , The Computer Journal, Vol.12 ; pp.307-316
    23. Lü Z , Hao J K (2010) Adaptive tabu search for course timetabling , European Journal of Operational Research, Vol.200 (1) ; pp.235-244
    24. Mahiba A A , Durai C A D (2012) Genetic Algorithm with Search Bank Strategies for University Course Timetabling Problem , Procedia Engineering, Vol.38 ; pp.253-263
    25. Martin C H (2004) Ohio University's college of business uses integer programming to schedule classes , Interfaces, Vol.34 ; pp.460-465
    26. Klatte D , Luthi HJ , Schmedders K , Mason A J (2011) OpenSolver - An open source add-in to solve linear and integer programmes in Excel , Operations Research Proceedings Springer Berlin Heidelberg, ; pp.401-406
    27. Miranda J , Rey P A , Robles J M (2012) UdpSkeduler: A web architecture based decision support system for course and classroom scheduling , Decision Support Systems, Vol.52 (2) ; pp.505-513
    28. Mirrazavi S K , Mardle S J , Tamiz M (2003) A two-phase multiple objective approach to university timetabling utilizing optimization and evolutionary solution methodologies , Journal of the Operational Research Society, Vol.54 (11) ; pp.1155-1166
    29. Panagiotis S , Vigla E , Karaboyas F (1998) Nearly optimum timetable construction through CLP and intelligent search , International Journal of Artificial Intelligence Tools, Vol.7 (4) ; pp.415-442
    30. Phillips A E , Waterer H , Ehrgott M , Ryan D M (2015) Integer programming methods for largescale practical classroom assignment problems , Computers & Operations Research, Vol.53 ; pp.42-53
    31. Schimmelpfeng K , Helber S (2007) Application of a real-world university-course timetabling model solved by integer programming , OR Spectrum, Vol.29 (4) ; pp.783-803
    32. Tripathy A (1980) A Lagrangian relaxation approach to course timetabling , Journal of the Operational Research Society, Vol.31 (7) ; pp.599-603
    33. Vermuyten H , Lemmens S , Marques I , Belien J (2015) Developing compact course timetables withoptimized student flows , European Journal of Operational Research, Vol.251 (2) ; pp.651-661