Introduction

Universities across the world are accelerated to face another major financial crisis due to the unexpected loss of revenues caused by unprecedented pandemic. The higher education sector in Australia expects the revenue loss to be AUS$3–4.6 billion in the academic year 2019–20. In the academic year 2020–21, a number of international student enrolments in US universities and colleges was expected to reduce by at least a quarter. Likewise, a 100% fall in fee income from international (Non-EU and EU) students would result in a £6.9 billion loss of income to the UK higher education sector [1]. Many universities have, therefore, tried to reduce the impact on their permanent workforce by revising their infrastructure programs, cut executives’ pay, resizing casual staff, frozen hiring and drawn on any available reserves, improving resources’ utilisation or minimising operational costs via course timetabling and so on.

Due to varying numbers of courses, curricula, students but limited numbers of resources (e.g., lecturers, classrooms), a course timetabling problem (CTP) repeatedly arises every semester in academic institutes. For the practical course timetables without any conflict or event clash, all hard constraints must be satisfied [2]. Whilst soft constraints (e.g., the quality of timetables, staff preferences and resources’ utilisation) should be optimised [2]. Solving the CTP can be accomplished using academic staffs with/without automatically course timetabling tool. Without any automatic timetabling program, solving a large CTP is an extremely difficult task and requires a group of staff to work. Moreover, the computational time required for finding the optimal course timetables increases exponentially with the size of problem [3]. Because the CTP is classified to be a Non-deterministic Polynomial (NP)-hard problem [4]. Developing an automated timetabling tool, in which computational intelligence is embedded to generate the optimal timetables, is an alternative way to deal with these difficulties, especially for solving large sizes of CTP.

Computational Intelligence (CI) based on nature-inspired optimisation methods, e.g., Genetic Algorithm [5], Frog Leaping Algorithm [6], Artificial Immune System [7], Ant Colony Optimisation [4], Grey Wolf Optimisation [8], Bat Algorithm [9], Particle Swarm Optimisation (PSO) [10], has become very popular to solve the large sizes of combinatorial optimisation problems [11]. Although there is no guarantee to yield an optimal solution, these algorithms can practically solve the NP-hard problems within acceptable computational time [12]. Conventional PSO has been widely applied to deal with the NP-hard problems in many problem domains because of several advantages such as a few parameters to be identified, easy for learning and implementation, and little memory requirements to solve [13]. Therefore, in this present paper, we proposed to improve newer variants of PSO, such as Standard PSO (SPSO), Accelerated PSO, and Maurice Clerc PSO (MCPSO) by adopting hybridisation strategies.

In cases of very high complex constraints and very large problem size, hybridisation strategies can improve the performances of PSO by balancing exploitation and exploration searches [2]. Many types of Local Search (LS) strategies, e.g., Neighbourhood Search [14], Hill Climbing [15], Exchange Operator (EO) [2, 16], Local Beam Search [17], Insertion Operator (IO) [2], have been found to hybrid with PSO for dealing with the CTP. Besides avoiding traps in a local optimum solution, hybrid approaches can increase the opportunity to discover the global best solution quickly [18]. According to a literature survey above, only one article has considered more than one type of LS strategies (IO and EO) embedded in MCPSO for solving the CTP [2]. However, the study on hybridisation between SPSO and difference IO:EO ratios to construct the best practical course timetables having the minimal academic operating costs has not been reported.

The objectives of this work were to: (i) develop SPSO and embedded it into the Hybrid Particle Swarm Optimisation-based Timetabling (HPSOT) program for solving the proposed CTP; (ii) and compare the performances of the SPSO and its hybridisations using five combinations of IO:EO ratios in terms of minimal total operating costs, computational time, and convergence speed. This paper is an extension of a conference paper [2] presented in the 13th International Conference on Blended Learning (ICBL 2020). The next section describes the CTP and its constraints for this research work. The third section describes the concept of PSO and its variants followed by the processes of the HPSOT program in the fourth section. The fifth section shows the experimental results and analysis before conclusions in the last section.

Course Timetabling Problem

