Keywords

1 Introduction

Educational timetabling challenges include school timetabling, examination timetabling and university course. Basically, university timetable problem exists in two forms, viz course and examination timetable formats [1]. Examination scheduling or timetabling is one of the most difficult problems faced by academic community [2]. Timetabling challenge is defined as assigning examinations into a fixed number of timeslots hereby satisfying all university constraints [3]. However, for every institution the objective is to construct an effective and satisfactory examination timetable. An institutional timetable is said to be effective when it keep its users satisfied to a reasonable extent.

The main challenge of examination timetable scheduling is the population of students when compared to the inadequate available resources within a short period of time; hence, the population of students will always be more than available resources [4]. The problem addressed here deals with the assignment of examinations into a limited number of timeslots with respect to certain constraints for the undergraduate students with about a population of 15,000 from the Federal University of Agriculture, Abeokuta, Nigeria. There are two major types of constraints to be satisfied when dealing with a university examination timetabling which are: Hard and Soft constraints. Hard constraints are conditions that must be conceited while soft constraints may not be conceited, but it is desirable to have a good and feasible timetable. Hard constraints considered in this study was adopted from [5]: (i) every examination should be assigned to a venue at a particular timeslot; (ii) the scheduled examinations must not exceed the venue capacity; (iii) the maximum number of time period within a day should not be exceeded. Soft constraint include: (i) student preference for having an examination a day; (ii) finalist preference for having their examinations scheduled for first to second week of the examination. Satisfying all the constraints to have a good timetable is becoming increasingly difficult. The motivation of this study is the complexity of satisfying the constraints in examination timetable which includes high time consumption and manpower, thereby being too stressful. However, the major objective of this study is to design an algorithm that performs all hard and soft constraints using optimization algorithm and local search techniques to produce an effective timetable feasible solution. The rest of the paper is organized as follows. The literature review and related work is presented in Sect. 2. Section 3 presents the methodology and the results obtained. Section 4 discusses the implementation of the proposed system and the result obtained. The study concluded in Sect. 5.

2 Background and Review of Related Works

This section reviews some related work on examination timetabling, although quite a number of solutions have been suggested on solving course scheduling in a university system. Particle swarm optimization is one of the most common approaches applied by earlier researchers in solving timetabling for institution, metro transit network, etc. [6, 7].

Particle swarm optimization (PSO) is a population-based stochastic optimization mechanism inspired by social behavior of bird flocking or fish schooling. This approach solves a problem by having a population (swarm) of candidate solutions known as particles around in the search space over the particles position and velocity [8]. The velocity directs the flying of potential solution, called particles by following its current position known as local best known position, and is also guided toward the best known position in the search space known as the global best position, tracked by particle swarm optimizer [9]. The main concept of the PSO algorithm comprises of changing the velocity or accelerating each particle toward its gBest and lBest locations at each step. Acceleration is measured by a random term, with separate random numbers being generated for acceleration toward gBest and lBest locations [3]. However, the velocity and position of the particles are updated by Eqs. (1) and (2).

$$ V_{(t + 1)} = V_{(t)} + c1*{\text{rand}}()*\left( {P_{it} - X_{it} } \right) + c2*{\text{rand}}()*\left( {P_{gt} - X_{it} } \right) $$
(1)
$$ X_{it} = X_{it} + V_{(t + 1)} $$
(2)

where:

  • v(t) is the velocity component of particle ith at iteration t;

  • v(t+1) is the velocity component of particle ith at iteration t + 1;

  • Pit is best location of particle ith and

  • Pgt is the global best position of particle ith of the whole swarm,

  • c1 and c2 are learning factors for deriving how the ith particle approaching the position that is closer to the individual local best and global best,

  • rand() is a random number in the range [0, 1].

2.1 Literature Review

Pillay [10] presented a genetic programming approach for automated induction of construction heuristics for the curriculum-based course timetabling problem on ITC 2007 dataset. Ahmad and Shaari [3] proposed a PSO approach for solving examination timetable generator in three institutions. However, the proposed study has not been implemented and evaluated yet. Ilyas and Iqbal [11] analyzed hybrid heuristic and meta-heuristic technique to solve university course time tabling challenges. The study concluded that hybrid methods require more computational cost and is difficult to implement.

