An Overview of the Heuristic Approaches for University Course Timetabling System

An Overview of the Heuristic Approaches for University Course Timetabling System

Vasugi Mudaliar. R. K Department of Computer Science, Christ University

Bangalore-29, Karnataka, India

Rohini

Department of Computer Science, Christ University

Bangalore-29, Karnataka, India

Manoj Kumar Mishra Department of Computer Science, Christ University

Bangalore-29, Karnataka, India

Abstract Course Timetabling is a complex constraint satisfaction problem that consists of scheduling the students and faculty using the resources available in the University to satisfy various constraints. An enormous group has proposed their disparate views in the literature depending on the type of university, resources available, hard and soft constraints. This problem addresses various constraints based on the resources available in the institution and analyses various implementation of case based reasoning and artificial intelligence techniques with hyper-heuristic methods to discover the knowledge of the timetabling problem methods and algorithms to arrive at the solution. In this paper, comparison of this problem and the formulations of constraints and algorithms are done with different solutions.

Keywords Heuristics; Timetabling; Constraints; Case- based reasoning (CBR); Artificial Intelligence;

1. INTRODUCTION

   Timetabling is a list of scheduled events arranged according to the predefined time slots. It is an NP hard problem which includes events like teachers, students, courses and resources which incorporate the facilities like equipments and rooms required for theoretical and practical courses. Time slots are divided into weekly and daily as it varies from each institution. Several unsatisfactory issues were confronted when timetable was done manually. This led to the invention of automated solution for course timetabling using different approaches and optimization techniques.

   Course Timetabling is a real time complex problem that any educational institution has been facing regularly. It generally satisfies a set of common constraints in todays curriculum.

   Constraints are a set of restrictions for scheduling the events. This problem is tackled by assigning a set of rooms to a set of courses and timeslots based on a set of constraints.

   There are two types of constraints followed while framing the timetable. They are hard constraint and soft constraint. Hard constraints are constraints that are satisfied compulsorily and not violated. For example, one teacher cannot attend two classes at the same time. Soft constraints are constraints that are desirable and define how good a given feasible solution is and not necessary to minimise violations. For example, a teacher can request a special classroom for a given course.

   Course timetabling makes a significant contribution in any educational institution by managing hard and soft constraints. Many researchers have addressed the timetabling

   problems using Case-based reasoning, Memetic Algorithms, Hybrid Genetic Algorithms, Meta-heuristic approach, Hyper- heuristic approach and Combination based solution approach. College course timetabling allows us to schedule lectures per week without any overlap, for all the resources and courses available in the institution.

   This paper is organized as follows: Section II depicts the architecture of university timetable system. Section III describes the problem with related research work that compares different approaches and techniques. Section IV relates artificial intelligence with the problem. Section V discusses about experimental analysis. Conclusion and future work has been presented in last section.

2. SYSTEM ARCHITECTURE

   Figure 1 depicts university timetable scheduling using particle swarm optimization.

   Figure 1: Architecture of University Timetable System

   The Timetable class represents the database in the form of objects as in Figure 2. A hierarchy of slot selection rules that the university offers is shown in the Figure 3. Figure 4 depicts dependent variables like faculty, subjects, and classrooms entities.