Scheduling or timetabling is an important problem and active area of research with applications in many fields [19], e.g., transportation [20], sport [21], healthcare (e.g., nurse rostering [22], surgery [23]), industrial production [8], employee [24], educational institutes (e.g., secondary school [25], university [18]). The university course timetabling problem (UCTP) is a classic and famous optimisation problem in the field of computer science and management science [26]. The UCTP is to find a method to allocate all course or events into the given timeslots and classrooms, whilst all pre-defined constraints must be satisfied [27].

Most of the UCTP constraints can be mainly classified into two groups including hard constraints and soft constraints [12]. The most important constraints are hard constraints, each of which must be satisfied to guarantee the candidate timetables to be the feasible timetables [28]. Soft constraints can be more relaxed, some violations of soft constraints can be accepted but it should be minimised [4].

The characteristics of all hard constraints (H) considered in this work can be explained as follows [18]: (H1) all given courses must be scheduled, in which all lectures or laboratories for each course must be assigned to different periods; (H2) lecturers and students can only attend one lecture or event at a time; (H3) each timeslot for the given classrooms cannot assign a lecture or event more than one; (H4) all courses required by lecturers and students must not be scheduled in their unavailable periods; (H5) each course must be scheduled in the specific classrooms according to its given requirements (e.g., types of classroom, room facilities, and building location); and (H6) all events or lectures for a course required consecutive timeslots must be satisfied.

H1–H3 are related to the event-clash constraints for course timetabling problems and they can be found in most of the educational institutes [12]. H4–H6 are particular constraints for each lecturer, curriculum, and courses found in most of the universities in Thailand. In addition, Soft Constraints (S) can be described as follows [18]: (S1) all courses should be scheduled in the proper types of the classroom to keep away from unnecessary renting or operating costs (currency unit per period); (S2) each course taught by the given lecturer(s) should be assigned according to their preferred working days and periods for saving the hiring or employing costs (currency unit per period); and (S3) each classroom should be used in consecutive periods of a day for reducing the number of times to prepare or clear that classroom after usability (per time).

The objective functions or f(xi) for this work are calculated by considering S1–S3 for minimising the total operating costs obtained from the candidate timetables as shown in Eq. (1) [29]:

$$f(x_{i} ) = \,\,\psi_{1} S_{1} + \psi_{2} S_{2} + \psi_{3} S_{3}$$
(1)
$${\text{Subject to}}: H_{k} = 0,\,\forall k.$$
(2)

The aim of Eq. (1) is to evaluate the total operating costs related to S1–S3. The weightings (ψ1-ψ3) for each soft constraint depend upon the user preferences for each educational institution. In this work, ψ1-ψ3 were set at 50 (currency units/h), 300 (currency units/h), and 2.5 (currency units/times), respectively. Equation (2) is to check the feasible timetables, each of which H1–H6 cannot be violated. Where k is an index for the kth hard constraint (k = 1, 2,…, K), where K is the given number of hard constraints.

PSO Variants and Literature Review

Particle Swarm Optimisation (PSO) was firstly introduced by Kennedy and Eberhart in 1995 [30]. The inspiration of PSO was the swarm behaviour in nature, e.g., bird flocking, fish schooling [31]. PSO is also classified to be a stochastic optimisation method based on Swarm Intelligence (SI) [13] that performs searching via a group of particles being updated from iteration to iteration [32]. Moreover, PSO has been applied to solve many optimisation areas, computational intelligence, and design applications [31]. Because of its many advantages, such as simplicity and flexibility [31], fast convergence and few parameter settings [16], PSO has become one of the popular swarm intelligent methods [31]. According to a brief literature review, many PSO variants have been continuously extended and proposed, such as original PSO [16], Accelerated PSO (APSO) [31], Standard PSO (SPSO) [15], Maurice Clerc PSO (MCPSO) [14].

The general concepts of the aforementioned variants of PSO can be briefly described as follows. The essential parameters of PSO are identified in the initialisation step. Each particle or solution xi (i = 1, 2, …, P) is randomly created before computing its fitness value using the objective function or f(xi). Where i is the index of particles, whereas P is the population size (number of particles). Next step, the iteration best solution (xtbest) and the global best solution (g*best) are specified by considering Eq. (3) [32]. Where Inow is the current iteration, whilst t is the index of iterations:

$$\begin{gathered} x_{{{\text{best}}}}^{t} \, = \min \{ f(x_{i}^{t} )\} ,\,\,\,\,i \in (1,\,\,2,\,3,\,...,P), \hfill \\ g_{{{\text{best}}}}^{*} \, = \min \{ f(x_{i}^{t} )\} ,\,\,\,\,i \in (1,\,\,2,\,3,\,...,P),\,\,\,t \in (1,\,\,2,\,3,\,...,I_{{{\text{now}}}} ). \hfill \\ \end{gathered}$$
(3)

For an original PSO, a new solution (xit+1) for a particle i is achieved using velocity and position vectors according to Eqs. (4, 5) [33]. vi is the velocity for particle i, whereas c1 and c2 factors are the positive acceleration coefficients. r1 and r2 parameters are random variables uniformly distributed from 0 to 1 [32]:

$$v_{i}^{t + 1} = v_{i}^{t} + \,\,c_{1} \,r_{1} \,(x_{{{\text{best}}}}^{t} - x_{i}^{t} ) + \,c_{2} \,r_{2} \,(g_{{{\text{best}}}}^{*} - x_{i}^{t} )$$
(4)
$$x_{i}^{t + 1} = x_{i}^{t} + \,\,v_{i}^{t + 1} .$$
(5)

In the case of SPSO, a new solution xit+1 is produced using velocity and position vectors according to Eqs. (6) and (5) [32, 33]. Where ω is the inertia weight factor that is used for balancing the global exploration and local exploitation [32]:

$$v_{i}^{t + 1} = \omega \,v_{i}^{t} + \,\,c_{1} \,r_{1} \,(x_{{{\text{best}}}}^{t} - x_{i}^{t} ) + \,c_{2} \,r_{2} \,(g_{{{\text{best}}}}^{*} - x_{i}^{t} ).$$
(6)

New velocity and position for a solution xit+1 for MCPSO can be updated using Eqs. (7, 8), and (5) [33]. Where, k is a constriction factor to control particles velocity, φ is a positive parameter depending on the given acceleration coefficients [33]:

$$v_{i}^{t + 1} = k(\,v_{i}^{t} + \,\,c_{1} \,r_{1} \,(x_{best}^{t} - x_{i}^{t} ) + \,c_{2} \,r_{2} \,(g_{best}^{*} - x_{i}^{t} ))$$
(7)
$$k = \frac{2}{{\left| {2 - \phi - \sqrt {\phi^{2} - 4\phi } } \right|}},\,\,\,\,\,\,\phi = c_{1} + c_{2} ,\,\,\,\,\,\,\phi > 4.$$
(8)

For APSO, a new solution xit+1 is produced using velocity and position vectors from Eq. (9, 10), and Eq. (5). Where εt is drawn from N(0, 1) [31]. Where c0 is an initial value of random parameter distributed from 0.5 to 1 [31]. Where, γ is a control parameter that should be set at 0.9–0.97 [31]. For easier implementation, updating velocity and position vectors for APSO can be switched to use only Eq. (11) [31]:

$$v_{i}^{t + 1} = v_{i}^{t} + \,\,c_{1} \,(g_{{{\text{best}}}}^{*} - x_{i}^{t} ) + c_{2} \varepsilon_{t}$$
(9)
$$c_{2} = c_{0} \gamma^{t} ,\,\,\,\,\,\,(0 < \gamma < 1)$$
(10)
$$x_{i}^{t + 1} = (1 - c_{1} )x_{i}^{t} + \,\,c_{1} \,(g_{{{\text{best}}}}^{*} ) + c_{2} \varepsilon_{t} .$$
(11)

The quality of solution (fitness value) for a new solution xit+1 is measured using the objective function f(xit+1). The solution xtbest can be replaced by a new solution xit+1 if its fitness value is better than that obtained from the f(xtbest). If a fitness value obtained from the f(xit+1) is also better than that obtained from the f(g*best), the g*best will be replaced by a new solution xit+1. These processes are repeated until the maximum iteration (I) or the given stop criterion is achieved.