Chen and Shih [4] presented a constriction PSO with local search technique in solving university course timetabling problems. The experimental result shows the improvement in the solution quality and low computational complexity based on the small data sample used for implementation. Oswald and Anand [12] presented a novel hybrid PSO algorithm for solving university course timetabling problem. The experimental result gave a suboptimal solution, with major limitation on the inability to satisfy the soft constraints. Tassopoulos and Beligiannis [13] experimented with dataset from different high schools using PSO algorithm. The result shows that PSO outperformed the other techniques while [8] analyzed the application of PSO in course scheduling system. The study considered the hard and soft constraints and gave a quality solution. Najdpour and Feizi-Derakshi [14], Bhatt and Sahajpal [15], Karol et al. [16] developed an automatic course scheduling system using a generic algorithm, however, the former combined GA with cycle crossover approach for solving soft constraints with an improve solution when compared with the manually generated solution. Karol et al. [16] introduced known parallelization techniques to generic algorithm, which has high computational complexity.

The overall summary of the existing approaches to timetable scheduling problems includes difficulty of incorporating the constraints into scheduling procedures to improve schedule quality. Table 1 shows a summary of some existing solutions on timetabling problems related to this work.

Table 1 Summary of reviewed related work
Full size table

3 The Proposed Methodology

This study designed an automatic examination timetable system for the Federal University of Agriculture, Abeokuta (FUNAAB), Nigeria, using particle swam optimization algorithm and local search technique. In FUNAAB, the manual examination timetable was always done by a Timetable Committee known as (TIMTEC). However, in the process of designing the timetable by TIMTEC, several draft copies are corrected before the final timetable is reached due to the manual procedure and complexity of the scheduling; hence, there is a need for an automatic examination timetabling scheduling algorithm. The proposed PSO-based algorithm structure is shown in Fig. 1 while Table 2 shows the pseudocode of algorithm for the PSO-based algorithm, and Table 3 shows the local search techniques algorithm.

Fig. 1
figure 1

Proposed PSO-based algorithm structure

Full size image
Fig. 2
figure 2

Screenshot of examinations and students population for first semester

Full size image
Table 2 Pseudocode of algorithm
Full size table
Table 3 Local search technique algorithm
Full size table

3.1 Mapping of University Examination Timetable to PSO

Federal University of Agriculture Abeokuta uses three weeks’ time period for her examination, the three weeks duration starts on Monday–Friday due to the general five working days, when it falls during the festive period, then it is likely to start anytime during the week. In FUNAAB, the duration of an examination can be 2, 2.5, or 3 h. The time given on the timetable does not determine the time spent for the examination; the lecturer(s) determines that. Therefore, the preferable length of one timeslot is half an hour.

Considering the theory examination only, we have two sessions; morning (9 am–12 pm) and afternoon (2 pm–5 pm) for the examination. Maximizing the available facilities, examinations can be allocated to venues for 30 time period, considering the availability of venue for each session in the time period (three weeks). The Halls and their capacity are represented using one-dimensional array, respectively, where the name of a particular hall is referencing its capacity using the same index (as shown in Tables 4 and 5). The Examinations and their population will also be stored in one-dimensional array (as shown in Tables 6 and 7).

Table 4 Encoding of halls (H is the number of available halls)
Full size table
Table 5 Encoding of hall capacity
Full size table
Table 6 Encoding of examinations (N is the total number of examination)
Full size table
Table 7 Encoding of examination population
Full size table

The total timeslots per day will be 12 with half an hour per timeslot. The day of the timeslot can be calculated by taking the ceiling of the number divided by 12. For example, the day of timeslot number 15 will be equal to the ceiling (15/12) = 2 (Tuesday) and the day of timeslot number 38 will be equal to the ceiling (38/12) = 4 (Thursday). The whole timeslots of a week can be represented by one-dimensional array as shown in Table 8, the first 12 elements (1–12) of the array will represent the timeslots for Monday, the second 12 elements (13–24) of the array will represent the timeslots of Tuesday, etc.

Table 8 Timeslots of a week in one-dimensional array
Full size table

