Abstract
Examination timetabling is an inevitable problem of educational institutions. Each institution has its own 3 particular limitations, however, the main structure is same: assigning exams to time slots and classrooms. Several 4 institutions solve the problem manually, but it becomes more difficult every year with increasing number of students 5 and limited resources. There are many studies in the literature addressing Examination Timetabling Problem (ETP) 6 and provide high quality solutions within reasonable amount of time. Nevertheless, almost none of them can be used 7 in practice since they are not converted into a decision support system (DSS). Commercial DSS's, on the other hand, 8 are generally transactional based and do not have optimization capabilities, i.e., they prevent conflicts via functional 9 user interfaces. In this study, we propose a mixed integer programming (MIP) model that addresses the ETP of the 10 Industrial Engineering Department of Yıldız Technical University. The model, which is capable of solving a wide range 11 of similar ETP instances, is embedded into a DSS in the form of a spreadsheet. Given the enrolment lists of the courses, 12 it generates schedules with minimum conflicts and consecutive exams while addressing requests of the lecturers and 13 students. It does not require any technical knowledge and can be used by an average spreadsheet user. Moreover, it's 14 flexible in terms of using for scheduling problems of other educational institutions. Currently, the DSS is in use by the 15 department and real life instances can be solved within a few seconds saving significant amount of man-hours.
Abstract
16

(an MIP), (ii) embed the model into a DSS, and (iii) use a commercial solver to solve the model. Therefore, 1 we focus on the studies that model ETP with mathematical models and/or develop DSS for ETP or similar 2 problems like course timetabling problem (CTP). 3 International Timetabling Competition provides a very general instance for ETP. McCollum et.al. [5] 4 developed an integer programming (IP) model that addresses the ETP of the competition. This model is 5 improved by preprocessing stages in study of Arbaoui et.al. [6] . The preprocessing stages reveal general conflict 6 constraints. With the improved model, the number of hard and soft constraint were reduced. Gogos et.al. [7] 7 used greedy randomized adaptive search procedure that involves several optimization algorithms together with 8 an IP model. 9 The above papers provide solution methods for the same ETP instance. There are also several studies 10 that address institution-specific problems. Al-Yakoob et.al. [8] proposed two MIP models to solve ETP and TA 11 assignment problems of Kuwait University. They developed heuristic approach to reduce dissatisfaction levels of 12 the TAs for during their assignment problem. Cavdur and Kose [9] proposed a fuzzy logic model which generates 13 parameters of a MIP that solves ETP of Uludag University IE department. TA assignment was fulfilled using 14 a greedy heuristic. Komijan and Koupaei [10] developed a binary model to solve postgraduate students' exam 15 schedules of the IE department at Islamic Azad University. 16 ETP instances of these studies were solvable within reasonable time limits using commercial solvers. On 17 the other hand, some problems required extra effort to be solved, i.e., the solvers or CPU power were not 18 sufficient to solve them. Hence authors came up with several solution techniques. Dimopoulou and Miliotis [11] 19 is an early attempt to solve a real life instance. They provided an IP model for ETP of Athens University of 20 Economics and Business and solve it using a heuristic solution which generates an initial feasible solution first 21 and then improves the solution by relaxing some constraint. Qu and Burke [12] showed that problems can be 22 decomposed into an easy set and a hard set of problems. They stated that the basic idea of decomposition is 23 to "divide and conquer", as optimal solutions of smaller sub-problems may be much easier to obtain by using 24 relatively simple approaches or even exact methods. They showed that although the difficult set is small in size, 25 it makes a major contribution towards the total cost of the constructed solution. Later Qu et.al.