3. RELATED WORKS

   Timetable organizer helps student in planning their own timetable based on the courses they wish to enrol by providing best possible combinations for that particular semester in an accurate manner [1]. Burke et al. [2] provides an overview of University timetabling that concentrates on meta-heuristic, multi-criteria, case-based reasoning, hyper- heuristic and self-adaptive approaches. The objective is to create better real-world timetabling systems with the usage of parameters, multi-criteria approaches and general. It is not dependent upon problem specific information and represents an approach which is more flexible to solve more complex problems with an optimal solution. Case-based reasoning is a knowledge based paradigm where new problems are solved

   by using previous experience or knowledge. CBR discovers and represents the knowledge that allows finding most similar source cases that give good predictions of the best heuristics [3]. Figure 5 shows the process of measuring and solving the problem using case-base and Figure 6 represents courses as attributes in form of graph. Multiple-retrieval CBR is an effective initialisation method for local search methods such as Hill Climbing, Tabu search and Simulated Annealing [4]. Figure 7 explains the flow of data in multiple CBR system.

   Figure 5: A Case-based reasoning framework.

   Figure 6: A course timetabling problem represented by the attribute graph.

   Figure 7: Schematic diagram of the multiple- retrieval CBR System.

   A single-stage simulated annealing (SA) design method is robust and effective to solve the problem and applies statistical methodology to fine tune the parameters [5]. Tabu search (TS) speeds up the solution finding process based on the given set of operating parameters for timetable construction using evolutionary approach [6]. Simulated annealing depends on a cooling schedule; Tabu search requires an appropriate length of Tabu list.

   Schaerf et al. [7] suggests that course timetabling is NP- complete problem that provides an accurate solution for small cases and generate better optimal solutions and tunes the length of a chromosome [7] and provides a more flexible and effective timetable that fits into complex problem space [8]. Genetic algorithms (GA) have multi-directional search property which enables us to solve the problem using three hybrid genetic algorithms: fuzzy genetic algorithm randomized iterative search (FGARI), fuzzy genetic algorithm simulated annealing (FGASA) and fuzzy genetic algorithm tabu search (FGATS) that are proposed in [9].

   Anirudha Nanda et al. [10] apply a heuristic algorithm that tries to find a good approximate solution for the following search methods (Tabu Search, Simulated Annealing, Scatter search and Genetic algorithms). Recent heuristics and evolutionary timetabling algorithms like memetic and genetic algorithms help to explore neighbourhood solutions. [11]. In novel greedy heuristic algorithm the runtime is significantly reduced as the constraints are modelled based on the objective function for all curriculums of a student and transforms heuristics using relational calculus [12].It provides a general solution when there are issues regarding clashes of lectures and subject pertaining to teachers.

   A heuristic approach which doesnt violate hard constraints leads to a good set of solutions. The evolutionary squeaky wheel optimization technique follows a cycle of Analysis, Selection, Mutation, Prioritization and construction and eds when the stop condition is reached [13].

   Distributed algorithms are widely used to provide agents for better resource allocation and find good solution for this problem. Agent technology is an important domain of research and helps us in gathering knowledge about the application in domain and to enhance profiles of users in artificial intelligence [14]. Distributed architecture focuses on methods based on multi-agent system approach that increases the ability of scheduling each department and prevent collision among the resources [15]. Rohit Pradip Soni et al.

   1. discusses about object-oriented expert system that computes probability of various data sources and converts into object-oriented database approach.

      Fuzzy methods are employed to satisfy different soft constraints and three different heuristic orderings like largest degree, saturation degree, and largest enrolment. This method measures the problem similarity in case-based reasoning and maintains the feasibility of the timetable. Rescheduling and unscheduling events are performed until all events are scheduled. Fuzzy multiple heuristic orderings approach

      produces good quality solutions with low requirement for rescheduling. Fuzzy multiple heuristic approach can be applied to a wider range of timetabling and scheduling problems by adding more combination of heuristic orderings and applying simple optimization algorithm [17].

      A two stage process class-course-faculty model increases the performance of the department and the rules are framed based on the availability of the resources and courses. The two stage approach comprises of Stage I processing class-course scheduling system and Stage II by class- faculty assigning system. The inputs are taken by the class-course scheduling and faculty scheduling process with the two fitness function through heuristic driven process to generate the required outputs [18].

      Particle swarm optimization (PSO) is an evolutionary technique where two different types of hybrid PSO called Local search and constraint-based reasoning are used and PSO constraint-based reasoning gives a near-optimal solution [19]. An initial solution is constructed using appropriate heuristic and certain parameters then the improvement is carried out using meta-heuristics. Meta- heuristics are higher level procedures used to find, generate, partial search algorithm.

      Multi-objective Pareto optimization finds set of non- dominated solutions that represent the desired trade-off surface. Hyper-heuristics are mainly used to raise the level of generality at which most current met-heuristic systems work. The heuristic that is best suitable for optimization during the search is investigated and result is obtained in multi-objective hyper-heuristic approaches [20]. Iterated local search combines both add and delete operations which gives an effective hyper heuristic approach [21].

      Rule based heuristics helps to build a constrained timetable using knowledge-based system. The knowledge is determined as a set of rules using an expert system shell called CLIPS [22]. Multi-phase rule based expert system called Graduate Course Advisor (GCA) is simulated to retrieve information about students academic history and interests to schedule the course the students prefer. The GCA uses a rule interpreter which has 400 rules in the rule bases to evaluate and schedule the courses [23].

      An optimised student flow helps in finding good quality feasible solutions by adapting the two-stage integer programming approach [24]. A mathematical model was built that enables identification of best timetable that meets the specific needs of lecturers in an organization [25].