After the PSO algorithm has been applied, Tables 4, 5, and 8 are mapped to PSO to form Table 9. The total number of examinations is represented as one-dimensional array (Table 4) where the index of the array will represent implicitly the hall name and will also be used to calculate day and session of the day the examination is to hold.

Table 9 Mapping of examinations, venues, and timeslots to PSO
Full size table

After the allocation of examinations to venues using the PSO algorithm, local search algorithm is applied which works by searching for venues that fit for the population of each examination until examinations are exhausted.

3.2 Data Source

In this study, the examination timetable problem at the Federal University of Agriculture, Abeokuta was properly studied. The dataset presented in this study is a real data for 2016 undergraduate examinations for first and second semester. The dataset, the total number of examinations is 889 with about 15,000 students and 39 halls; the capacity of the venues for examinations is different from the normal capacity of venues due to the sitting arrangement during the examination. The number of examination days and timeslots are 15 days with 30 available timeslots. The dataset is available at TIMTEC of the Federal University of Agriculture, Abeokuta.

4 Implementation and Results Obtained

This section discusses the implementation and the experimental results obtained from the automatic PSO_LST timetable system. The minimum system requirement for this study includes Window XP or any compatible OS, NetBeans IDE/Eclipse, 2.4 GHz processor, 20 GB Hard disk, and 1 GB RAM. The following are the parameters required to execute this algorithm:

  • A list of all courses whose examination is to be done

  • A list of all Halls to be used for examination

  • The number of particles

  • The Constriction (Learning) factors

  • The Minimum fitness threshold

  • The Maximum fitness threshold

  • Days: the number of days required for the examinations.

Table 10 shows the venue and examination details for FUNAAB displaying the number of sessions per day.

Table 10 Venue and examination details
Full size table

4.1 Experimental Results

The algorithm has been tested using the first and second semester examination, session 2015/2016, of the Federal University of Agriculture, Abeokuta. Figure 3 shows the screenshot result from first semester examination scheduling test (Figs. 2, 4, and 5).

Fig. 3
figure 3

Screenshot of venues and their capacity for first semester

Full size image
Fig. 4
figure 4

Screenshot showing input of parameters for first semester

Full size image
Fig. 5
figure 5

Screenshot showing allocation of examinations to venues for first semester

Full size image

4.2 Results

This section gave an evaluation result of the FUNAAB examination timetable after using the particle swarm optimization technique and a result after combining the PSO and local search algorithm. Table 11 shows the table of the evaluation result obtained.

Table 11 Evaluation of results obtained
Full size table

  • Allocation: total number of examinations successfully allocated to an examination hall.

  • Un-allocation: total number of examinations not successfully allocated to an examination hall.

  • Clashes: Conditions where two examinations are allocated to the same venue.

  • Multiple: a condition where a venue has been allocated more than one examination.

  • Duplication: a condition where an examination has been allocated multiple times.

$$ {\text{Error}}(\% ) = \left( {{\text{Total number of clashes}}/{\text{Total number of courses}}} \right)*100 $$
(3)
$$ {\text{Deg}} . {\text{ of Acc}} = \left( {{\text{Total number of allocated}}/{\text{Total number of courses}}} \right)*100 $$
(4)

From the summary of the results on Table 11, using Eqs. (3) and (4), a degree of accuracy of 84%, error of 10% for first semester and a degree of 77%, error of 22% for second semester was observed. Based on this result, PSO algorithm could not provide a perfectly feasible solution but a near-optimal solution with the integration of local search technique as its degree of accuracy is in the range of 77–84%. It is observed from the results that, when the value of the learning factors c1 and c2 equals 1; more optimal solutions are obtained compare to when c1 and c2 equals 2.

5 Conclusion

In this study, an enhanced particle swarm optimization algorithm was presented for the Federal University of Agriculture, Abeokuta, Nigeria examination timetable scheduling by integrating the local search technique. The integration of the local search technique in the scheduling process helped to increase the effectiveness of the algorithm and the degree of accuracy against using only PSO. From the results obtained, combination of the particle swarm optimization algorithm and local search technique for the University examination timetable approaches near-optimal solution. By using the method of integrating PSO algorithm and LS technique, this research may produce feasible timetable for E-examinations, laboratory, and college timetable. A future research consideration would be to apply the PSO algorithm, LS technique, and course sandwiching to the University course and examination timetable.