Nowadays, using only conventional or standard PSO to solve most of the real-world constraint optimisation problems is a very difficult task [17]. Conventional PSO often suffers from low exploration ability and premature convergence, especially for very high complex multimodal problems [34]. The hybrid strategies have been widely accepted to increase the performance of algorithms for obtaining better solutions [35]. According to a literature survey on Scopus database using “course timetable*” and “particle swarm” as keywords for document search in data records (e.g., article title, abstract, and keywords) covering the period from the last two decades, several variants of PSO and their hybridisations for solving the UCTP are reported in Table 1.

Table 1 Literature survey of PSO variants with/without hybridisation for solving the UCTP
Full size table

According to Table 1, the real-world and benchmark course timetabling problems have been solved using many variants of PSO. Genetic Algorithm (GA), Interchange Operator, and Hill Climbing heuristic have also been applied to hybrid with PSO [16] and Standard PSO (SPSO) [15] to solve the real-world problems of course timetabling. Local Beam Search, Neighbourhood Search, and Constraint-based Reasoning have been hybridised with Maurice Clerc PSO (MCPSO) [14, 17, 36]. However, hybridising SPSO with different ratios between Insertion Operator (IO) and Exchange Operator (EO) has not been reported.

Hybrid Particle Swarm Optimisation-Based Timetabling Tool

For this work, a HPSOT program was designed and developed using two programming languages including TCL/TK language for developing the graphical user interface and C language for generating the best timetable. The HPSOT tool was proposed to construct the practical timetables for lecturers, students, and classrooms having the lowest total university operating costs. Both Standard PSO (SPSO) and Maurice Clerc PSO (MCPSO) were integrated with the HPSOT tool with five different ratio settings of Exchange Operator (EO) and Insertion Operator (IO). The main procedure of the HPSOT tool can be divided into six sequential steps, as shown in Fig. 1.

Fig. 1
figure 1

Pseudocode of the HPSOT program

Full size image

According to Fig. 1, the first step is an initialisation process for the HPSOT tool. All input data, such as numbers of courses, lecturers, rooms, curricula, etc., are uploaded before setting the essential parameters for both SPSO and MCPSO. Then, the total number of events (n) is calculated from the total number of teaching periods required for all courses (see Fig. 2). An event list is then created to keep a set of n events. To reduce the probability of getting infeasible timetables in this process, the sequence of events in the event list is sorted using a constructive heuristic named the Largest Unpermitted Period Degree (LUPD) [39].

Fig. 2
figure 2

Initialisation of a candidate solution or timetable

Full size image

Next process is to create a candidate solution or timetable xi, as shown in Fig. 2 for an example. The dimension size of a candidate timetable is considered from the numbers of given classrooms, working days per week (d), and periods per day (p). Then, all events in the sorted list are assigned into an empty timetable for producing a candidate timetable xi (i = 1, 2, 3,…, P), where P is the number of given population or particles. From Fig. 2, it can be seen that all encoded events representing Physics, Calculus, and Sport subjects were successfully scheduled in a candidate solution. However, the “0” values located in the candidate solution illustrated in Fig. 2 represent the idle (empty) periods or timeslots.

After that, a random key technique [40] is applied for each xi solution to accommodate a solution evolution or movement process. A new list of a random key having the same dimension size of the xi timetable is created. Each slot of a random key list is assigned to have a random number between 0 and 1 using the Uniform Distribution. Both initial timetable construction and random key processes for each particle xi will be repeated until getting to the maximum number of particles (P).

The second step is the movement (evolution) processes for both SPSO and MCPSO. In the case of MCPSO, updating velocity for each solution or particle xit+1 is produced using Eq. (7)-(8), whereas updating velocity according to Eq. (6) is used for SPSO. The position of particle xit+1 for both SPSO and MCPSO is then updated using Eq. (5).