4. ON THE ROLE OF AI

   Artificial Intelligence (AI) is an active area where timetabling has developed a variety of approaches for solving problems like sequential methods, cluster methods, constraint based approaches and meta-heuristics methods. This approach integrates expert systems and constraint programming to implement the problem.

   Parameter	Value
   Crossover Probability	0.8
   Mutation Probability	0.5
   Population size	100
   Tabu list size	9
   Neighbourhood structures list size in FGARI and FGASA	9
   Neighbourhood structures list size in FGATS	3
   1 parameter in FGATS	3
   Maximum number of generation	3000
   Maximum number of iteration in local search algorithm	3 times the number of courses
   Average number of courses	200

   Parameter	Value
   Crossover Probability	0.8
   Mutation Probability	0.5
   Population size	100
   Tabu list size	9
   Neighbourhood structures list size in FGARI and FGASA	9
   Neighbourhood structures list size in FGATS	3
   1 parameter in FGATS	3
   Maximum number of generation	3000
   Maximum number of iteration in local search algorithm	3 times the number of courses
   Average number of courses	200

   Expert systems are utilized to incorporate knowledge into the timetabling system and provide reasoning capability for knowledge deduction. The separation of the knowledge base, facts and the inference engine in expert systems provides greater flexibility to support changes. The constraint hierarchy is utilized to capture hard and soft constraints and to reason about constraints using constraint satisfaction and relaxation techniques. Heuristic research is going on, where some more rules can be added in order to find algorithms that are robust.

5. EXPERIMENTAL ANALYSIS

Fitness

Fitness

Petrovic et al. analyses different set of experiments that were conducted with different number of features to display the average performance using Tabu search and Hill Climbing. Figure 8 shows that Tabu search performs better than Hill climbing [3]. Two case bases with different number of source cases are built thereby refining the size of the database with 90 source cases. The second case bases are trained more that leads to a table with better performance in CBR [3]. CBR stage process increases the system performance by examining before and after second stage process as shown in Table 1.

Figure 8: System performance by Tabu search and Hill climbing on different features.

Table 1: ystem performance before and after the second stage process on CBR.

Table 2: Dataset properties

Table 3: Parameter settings in proposed algorithms

Data sets

Figure 9: Fitness of FGARI, FGASA, FGATS, RI, SA, TS and GA algorithms on each data sets of table 2.

Table 4: Fuzzy rule set for multiple heuristic ordering

(VS=very small, S= small, M= medium) (H=high, VH=very high)

Figure 9 shows the performance of the proposed methods FGARI, FGASA, and FGATS are measured using best fitness and execution time. MATLAB tool was used to code the algorithms. Table 2 presents the datasets divided into nine different groups and Table 3 denotes the value of parameters used in suggested algorithms [9].Table 4 sets fuzzy rule for multiple heuristic ordering. Table 5 shows the characteristics of multiple ordering data sets in course timetabling. Table 6 compares solution obtained for single and fuzzy multiple orderings.

Table 5: Course timetabling problem characteristics

Data sets No. No. No. of No. of

of of students features

Table 6: Comparison of solution quality between single heuristic ordering and fuzzy multiple heuristic ordering.

Data Sets Best Single Heuristic

Fuzzy LD SD LCD LR WLD

Small 1 10 76 31 48 79 80

Table 7: Comparison of number of rescheduling procedures required to produce the solution.

Data Sets Best Single heuristic Fuzzy

LD SD LCD LE WLD

Table 7 compares the rescheduling procedures to provide the required solution. From the above table we can infer that combination of fuzzy heuristic orderings provide better results.

CONCLUSION

Case based reasoning gives a good solution by considering the hyper-heuristic approach and overcomes all the problems in the form of cases that is stored in the case base by predicting the best heuristic. It solves problem based on the previous good solutions and avoids problem solving from scratch saving a lot of effort. A wide range of artificial intelligent methods helped us to discover new knowledge in search space.

We have done ample amount of research survey to understand the problem definition and its importance. In this paper, we have compared different heuristic method for timetabling problem and their advantages and disadvantages with their experimental results. With that gist, in future we will try to develop a new technique to optimally solve above mentioned problem.

REFERENCES:

1. Nem, Sopha, et al. "Combination-based Solution for Timetable Organizer."WSEAS International Conference.Proceedings.Recent Advances in Computer Engineering Series.No. 9.WSEAS,( 2013).

2. Petrovic, Sanja, and Edmund K. Burke. "University timetabling." Handbook of scheduling: algorithms, models, and performance analysis 45 (2004): 1-23.