[13] used IP 26 models to solve the hard sub problems of the ETP and introduced new cutting planes to have better solutions.
27
In addition to these studies, Tilahun [14] created a heuristic approach to solve ETP. He used a discrete version 28 of the the prey-predator algorithm and set up a simulation for test. hundreds of exams to schedule over such a short time period that there is simply no feasible solution. Hence 32 they allowed multiple sessions of the same exams and the aim was to minimize the number of duplicate exams.
33
They had a two stage solution method. In the first stage a good initial solution was developed using a greedy 34 approach. This solution was improved in the second stage using MIP models. Pamukkale University. Both studies developed a two stage method where the first stage assigns time slots to 38 the courses and the second stage assigns classrooms.
39
Only a few of the studies cited above were successful to develop a DSS to solve real life instances. The number of DSS studies related with ETP is limited. Hence we also consider DSS studies proposed 3 for other educational scheduling problems. In fact, DSS studies regarding CTP constitutes the majority of the 4 DSS studies in education. Piechowiak and Kolski [18] formed a constraint programming for CTP and they 5 implemented by using multi-agent approaches to create DSS. Miranda [19] created a computer system, whose 6 name is "eClasSkeduler", by using IP for CTP. The author applied this system at the Universidad de Chile. Their DSS, which they create using an IP, consists of three stages: the faculty-course assignment stage, the 10 courses-time slot assignment stage, and time slot-room assignment stage.
11
We noticed two very recent studies that provides DSS for educational purposes. Bailey and Michaels
12
[22] provides a spreadsheet based DSS for assigning students to teachers in primary schools and middle high They provide a web based DSS and implement it at a Middle Eastern University. Table 1 shows ETP and CTP 17 studies using the mathematical programming methods and/or proposing DSS. In this section, we present the current structure of the department and define the problem. YTU-IE offers 32 two programs at the undergraduate level: Turkish (or 30% English) program and English (or 100% English) 33 program. The students enrolled to the Turkish program has to complete 30% of their credit load with English 34 courses. Hence, the students in Turkish programs can attend the courses offered in English as well. The courses 35 are offered in two semesters: fall and spring. In 2018, there was an update in the curriculum of the department.
36
As a result, some new courses are added to the curriculum and semesters of some courses are switched. For 37 example, operation research 1 (OR1) was offered as a second year class in the old curriculum and is offered as week lasts one week, final week can last more than a week. Therefore it's not always possible to use a 4 timetable of midterm week for the final exams. Please note that the department can use only a few days 5 since remaining days are allocated to service courses like mathematics, physics, etc.
6
• Days are divided into six equal time slots that lasts ninety-minutes.
7
• The undergraduate program can use five classrooms for examination. Moreover, graduate courses continue 8 in the midterm week as well, hence the number of available classrooms is generally smaller than five.
9
• Instructor may have more than one course and they may ask to have their examination at the same time.
10
Instructors also may choose specific days or slots for exams.
11
• If there are significant number of students enrolled in any two courses, then (i) their exams must be on campus. Hence, no exams are planned on the examination days of service courses.
19
• Students may not have more than three exams in a day.
20
• Exams last a single slot.
21
Currently, it is almost impossible to create examination schedules manually that addresses the rules 22 above, due to increasing number of students, the change in the curriculum and the decrease in the number of 23 TAs. and variables of the MIP model are given in Table 2 and Table 3 respectively.
27
We first propose our MIP model below and then explain the constraints and the objective function.
27
Subject to 28 d∈D t∈T
27
Number of students enrolled in course i I 2 (n)
27
Course tuples of size two that has at least n students in common I 3 (n)
27
Course tuples of size three that has at least n students in common I 4 (n)
27
Course tuples of size four that has at least n students in common I 
27
possible to spare time for grading the exams. Therefore the model schedules the classes (especially the crowded 1 ones) as early as possible. Second, there is a significant decrease in the success of the students in late exams.
2
Third, it minimizes the number of assigned classrooms which also corresponds to minimizing the number of TAs 3 in charge. The first part in the objective function deals with early finishes and last slots through the coefficients 4 e 1 idt . The second part handles the number of classrooms. 5 
DSS implementation 6
In this section, we first describe our DSS and then we illustrate the implementation with the timetables of 7 spring and fall semesters of 2018-2019 for YTU-IE.
DSS implementation 6
8
DSS implementation 6
The aim of this study is to create a DSS that enables to prepare timetables addressing the rules of 9 the department, the requests of instructors and the needs of the students. We used MS Excel and its add-in 10 Solver Studio to develop the DSS. Solver Studio contains an interpreter which allows coding with using different 11 programming languages. We used Python for coding and Gurobi 5 for solving the proposed MIP model.
DSS implementation 6
12 Figure 1 .
Structure of DSS
The structure of the DSS, which consists of three parts, is given in Figure 1 . The first part is the system 13 input. Types of input data is given in Table 4 . These tables are created by using data items editor of the Solver In the spring semester of 2018-2019, I 2 (s 2 = 1) has 758, I 3 (s 3 = 1) has 3228 and I 4 (d 4 = 1) has 5033 1 elements. Number of common students for these lists are given in Figure 3 . Each slice in the pie charts gives the 2 number of tuples created according to the number of common students. In Figure 3 (a), for example, there are 3 107 pairs who have 1 common student and 338 pairs which have 6 or more common students. It can be observed 4 that using the set with c 2 = 2 rather than c 2 = 1 , removes 107 constraints from the problem. Similarly using 5 d 4 = 2 rather than d 4 = 1 removes 3659 constraints.Like Figure 3 The instances were run on an Intel R Core TM i5-3470 CPU computer with 4 GB RAM. We have prepared 8 the midterm and the final for fall and spring semesters of 2018-2019. We set the optimality gap to 10% which 9 is found to work well during experiments. Computational results of spring term examination timetables are 10 given in Table 5 . Since final program has more issues to be addressed, the number of constraints and variables 11 is more in the final program. It took less than 20 seconds to create the exam schedules for both semesters using 12 the DSS. We announced the resulting timetables on the department web site and received feedback from both 13 students and academics to revise our model and DSS. One motivation of this study is increasing number of complaints from students due to conflicts, i.e., 15 having simultaneous exams. Note that we handled this issue with constraints (7) and (12) through the sets 16 I 2 (.) and I 3 (.) Table 6 shows comparison of conflicts in midterm exam schedules prepared manually and by DSS 17 for spring midterm. Exam indicates that number of exam in one term and conflicts shows number of students 18 that have conflicts in their exams. In YTU, students must have a legal excuse (medical report, conflict, etc.) to 19 take a make-up exam for the midterm. On the other hand no excuse is required to take the re-sit exam (i.e., the 20 make-up exam for the final). Therefore the number of students with conflicts is recorded only for midterms (by 21 the department secretariat). It can be observed that the number of students with conflicts reduced although the 22 number of examinations increased. In order to have a normalized measure, we divided the number of students 23 with conflict to the number of exams. This ratio shows the number of students that has a conflict per exams.
24
The DSS reduced the ratio by 22%. The sets I 2 (.) , I 3 (.) and I 4 (.) are characterized by the parameters s 2 , c 2 , s 3 , c 3 , and d 4 . These 1 parameters affect the feasibility and quality of the solution through the sets. We illustrate their effect throughout 2 the final timetable of 2018 Fall. Generally the final week lasts two weeks (or 10 days). This period includes 3 service course examinations (3.5 days) and presentations of graduation thesis of the fourth year's students (2 4 days). Therefore 4.5 days are left in two weeks for YTU-IE to allocate the finals of the department. In order 5 to see the timetables for different lengths of periods, we tried some combinations of different days and slot. For 6 each day-slot combination, we tuned the parameters s 2 , c 2 , s 3 , c 3 , and d 4 to find a feasible solution. We 7 prepared the schedules for 3, 4 and 4.5 days with 5, 6 and 7 slots. These parameters and comparative results 8 of these combinations are given in Table 7 . Slot 6 brucemullins@example.net and slot 7 brucemullins@example.net, hence we tried to 9 avoid allocating exams to these last two slots due to its negative effect on the overall success of the students.
25