For the university course scheduling case, an example of a movement process is shown in Fig. 3. If the first event of subject number 2 in the xi(t) solution is selected for moving, then the next step is to calculate a new value of velocity (or random key) for xi(t) based on the values obtained from the first event of subject number 2 embedding in both xtbest and the global best g*best solutions. If a new value of velocity is equal to 0.07, it will be replaced into the same position of subject number 2 in the xi(t) solution. After that, the movement process of the remaining events in the xi(t) solution is also implemented similar to the aforementioned steps. Then, a list of random keys is increasingly sorted before moving all events (courses) of the xi(t) solution to the new positions according to the ascending order of new random keys.

Fig. 3
figure 3

Example of movement processes using a random key technique for SPSO

Full size image

After the movement process, a new solution or timetable xit+1 may be either feasible or infeasible timetable. In the case of an infeasible solution, the repair process was adopted from previous research [18] to rectify all infeasible timetables to obtain feasible timetables. The main rectifying steps can be described as follows: (i) find the encoded events having some violations of hard constraints (H1–H6); (ii) for each violated event, seek the possible idle or empty timeslots without H1–H6 violations (called the feasible timeslots) for that violated event before swapping randomly; (iii) if the feasible timeslots from the previous step cannot found, search the possible non-empty timeslots (events) without any violation of H1–H6 for that violated event and vice versa before random swapping; and (iv) repeat the steps (ii) and (iii) until all violated events in a candidate solution are rectified.

The third step is to determine the quality of solution xit+1 using Eq. (1). If f(xit+1) is better than f(xtbest), the current best particle xtbest is replaced by the xit+1 solution. Moreover, a particle g*best is replaced by the xit+1 if the quality of xit+1 solution is also the best-so-far timetable. These processes are repeated until the quality of the solution obtained from all particles is determined.

The fourth step is to produce the hybridisation for SPSO and MCPSO using two strategies of Local Search (LS) including an Insertion Operator (IO) and Exchange Operator (EO), as shown in Figs. 4 and 5, respectively. Both operators are demonstrated for their ability to improve the solution quality according to Eqs. (12) and (13) [2]:

$$x_{i}^{t + 1^{\prime}} = x_{i}^{t + 1} + \,\,IO$$
(12)
$$x_{i}^{t + 1^{\prime}} = x_{i}^{t + 1} + \,\,EO.$$
(13)
Fig. 4
figure 4

Example of an Insertion Operator (IO)

Full size image
Fig. 5
figure 5

Example of an Exchange Operator (EO)

Full size image

In this present work, five strategies of IO:EO ratios including IO(100%), IO(75%):EO(25%), IO(50%):EO(50%), IO(25%):EO(75%), and EO(100%), were proposed for both SPSO and MCPSO hybridisations. For examples, MCPSO + IO(100%) means that all particles or solution xit+1 (i = 1, 2, 3,…, P) must be produced using only IO strategy for each iteration. Likewise, the MCPSO + IO(75%):EO(25%) indicates that 75% of particles in the population were hybridised using IO, whereas the hybridisation of the remaining particles (25%) were carried out using EO. After this process, a new improvement solution was changed from xit+1 to xit+1′.

In the fifth step, if some infeasible timetables were found from the previous step (xit+1′), these timetables were then rectified using the repair process again. The quality of solution xit+1′ was determined using Eq. (1) before updating xtbest and g*best. The processes from step 2 to step 5 were repeated until reaching the maximum iterations (I). For the final step, the best timetable for each lecturer, student, and room obtained from the proposed program was displayed together with the computational report.

Computational Experiment

The HPSOT tool for constructing the efficient course timetables with the minimum total operating costs in the university has previously been developed. Therefore, this experiment was designed to explore and compare the performances of hybrid SPSO and MCPSO with five combinations of IO:EO ratios, which were 0%:100%; 25%:75%; 50%:50%; 75%:25% and 100%:0%. In this work, the best settings for both SPSO and MCPSO parameters were adopted from previous work [29]. Eleven real-world course timetabling problem instances were also adopted from the previous research [41]. The timetable was based on 1 h per period. Due to the different sizes of the problem instances, the parameters were ranged from 173 to 1,009 events; 53 to 142 classrooms; 19 to 66 curricula; and 30 to 143 lecturers, which need to be scheduled in timetable ranged from 10 to 13 periods per day; 5 to 7 days per week. The number of computational run for each instance was repeated ten times using different random seeds. Each instance was tested on a personal computer with Core i7 3.20 GHz of CPU and 8 GB of Ram. The computational results for hybrid SPSO and MCPSO were analysed in terms of minimum (Min), maximum (Max), Mean (currency unit), standard deviation (SD), computational time (minute) and P-value obtained from the analysis of variants (ANOVA) as shown in Table 2.