Petrovic, Sanja, and Rong Qu. "Case-based reasoning as a heuristic selector in a hyper-heuristic for course timetabling problems." (2002): 336-340.

Burke, Edmund K., et al. "Multiple-retrieval case-based reasoning for course timetabling problems." Journal of the Operational Research Society 57.2 (2006): 148-162.

Bellio, Ruggero, et al. "Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem." Computers & Operations Research 65 (2016): 83-92. Norberciak, Maciej. "Universal method for timetable construction based on evolutionary approach." International Journal of Applied Mathematics and Computer Sciences 3.3 (2006).

1. Schaerf, Andrea. "A survey of automated timetabling." Artificial intelligence review 13.2 (1999): 87-127.

2. Sani, H. M., and M. M. Yabo. "Solving Timetabling problems using Genetic Algorithm Technique" International Journal of Computer Applications 134.15 (2016).

3. Abadeh, MeysamShahvali Kohshori1and Mohammad Saniee. "Hybrid Genetic lgorithms for University Course Timetabling." (2012).

4. Nanda, Anirudha, Manisha P. Pai, and AbhijeetGole. "An algorithm to automatically generate schedule for school lectures using a heuristic approach." International journal of machine learning and computing 2.4 (2012): 492-495.

5. Burke, Edmund Kieran, and SanjaPetrovic. "Recent research directions in automated timetabling." European Journal of Operational Research 140.2 (2002): 266-280.

6. Zhang, Dezhen, et al. "A novel greedy heuristic algorithm for university course timetabling problem." Intelligent Control and Automation (WCICA), 2014 11th World Congress on. IEEE, (2014).

7. Aickelin, Uwe, Edmund K. Burke, and Jingpeng Li. "An evolutionary squeaky wheel optimization approach to personnel scheduling." Evolutionary Computation, IEEE Transactions on 13.2 (2009): 433-443.

8. De Causmaecker, Patrick, et al. "Agent technology for timetabling."Proceedings of the 4th international conference on practice and theory of automated timetabling. (2002).

9. Babaei, Hamed, and Amin Hadidi. "A Review of Distributed Multi-Agent Systems Approach to Solve University Course Timetabling Problem." (2014).

10. Rohit Pradip Soni and Suganya Mahadevan. A Probability based Object-Oriented Expert system for Generating Time-Table International Journal of Research in Computer Applications & Information Technology, Volume 1, Issue 1, July-September, (2013), pp. 52-58.

11. Asmuni, Hishammuddin, Edmund K. Burke, and Jonathan M. Garibaldi. "Fuzzy multiple heuristic ordering for course timetabling." Proceedings of the 5th United Kingdom workshop on computational intelligence (UKCI 2005). (2005).

12. Hsu, Chin-Ming, and Hui-Mei Chao. "A two-stage heuristic based class-course-faculty assigning model for increasing department- education performance." New Trends in Information and Service Science, 2009.NISS'09.International Conference on.IEEE, (2009).

13. Deris, Safaai, MohdHashim, and SitiZaiton. "Solving University Course Timetable Problem Using Hybrid Particle Swarm Optimization." (2008), pp 93-99.

14. Burke, Edmund K., J. Dario Landa Silva, and Eric Soubeiga. "Multi-objective hyper-heuristic approaches for space allocation and timetabling." Metaheuristics: Progress as Real Problem Solvers. Springer US, (2005).129-158.

15. Soria-Alcaraz, Jorge A., et al. "Iterated local search using an add and delete hyper-heuristic for university course timetabling." Applied Soft Computing 40 (2016): 581-593.

16. Gervás, Pablo, and Beatriz San Miguel. "Sequential Building of Constrained Timetables Using Rule-Based Heuristics: An Expert System for Automated Timetabling at UEM." UEM,6to.CongresoInternacionalde InvestigacionenCienciasComputacionales CIICC99. (1999).

17. Valtorta, Marco G., Bruce T. Smith, and Donald W. Loveland. The graduate course advisor: a multi-phase rule-based expert system. Duke University, Department of Computer Science, (1984).

18. Vermuyten, Hendrik, et al. "Developing compact course timetables with optimized student flows." European Journal of Operational Research (2015).

19. Pereira, Valdecy, and Helder Gomes Costa. "Linear Integer Model for the Course Timetabling Problem of a Faculty in Rio de Janeiro." Advances in Operations Researcp016 (2016).