10
Moreover the academic staff asks to finish the exams as early as possible to finish grading in a timely manner.
11
We report (i) the number of exams on consecutive days ( 1 st day, 2 nd day, etc.), (ii) the number of students 12 taking exams in the first and second week, (iii) the number of exams and students in the last slots, i.e., in slots 13 6 and 7 . We do not report solution time since all examination timetables are obtained in a minute. We don't 14
11
give the number of classes assigned to exams since they are almost the same in every instance. It turns out 15 that the number of exams are distributed evenly except the 3-day schedules where the last day has significantly 16 less number of exams. Since there are many students taking exams in slots 6 and 7, three day exam schedules 17 with 6 and 7 slots and a four day schedule with 6 slots turn out to be dominated by other combinations. For 18 the scenarios with 5 lost, number of students with conflicting exams are quite high for the exam timetables 19 with 3 days and 4 days. Therefore, these cases has been eliminated since the number of students whose exams 20 overlapping is high. Although the parameter brucemullins@example.net day exam is not as high as 3 days and 4 days, the 21 number of students in the first week is smaller than 6 and 7 slots. Thus, 4.5 days exam with 5 slot is dominated.
11
For the remaining cases, number of students at slots 6 and 7 are very close to each other. Moreover, students,
23
TAs and instructors do not want to have 7 slots unless it has to exist to maintain feasibility. The number of 24 students taking exam in the first week turns out to be larger in the eighth combination (4.5 days with 6 slots).
25
Note that this is possible since the values of the parameters change in each setting (Table 7) . Using the results 26 in Table 7 and following the confirmation of the department management, a 4.5 days schedule with 6 slots was 27 announced as the final schedule. The final schedule is printed in the output tab of the spreadsheet and it can 28 be directly saved as a PDF file to announce on the web. 29 6. Conclusion and future work 30 We proposed a DSS to solve the ETP of YTU-IE. We addressed the ETP with a MIP model and embedded the 31 MIP in the core of the DSS which is in the form on MS Excel sheet. Given the enrolment lists of the courses, 32 the DSS is able to generate examination timetables in a few seconds. The DSS does not require any coding or 33 optimization expertise and can be used by an average MS Excel user by fulfilling the requests and requirements 34 of the department, instructors and students. The DSS is able to prepare examination timetables with a reduced 35 exam intensity in a day. Moreover, a balanced program can be created by providing the best way to ensure that 36 students do not have an exam at the same time, no any two consecutive exams, and no more than three exams 37 Week 2 Exam Student 1 3 5 11 10 10 10 10 20 16 12 --2888 -315.362.6142 18 12 --2888 -10 652 3 3 7 4 2 2 2 2 16 20 12 --2888 -11 615 4 4 5 4 3 3 3 3 13 15 9 11 -2165 723 --5 4 6 1 3 1 3 2 12 13 12 11 -2168 720 9 635 6 4 7 1 2 1 2 2 11 14 11 12 -2092 796 11 538 7 4,5 5 2 3 3 2 2 12 12 11 9 4 2081 807 --8 4,5 6 1 3 1 3 2 11 12 8 12 5 2163 725 8 546 9 4,5 7 1 2 1 2 2 12 12 9 12 3 2024 864 7 515 in a day. Since all the required information is defined in DSS, a system-oriented structure has been created by

{'paper_id': '209179044', 'title': 'A Spreadsheet Based Decision Support System for Examination Timetabling', 's2_url': 'https://api.semanticscholar.org/CorpusID:209179044', 'source': 'S2ORC'}