Table 2 Performance comparisons between the conventional SPSO and MCPSO as well as its hybridisations
Full size table

According to Table 2, the hybrid performances of both SPSO and MCPSO with five combinations of IO:EO ratios to generate the preferable course timetables with the minimum total operating costs are better than the performances obtained from their conventional variants for all problem instances. MCPSO + IO(75%):EO(25%) performed best as it produced timetables with the lowest mean operating costs for four out of eleven problem instances including instance numbers 6, 7, 8 and 11. Secondly, SPSO + IO(75%):EO(25%) was also the best performance for problem instance numbers 2 and 5. According to the mean values of the total operating costs associated with the generated timetables, both MCPSO + EO(100%) and MCPSO + IO(50%):EO(50%) were the best hybridisation ratio for two problem instances, whereas MCPSO + IO(25%):EO(75%) was the best only one problem instance. Moreover, the differences in the mean values achieved by SPSO and MCPSO methods were statistically significant with a 95% confidence interval using ANOVA (P value ≤ 0.05), especially in medium–large problem instances. The standard deviations obtained from all proposed methods were moderately different for all problem instances.

The average computational times required by hybrid SPSO and MCPSO with five combinations of IO:EO ratios were quicker than that obtained from their conventional variants for all instances. According to the largest instance in Table 2, the execution time required by both hybrid SPSO and MCPSO was reduced up to 60.30% and 60.85%, respectively. This was because the number of generated solutions in the current population is double after using IO and EO strategies. To limit the amount of search at the 24,000 candidate solutions, the number of iterations (I) for the proposed hybrid methods was, therefore, reduced by half.

The convergence speed comparisons to construct the best so far timetable for hybrid SPSO and MCPSO with five combinations of IO:EO ratios are shown in Fig. 6 and Fig. 7, respectively. The problem instance number 11, which was the largest size, was selected to be an example for this comparative study. Although SPSO + IO(75%):EO(25%) had a lower average of best so far solutions than other methods in the initial generations, the average value obtained from the middle to the last generations for this hybrid approach was the best, as shown in Fig. 6. Likewise, the aforementioned results using MCPSO + IO(75%):EO(25%) had a lower average of best so far solutions than other approaches during the middle generations. The average value obtained from the hybrid approach was also the best in the last generation, as shown in Fig. 7. Therefore, the proposed hybrid strategies with combinations of IO:EO ratios improved the performances of both SPSO and MCPSO in terms of the solution quality and convergence speed.

Fig. 6
figure 6

Convergence plots of hybrid SPSO with LS for the 11th problem instance

Full size image
Fig. 7
figure 7

Convergence plots of hybrid MCPSO with LS for the 11th problem instance

Full size image

Conclusions

A Hybrid Particle Swarm Optimisation-based Timetabling (HPSOT) program was developed for solving the real-world university course timetabling problem in Thailand. Both hybrid SPSO and MCPSO with five combinations of IO:EO ratios were proposed and embedded into the HPSOT tool for constructing the desirable timetables with minimum total operating costs. The statistical analysis on the computational results suggested that the differences in average values achieved by conventional SPSO and MCPSO methods were statistically significant with a 95% confidence interval. The averages of the total operating costs associated with the timetables produced by hybrid SPSO and MCPSO with IO:EO ratios were better than those results obtained from their original variants for all problem instances. According to fair comparison in term of the amount of search, the computational times required by all proposed hybrid approaches were faster than their original variants for all problem instances. Moreover, the convergence speeds generated from the hybrid SPSO and MCPSO using the IO:EO ratio of 75%:25% were the best configurations comparing with the other hybrid ratios.